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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

История[править | править вики-текст]

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

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

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

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

Схема взлома DES[править | править вики-текст]

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

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

Анализ одного раунда[править | править вики-текст]

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

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

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

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

Характеристики[править | править вики-текст]

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

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

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

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

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

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

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

Отношение сигнал/шум[править | править вики-текст]

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

Отношение числа правильных пар к среднему значению счетчика будем называть отношением сигнал/шум для нашей расчетной схемы и будем обозначать S/N

Чтобы выделить правильный ключ, необходима характеристика с достаточной вероятностью и достаточное количество пар, чтобы гарантировать наличие среди них правильных пар. Число необходимых пар определяется вероятностью характеристики, числом бит ключа, которые мы хотим определить, и уровнем идентификации ошибочных пар (они не вносят вклада в счетчики, так как отбрасываются раньше). Пусть мы ищем k бит ключа, тогда у нас 2^{k} счетчиков. Если m — число используемых пар, \alpha — средняя добавка к счетчикам для одной пары, \beta — отношение пар, которые вносят вклад в счетчики ко всем парам (в том числе отброшенным). Среднее значение счетчика равно \frac{m \cdot \alpha \cdot \beta}{2^{k}}. Если p — вероятность характеристики, то число правильных пар равно m \cdot p. Тогда имеем следующее соотношение для отношения сигнал/шум: S/N = \frac{m \cdot p}{m \cdot \alpha \cdot \beta / 2^{k}} = \frac{2^{k} \cdot p}{\alpha \cdot \beta}

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

Эффективность взлома[править | править вики-текст]

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

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

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

Сравнение с другими методами[править | править вики-текст]

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

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

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

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

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

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

Недостатки метода[править | править вики-текст]

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

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

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Coppersmith, Don (May 1994). «The Data Encryption Standard (DES) and its strength against attacks» (PDF). IBM Journal of Research and Development 38 (3): 243. DOI:10.1147/rd.383.0243. (subscription required)
  2. Biham E., Shamir A. Differential cryptoanalysis of DES-like cryptosystems (англ.). — 1990. — С. 7.

Литература[править | править вики-текст]