N. Дифференциальный и линейный криптоанализ DES

Показывать лекцию целиком

В этом приложении мы кратко обсуждаем две проблемы, которые связаны с шифром DES: дифференциальный и линейный криптоанализ. Полное рассмотрение этих двух проблем невозможно в этой книге. Это приложение дает общее представление и отсылает заинтересованных читателей к возможностям познакомиться с проблемой поближе в соответствующей литературе.

N.1. Дифференциальный криптоанализ

Дифференциальный криптоанализ для DES был изобретен Бихамом (Biham) и Шамиром (Shamir). В этом криптоанализе злоумышленник концентрируется на атаках с выборкой исходного текста. Анализ использует разность в прохождении различных входных сигналов через устройство или программу шифрации. Термин разность здесь применяется, чтобы рассмотреть с помощью операции ИСКЛЮЧАЮЩЕЕ ИЛИ несовпадение двух различных входных сообщений (исходные тексты). Другими словами, злоумышленник анализирует, как $$P \oplus P'$$ различаются при обработке в каждом раунде.

Вероятностные отношения

Идея относительно дифференциального криптоанализа базируется на вероятностных отношениях между входными разностями и разностями выхода. Два отношения представляют конкретный интерес в анализе: дифференциальный профайл и характеристика раунда, как это показано на рис. N.1.

(рис N.1) Дифференциальный профайл и характеристика раунда в DES

Дифференциальный профайл

Дифференциальный профайл (он же профайл ИСКЛЮЧАЮЩЕЕ ИЛИ) показывает вероятностное отношение между входными разностями и разностями выхода S-блока. Подобные профайлы могут быть созданы для каждого из восьми S-блоков в DES.

Характеристика раунда

Характеристика раунда подобна дифференциальному профайлу, но вычисляется для целого раунда. Она показывает вероятность, с которой одна входная разность создала бы разность определенного выхода. Обратите внимание, что характеристика одна и та же для каждого раунда, потому что любое отношение, которое включает разности, не зависит от ключей раунда. Рисунок N.2 показывает четыре различные характеристики раунда.

(рис N.2) Некоторые характеристики раунда для дифференциального криптоанализа

Хотя существует много характеристик для раунда, рисунок N.2 показывает только четыре из них. В каждой характеристике мы разделили входные разности и разности выхода в левые и правые секции. Каждая левая или правая разность состоят из 32 битов или восьми шестнадцатеричных цифр. Все эти характеристики могут быть найдены использующими программами, которые могут найти отношение входа-выхода в раунде DES. Рисунок N.2а показывает, что входная разность (x, 00000000₁₆) дает на выходе разность (x, 00000000₁₆) с вероятностью 1. Рисунок N.2б показывает ту же самую характеристику, как рисунок N.2а, за исключением того, что левые и правые вход и выход поменялись местами; вероятность изменится чрезвычайно. Рисунок N.2в показывает, что входная разность (40080000₁₆, 04000000₁₆) дает разность выхода (00000000₁₆, 0400000₁₆) с вероятностью 1/4. Наконец, рисунок N.2г показывает, что входная разность (00000000₁₆, 60000000₁₆) дает разность выхода (00808200₁₆ 6000000₁₆) с вероятностью 14/64.

Трехраундная характеристика

После создания и хранения однораундных характеристик анализатор может комбинировать различное количество раундов, чтобы создать множественную характеристику раунда. Рисунок N.3 показывает случай трехраундной DES. На рис. N.3, мы использовали три смесителя и только два устройства замены, потому что последний раунд не нуждается ни в каком устройстве замены. Характеристики, показанные в смесителях первых и третьих раундов, те же самые, как и на рисунке N.2b. Характеристика смесителя во втором раунде - та же самая, что и на рис. N.2a. Очень интересно отметить, что точки, в этом конкретном случае, разности входа и выхода - те же самые ( $$\Delta L_{3}=\Delta L_{0}$$ и $$\Delta R_{3} = \Delta R_{0}$$ ).

(рис N.3) Трехраундная характеристика

Шестнадцатираундная характеристика

Для шифра с шестнадцатью раундами можно скомпилировать много различных характеристик. Рисунок N.4 показывает пример. На этом рисунке шифр DES состоит из восьми секций с двумя раундами. Каждая секция использует характеристики а и б на рис. N.2. Ясно, что если последние раунды не имеют устройства замены, вход (x, 0) создает выход (0, x) с вероятностью (1/234)⁸.

(рис N.4) Шестнадцатираундная характеристика для дифференциального криптоанализа

Атака

Для примера предположим, что Ева использует характеристику по рисунку N.4, чтобы напасть на DES с шестнадцатью раундами. Ева каким-то способом провоцирует Алису, чтобы зашифровать много исходных текстов в форме (x, 0), в которой левая половина - x (различные значения) и правая половина - 0. Ева затем сохраняет все зашифрованные тексты, полученные от Алисы, в форме (0, x). Обратите внимание, что 0 здесь означает 00000000₁₆.

Нахождение ключа шифра

Окончательная цель злоумышленника в дифференциальном криптоанализе состоит в том, чтобы найти ключ шифра. Для этого нужно найти ключи каждого раунда от основания до вершины (K₁₆K₁).

Нахождение последних ключей раунда

Если злоумышленник имеет достаточно много пар исходного текста / зашифрованного текста (каждый с различными значениями. x ), он может использовать отношения в последнем раунде, 0 = f(K₁₆,x) и найти некоторые из битов в K₁₆. Это можно сделать, выбирая самые вероятные значения.

Нахождение других ключей раунда

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

Безопасность

Известно, что необходимы 2⁴⁷ выборки пар исходного текста / зашифрованного текста, чтобы напасть на DES с 16 раундами. Найти такое огромное число выбранных пар чрезвычайно трудно в ситуациях реальной жизни. Это означает, что DES неуязвимы для этого типа атаки.

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

Линейный криптоанализ для DES был разработан Матцуи. Это - атака знания исходного текста. Анализ использует распространение конкретного набора битов через устройство шифрования.

Отношения линейности

Линейный криптоанализ основан на отношениях линейности. В этом типе криптоанализа представляют интерес два набора отношений: линейные профайлы и характеристики раунда, как показано на рис. N.5.

(рис N.5) Линейный профайл и характеристика раунда в DES

Линейный профайл

Линейный профайл показывает уровень линейности между входом и выходом S-блока. Мы видели, что в S-блоке каждый бит выхода - функция всех входных битов. Желательное свойство в S-блоке достигнуто, если каждый бит выхода - нелинейная функция всех входных битов. К сожалению, эта идеальная ситуация не существует в DES; некоторые биты выхода - линейная функция некоторых комбинаций входных битов. Другими словами, можно найти, что некоторые комбинации битов входа-выхода могут быть отображены между собой, используя линейную функцию. Линейный профайл показывает уровень линейности (или нелинейности) между входом и выходом. Криптоанализ может создать восемь различных таблиц, по одной для каждого S-блока, в которых первый столбец показывает возможные комбинации входов по шесть бит, 00₁₆ до 3F₁₆. Первая строка показывает возможные комбинации выходов по четыре бита, 0₁₆ до F₁₆. Входы показывают уровень линейности (или нелинейности) данного проекта. Мы не можем углубляться в детали того, как измеряется уровень линейности, но входы с высокого уровня из линейности интересны для криптоанализа.