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

Дифференциальный криптоанализ — метод криптоанализа симметричных блочных шифров (и других криптографических примитивов, в частности, хеш-функций и поточных шифров).

Дифференциальный криптоанализ основан на изучении преобразования разностей между шифруемыми значениями на различных раундах шифрования. В качестве разности, как правило, применяется операция побитового суммирования по модулю 2, хотя существуют атаки и с вычислением разности по модулю [math]\displaystyle{ 2^{32} }[/math]. Является статистической атакой. Применим для взлома DES, FEAL и некоторых других шифров, как правило, разработанных ранее начала 90-х. Количество раундов современных шифров (AES, Camellia и др.) рассчитывалось с учётом обеспечения стойкости, в том числе и к дифференциальному криптоанализу.

История

Дифференциальный криптоанализ предложен в 1990 году израильскими специалистами Эли Бихамом и Ади Шамиром для взлома криптосистем, подобных DES. В своей работе они показали, что алгоритм DES оказался довольно устойчивым к данному методу криптоанализа, и любое малейшее изменение структуры алгоритма делает его более уязвимым.

В 1994 году Дон Копперсмит из IBM опубликовал статью, в которой заявил, что метод дифференциального криптоанализа был известен IBM уже в 1974 году, и одной из поставленных целей при разработке DES была защита от этого метода. У IBM были свои секреты. Копперсмит объяснял:

При проектировании использовались преимущества определенных криптоаналитических методов, особенно метода «дифференциального криптоанализа», который не был опубликован в открытой литературе. После дискуссий с АНБ было решено, что раскрытие процесса проектирования раскроет и метод дифференциального криптоанализа, мощь которого может быть использована против многих шифров. Это, в свою очередь, сократило бы преимущество США перед другими странами в области криптографии.

DES оказался криптостойким к дифференциальному криптоанализу, в отличие от некоторых других шифров. Так, например, уязвимым оказался шифр FEAL. Состоящий из 4 раундов FEAL-4 может быть взломан при использовании всего лишь 8 подобранных открытых текстов, и даже 31-раундовый FEAL уязвим для атаки.

Схема взлома DES

Функция Фейстеля

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

Анализ одного раунда

Базовый метод дифференциального криптоанализа — это атака на основе адаптивно подобранных открытых текстов, хотя у него есть расширение для атаки на основе открытых текстов. Для проведения атаки используются пары открытых текстов, связанных определенной разницей. Для DES и DES-подобных систем она определяется как исключающее ИЛИ (XOR). При расшифровке необходимо только значение соответствующих пар шифртекстов.

На схеме изображена функция Фейстеля . Пусть [math]\displaystyle{ X }[/math] и [math]\displaystyle{ X' }[/math] - пара входов, различающихся на [math]\displaystyle{ \Delta X }[/math]. Соответствующие им выходы известны и равны [math]\displaystyle{ Y }[/math] и [math]\displaystyle{ Y' }[/math], разница между ними - [math]\displaystyle{ \Delta Y }[/math]. Также известны перестановка с расширением и [math]\displaystyle{ P }[/math]-блок, поэтому известны [math]\displaystyle{ \Delta A }[/math] и [math]\displaystyle{ \Delta C }[/math]. [math]\displaystyle{ B }[/math] и [math]\displaystyle{ B' }[/math] неизвестны, но мы знаем, что их разность равна [math]\displaystyle{ \Delta A }[/math], т.к. различия [math]\displaystyle{ XOR\ K_{i} }[/math] c [math]\displaystyle{ A }[/math] и [math]\displaystyle{ A' }[/math] нейтрализуются. Единственные нелинейные элементы в схеме — это [math]\displaystyle{ S }[/math]-блоки. Для каждого [math]\displaystyle{ S }[/math]-блока можно хранить таблицу, строки которой — разности на входе [math]\displaystyle{ S }[/math]-блока, столбцы — разности на выходе, а на пересечении — число пар, имеющих данные входную и выходную разности, и где-то хранить сами эти пары.

