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

Метод линейного криптоанализа впервые был применен для атаки блочного шифра FEAL [376] и затем DES [377]. Данный метод использует линейные приближения. Это озна­чает, что, если выполнить операцию XOR над некоторыми битами открытого текста, затем над некоторыми битами шифротекста, а затем выполнить XOR результатов предыдущего суммирования, можно получить бит, который равен сумме некоторых бит ключа. Это назы­вается линейным приближением, которое может быть верным с некоторой вероятностью р. Если р  0,5, то этот факт можно использовать для раскрытия бит ключа.

Рассмотрим данный метод подробнее. Пусть в общем виде линейное выражение задается уравнением:

(3..1)

где i₁, i₂,…, i_a, j₁, j₂,…, j_b, и l_1, l_2,…, l_c, позиции некоторых бит открытого текста Р, шиф­ротекста С и ключа К. (Напомним, что суммирования в (3.1) выполняется по модулю 2) Для случайно выбранного открытого текста Р и соответствующего шифротекста с уравне­ние (3.1) выполняется с вероятностью р  1/2. Величина |р-1/2| определяет эффективность уравнения (31).

Таким образом, при заданном эффективном линейном выражении можно определить один бит ключа К, воспользовавшись следующим алгоритмом максимума правдоподобия:

Алгоритм 1.

Шаг 1. Пусть T задает число открытых текстов, таких, что левая часть уравнения (3.1) равна нулю.

Шаг 2. Тогда, если T > N/2 (N — общее число открытых текстов),

угадываем

Вероятность успеха увеличивается с ростом N или |р — 1/2|.

Рассмотрим криптоалгоритм DES с n-циклами криптографического преобразования. С учетом 48-битного ключа К_n и F-функции линейное выражение принимает следующий вид:

(3.2)

где через С^R обозначена правая половина блока шифротекста.

Оценивая эффективность уравнения (3.2) при подстановке различных кандидатов, можи восстановить К_n и Для этого следует воспользоваться следующим алгоритмом максимального правдоподобия:

Алгоритм 2.

Шаг 1. Пусть Т задает число открытых текстов, таких, что левая часть уравнения (3.2 равна нулю для каждого кандидата К_n⁽ⁱ⁾ (i = 1,2,...).

Шаг 2. Обозначим через Т_mах и Т_min максимальное и минимальное значения средиT_i .

Тогда

Рассмотрим линейные приближения для S-блоков. Задача заключается в исследовании вероятности того, что некоторый бит на входе S-блока равняется некоторому биту на выхо­де. Однако в более общем случае полезно рассмотреть зависимости сумм бит на некоторых входных и выходных позициях.

Для заданного S-блока S_a(a = 1,2,..., 8) и чисел 163и115 определим NSa(,) - число выходных значений для 64 возможных значений на входе S_а, таких, что результат логической операции «И» суммы по модулю 2 некоторых бит значения на входе S_а и числа  равен результату логической операции «И» суммы по модулю 2 некоторых бит значения на выходе S_а и числа . Данное условие можно записать в виде:

(3.3)

где S_(x)_t — t-й бит выходного значения S_ при заданном на входе значении х.

Если NSa(,) не равно 32, можно сделать вывод о корреляционной зависимости вход­ных и выходных бит S_. Например, уравнение 3.4 показывает, что четвертый бит входных значений S₅ равен сумме всех бит выходных значений с вероятностью 12/64 = 0,19:

NS₅(16,15)=12. (3.4)

Следующее уравнение выполняется с вероятностью 0,19 для случайно выбранного X и зафиксированного К (с учетом перестановки в Е- и Р-блоках):

(3.5)

В усеченной табл. 3.19 представлены значения NS₅(,) - 32 для всевозможных значе­ний  (номер строки) и  (номер столбца). Исследование полной таблицы показывает, что уравнение (3.4) является наилучшим линейным приближением во всех S-блоках (то есть величина |NS₅(,)| принимает максимальное значение). Следовательно, уравнение (3.4) является наилучшим линейным приближением для F-функции.

Из определения S-блоков вытекает, что

1. NSa(,) четно;

2. если  = 1,32 или 33, то NSa(,) = 32 для всех Sa и Sa.

Рассмотрим криптоалгоритм DES с тремя циклами преобразования. Следующее уравне­ние выполняется для первого цикла с вероятностью 12/64:

(3.6)

где через P^R и P^L обозначены правая и левая половины открытого текста. Аналогичное уравнение выполняется для последнего третьего цикла преобразования:

(3.7)

где через C^R и C^L обозначены правая и левая половины шифротекста.

Таблица 3.19 - Криптоанализ DES: усеченная таблица значений NS₅(,) - 32

Таким образом, линейное приближение для третьего цикла выглядит следующим образом:

(3.8)

Для случайно выбранного открытого текста Р и соответствующего шифротекста С урав­нение (3.8) выполняется с вероятностью (12/64)² + (1 - 12/64)² = 0,70. Поскольку уравне­ние (3.5) является наилучшим линейным приближением F-фун-кции, уравнение (3.8) явля­ется наилучшим приближением для DES с тремя циклами. Теперь, воспользовавшись Алго­ритмом 1, можно решить уравнение (3.8) для того, чтобы получить значение К¹₂₂ К³₂₂

Описанный метод можно обобщить на полный DES с шестнадцатью циклами криптогра­фического преобразования.