Линейный криптоанализ

Линейный криптоанализ — это метод вскрытия симметричных блочных шифров, основанный на построении линейных аппроксимаций (приближений) для нелинейных компонентов шифра (S-блоков). Целью атаки является нахождение связи между открытым текстом, шифротекстом и ключом, которая с вероятностью, отличной от 1/2, выполняется для случайных данных. Атака была впервые предложена японским криптографом Мицуру Мацуи в 1993 году и первоначально применена к шифру FEAL, а затем и к DES.

История

Линейный криптоанализ возник как развитие идей дифференциального криптоанализа, предложенного в конце 1980-х годов. В 1992 году Мицуру Мацуи и Хидэки Имаи опубликовали работу, в которой описали метод линейного приближения для DES. Полноценная атака на 16-раундовый DES была продемонстрирована Мацуи в 1993 году. Для вскрытия одного ключа требовалось около 2^43 пар открытый-шифротекст, что было значительно меньше полного перебора (2^56). Позднее метод был усовершенствован: появились варианты с использованием нескольких линейных аппроксимаций (многомерный линейный криптоанализ) и методы снижения сложности (например, атака с нулевой корреляцией).

Основные принципы

Линейная аппроксимация S-блоков

Симметричные блочные шифры часто используют нелинейные таблицы замен (S-блоки). Для каждого S-блока можно построить линейное уравнение, связывающее входные и выходные биты. Например, для S-блока с 4 входами и 4 выходами можно записать:

\[ \bigoplus_{i \in A} x_i \oplus \bigoplus_{j \in B} y_j = 0 \]

где \(x_i\) — входные биты, \(y_j\) — выходные биты, \(A\) и \(B\) — подмножества битов. Вероятность выполнения такого уравнения для случайного входа должна быть близка к 1/2. Если она существенно отличается (например, 0.75), то это даёт возможность для атаки.

Линейный криптоанализ DES

Для DES Мацуи нашёл 14-раундовую линейную аппроксимацию с вероятностью \(1/2 + 2^{-21}\). Это позволило восстановить 26 бит ключа, используя около \(2^{43}\) известных открытых текстов. Оставшиеся 30 бит перебирались полным перебором.

Методология атаки

Этапы

1. Построение линейной аппроксимации — для каждого раунда шифра находится линейное уравнение, связывающее входные и выходные биты раунда.
2. Комбинирование раундов — с помощью «piling-up lemma» (леммы о накоплении) вычисляется общая вероятность аппроксимации для всего шифра.
3. Сбор статистики — атакующий перебирает возможные значения части ключа (обычно биты последнего раунда) и для каждого кандидата проверяет, насколько часто выполняется линейное уравнение на парах открытый-шифротекст.
4. Выбор ключа — кандидат, дающий наибольшее отклонение вероятности от 1/2, считается верным.

Piling-up lemma

Если имеется \(n\) независимых линейных аппроксимаций с вероятностями \(p_i = 1/2 + \epsilon_i\), то вероятность их суммы (XOR) равна:

\[ p = \frac{1}{2} + 2^{n-1} \prod_{i=1}^n \epsilon_i \]

Это позволяет оценить, насколько сложно будет отличить истинный ключ от случайного.

Разновидности

Многомерный линейный криптоанализ

Использует несколько независимых линейных аппроксимаций одновременно. Это повышает эффективность атаки, особенно для шифров с короткими ключами. Метод был предложен в 1990-х годах и применялся, например, к шифру Serpent.

Нулевая корреляция

Атака, основанная на поиске линейных аппроксимаций с нулевой корреляцией (вероятность ровно 1/2). Такие аппроксимации позволяют отличить шифр от случайной перестановки.

Линейный криптоанализ с известным открытым текстом

Классический вариант, требующий знания пар открытый-шифротекст. Атакующий может выбирать тексты произвольно, но не может их изменять после начала атаки.

Линейный криптоанализ с выбранным открытым текстом

Атакующий может выбирать открытые тексты для шифрования. Это может упростить построение аппроксимаций, но требует большего контроля над шифром.

Применение к современным шифрам

AES

Линейный криптоанализ против AES (Rijndael) считается неэффективным из-за высокой нелинейности S-блоков (использующих обратные элементы в поле Галуа) и большого числа раундов. Наилучшие известные атаки требуют более \(2^{128}\) операций, что превышает полный перебор.

ГОСТ 28147-89

Для российского стандарта ГОСТ 28147-89 (ныне ГОСТ Р 34.12-2015 «Магма») линейный криптоанализ возможен, но требует большого количества пар открытый-шифротекст (порядка \(2^{64}\) для 32 раундов). Практическая атака на полный шифр не реализована.

Blowfish и Twofish

Эти шифры имеют сложные S-блоки, зависящие от ключа, что затрудняет линейный криптоанализ. Для Blowfish известны атаки только на версии с малым числом раундов.

Защита от линейного криптоанализа

Проектирование S-блоков

S-блоки должны иметь минимальное линейное смещение (bias). Для этого используются нелинейные функции, например, обратные элементы в поле Галуа (как в AES) или случайные перестановки с проверкой.

Увеличение числа раундов

Чем больше раундов, тем сложнее построить длинную линейную аппроксимацию. Современные шифры (AES-256, Кузнечик) имеют 10–16 раундов, что делает атаку непрактичной.

Использование ключезависимых S-блоков

Если S-блоки зависят от ключа (как в Blowfish), атакующий не может заранее построить аппроксимацию.

Шифры с изменяемой структурой

Например, шифры на основе сетей Фейстеля с переменным числом раундов или с динамическими перестановками.

Критика и ограничения

• Требование большого количества данных — классический линейный криптоанализ требует миллионов пар открытый-шифротекст, что на практике может быть недостижимо.
• Зависимость от шифра — метод эффективен только для шифров с линейными слабостями. Современные стандарты (AES, Кузнечик) спроектированы с учётом защиты от этого метода.
• Вычислительная сложность — для каждого кандидата ключа требуется перебор, что может быть сопоставимо с полным перебором.

Примеры успешных атак

• DES — вскрытие 16-раундовой версии с 2^43 парами (1993).
• FEAL — вскрытие 8-раундовой версии с 2^24 парами.
• Serpent — многомерная атака на 7-раундовую версию (2000).
• PRESENT — атака на 26-раундовую версию (2012).

Линейный криптоанализ в России

В России метод активно изучается в рамках криптографических исследований. Российские стандарты шифрования (ГОСТ Р 34.12-2015 «Магма» и «Кузнечик») прошли проверку на устойчивость к линейному криптоанализу. Для «Кузнечика» (блочный шифр с длиной блока 128 бит и ключом 256 бит) линейный криптоанализ считается неэффективным из-за высокого числа раундов (10) и нелинейного преобразования S-блоков.

Источники

• Matsui, M. (1993). "Linear Cryptanalysis Method for DES Cipher". Advances in Cryptology — EUROCRYPT '93.
• Heys, H. M. (2002). "A Tutorial on Linear and Differential Cryptanalysis". Cryptologia.
• Biham, E., Shamir, A. (1991). "Differential Cryptanalysis of DES-like Cryptosystems". Journal of Cryptology.
• Knudsen, L. R., Robshaw, M. (2011). "The Block Cipher Companion". Springer.
• ГОСТ Р 34.12-2015. "Информационная технология. Криптографическая защита информации. Блочные шифры".