Вскрытие раундового ключа основано на том факте, что для заданного [math]\displaystyle{ \Delta A }[/math] не все значения [math]\displaystyle{ \Delta C }[/math] равновероятны, а комбинация [math]\displaystyle{ \Delta A }[/math] и [math]\displaystyle{ \Delta C }[/math] позволяет предположить значения [math]\displaystyle{ A\ XOR\ K_{i} }[/math] и [math]\displaystyle{ A'\ XOR\ K_{i} }[/math]. При известных [math]\displaystyle{ A }[/math] и [math]\displaystyle{ A' }[/math] это позволяет определить [math]\displaystyle{ K_{i} }[/math]. За исключением [math]\displaystyle{ \Delta C }[/math] вся необходимая информация для последнего раунда содержится в итоговой паре шифртекстов.

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

Характеристики

Для определения возможных отличий полученных на i-м раунде шифртекстов используются раундовые характеристики.

N-раундовая характеристика представляет собой кортеж [math]\displaystyle{ \Omega \ = \ (\Omega_{P}, \Omega_{\Lambda}, \Omega_{T}) }[/math], составляется из различий открытого текста [math]\displaystyle{ \Omega_{P} }[/math], различий шифртекста [math]\displaystyle{ \Omega_{T} }[/math] и набора [math]\displaystyle{ \Omega_{\Lambda} \ = \ (\Lambda_{1}, \Lambda_{2},\ ...\ , \Lambda_{n}) }[/math] различий промежуточных результатов шифрования для каждого прошедшего раунда.

Характеристике присваивается вероятность, равная вероятности что случайная пара открытых текстов с различием [math]\displaystyle{ \Omega_{P} }[/math] в результате шифрования со случайными ключами имеет раундовые различия и различия шифртекстов, совпадающие с указанными в характеристике. Соответствующая характеристике пара открытых текстов называется «правильной». Не соответствующие характеристике пары открытых текстов зовутся «неправильными».

Простейшая однораундовая характеристика с вероятностью 1

Примем значение разницы текстов на выходе предпоследнего цикла, используемое при определении возможного подключа последнего раунда, [math]\displaystyle{ \Delta A = \Omega_{T} }[/math]. В таком случая «правильная» пара текстов позволяет определить правильный ключ, в то время как «неправильная» пара определяет случайный ключ.

В атаке обычно одновременно используются несколько характеристик. Для экономии памяти обычно используются структуры.

• Квартет — структура из четырёх текстов, которая одновременно содержит в себе по две пары текстов для двух разных характеристик. Позволяет сэкономить 1/2 памяти для открытых текстов.
• Октет — структура из 16 текстов, содержащая 8 пар, по 4 на каждую характеристику. Позволяет сэкономить 2/3 памяти для открытых текстов.

Отношение сигнал/шум

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

Для нашей расчётной схемы отношение числа правильных пар S к среднему значению счётчика N будем называть отношением сигнал/шум и будем обозначать [math]\displaystyle{ S/N }[/math].

Чтобы найти правильный ключ и гарантировать наличие правильных пар, необходимы:

• характеристика, обладающая достаточной вероятностью;
• достаточное количество пар.

Число необходимых пар определяется:

• вероятностью характеристики;
• числом бит ключа (бит, которые мы хотим определить);
• уровнем идентификации ошибочных пар (пары не вносят вклада в счётчики, так как отбрасываются раньше).

Пусть размер ключа равен k бит, тогда нам понадобится [math]\displaystyle{ 2^k }[/math] счётчиков. Если:

• m — число используемых пар;
• [math]\displaystyle{ \alpha }[/math] — средняя добавка к счётчикам для одной пары;
• [math]\displaystyle{ \beta }[/math] — отношение пар, которые вносят вклад в счётчики ко всем парам (в том числе отброшенным),

то среднее значение счётчика N равно:

[math]\displaystyle{ N = \frac{m \cdot \alpha \cdot \beta}{2^{k}}. }[/math]

Если [math]\displaystyle{ p }[/math] — вероятность характеристики, то число правильных пар S равно:

[math]\displaystyle{ S = m \cdot p. }[/math]

Тогда отношение сигнал/шум равно:

[math]\displaystyle{ S/N = \frac{m \cdot p}{m \cdot \alpha \cdot \beta / 2^{k}} = \frac{2^{k} \cdot p}{\alpha \cdot \beta}. }[/math]

Заметим, что для нашей расчётной схемы отношение сигнал/шум не зависит от общего числа пар. Число необходимых правильных пар — в общем, функция отношения сигнал/шум. Экспериментально было установлено, что если S/N=1—2, необходимо 20—40 вхождений правильных пар. Если же отношение намного выше, то даже 3—4 правильных пар может быть достаточно. Наконец, когда оно сильно ниже, число необходимых пар огромно.

S/N	Число необходимых пар
меньше 1	Велико
1—2	20—40
больше 2	3—4

Эффективность взлома

С увеличением числа раундов сложность криптоанализа увеличивается, однако остаётся меньше сложности полного перебора при количестве циклов меньше 16.

Зависимость от количества раундов
Число раундов	Трудоёмкость атаки
[math]\displaystyle{ 4 }[/math]	[math]\displaystyle{ 2^{4} }[/math]
[math]\displaystyle{ 6 }[/math]	[math]\displaystyle{ 2^{8} }[/math]
[math]\displaystyle{ 8 }[/math]	[math]\displaystyle{ 2^{16} }[/math]
[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 2^{26} }[/math]
[math]\displaystyle{ 10 }[/math]	[math]\displaystyle{ 2^{35} }[/math]
[math]\displaystyle{ 11 }[/math]	[math]\displaystyle{ 2^{36} }[/math]
[math]\displaystyle{ 12 }[/math]	[math]\displaystyle{ 2^{43} }[/math]
[math]\displaystyle{ 13 }[/math]	[math]\displaystyle{ 2^{44} }[/math]
[math]\displaystyle{ 14 }[/math]	[math]\displaystyle{ 2^{51} }[/math]
[math]\displaystyle{ 15 }[/math]	[math]\displaystyle{ 2^{52} }[/math]
[math]\displaystyle{ 16 }[/math]	[math]\displaystyle{ 2^{58} }[/math]

Устройство S-блоков также значительно влияет на эффективность дифференциального криптоанализа. S-блоки DES, в частности, оптимизированы для устойчивости к атаке.

Сравнение с другими методами

См. Известные атаки на DES

Дифференциальный криптоанализ и DES-подобные системы

В то время как полный 16-и раундовый DES оказался изначально спроектированным устойчивым к дифференциальному криптоанализу, атака показала себя успешной против широкой группы DES-подобных шифров.

• Lucifer, укороченный до восьми раундов, взламывается с использованием менее 60 шифртекстов.
• FEAL-8 взламывается с использованием менее 2000 шифртекстов.
• FEAL-4 взламывается с использованием 8-и шифртекстов и одного открытого текста.
• FEAL-N и FEAL-NX могут быть взломаны при количестве раундов [math]\displaystyle{ N \leq 31 }[/math].

Дифференциальный криптоанализ также применим против хеш-функций.

После публикации работ по дифференциальному криптоанализу в начале 1990-х годов последующие шифры проектировались устойчивыми к этой атаке.

Недостатки метода

Метод дифференциального криптоанализа в большей степени является теоретическим достижением. Его применение на практике ограничено высокими требованиями к времени и объёму данных.

Являясь, в первую очередь, методом для вскрытия с выбранным открытым текстом, дифференциальный криптоанализ трудно реализуем на практике. Он может быть использован для вскрытия с известным открытым текстом, но в случае полного 16-этапного DES это делает его даже менее эффективным, чем вскрытие грубой силой.

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

См. также

• Линейный криптоанализ
• Атака методом бумеранга
• Атака на связанных ключах

Литература

• Брюс Шнайер. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си.
• Панасенко, С. Современные методы вскрытия алгоритмов шифрования, часть 3 // Chief Information Officer - 2006.

Архивная копия от 15 января 2010 на Wayback Machine

• Biham E., Shamir A. Differential cryptoanalysis of the Data Encription Standart.
• Biham E., Shamir A. Differential cryptoanalysis of DES-like cryptosystems (англ.). — 1990.