Русская Википедия:Дифференциальный криптоанализ
Дифференциальный криптоанализ — метод криптоанализа симметричных блочных шифров (и других криптографических примитивов, в частности, хеш-функций и поточных шифров).
Дифференциальный криптоанализ основан на изучении преобразования разностей между шифруемыми значениями на различных раундах шифрования. В качестве разности, как правило, применяется операция побитового суммирования по модулю 2, хотя существуют атаки и с вычислением разности по модулю <math>2^{32}</math>. Является статистической атакой. Применим для взлома 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). При расшифровке необходимо только значение соответствующих пар шифртекстов.
На схеме изображена функция Фейстеля . Пусть <math>X</math> и <math>X'</math> - пара входов, различающихся на <math>\Delta X</math>. Соответствующие им выходы известны и равны <math>Y</math> и <math>Y'</math>, разница между ними - <math>\Delta Y</math>. Также известны перестановка с расширением и <math>P</math>-блок, поэтому известны <math>\Delta A</math> и <math>\Delta C</math>. <math>B</math> и <math>B'</math> неизвестны, но мы знаем, что их разность равна <math>\Delta A</math>, т.к. различия <math>XOR\ K_{i}</math> c <math>A</math> и <math>A'</math> нейтрализуются. Единственные нелинейные элементы в схеме — это <math>S</math>-блоки. Для каждого <math>S</math>-блока можно хранить таблицу, строки которой — разности на входе <math>S</math>-блока, столбцы — разности на выходе, а на пересечении — число пар, имеющих данные входную и выходную разности, и где-то хранить сами эти пары.
Вскрытие раундового ключа основано на том факте, что для заданного <math>\Delta A</math> не все значения <math>\Delta C</math> равновероятны, а комбинация <math>\Delta A</math> и <math>\Delta C</math> позволяет предположить значения <math>A\ XOR\ K_{i}</math> и <math>A'\ XOR\ K_{i}</math>. При известных <math>A</math> и <math>A'</math> это позволяет определить <math>K_{i}</math>. За исключением <math>\Delta C</math> вся необходимая информация для последнего раунда содержится в итоговой паре шифртекстов.
После определения раундового ключа для последнего цикла становится возможной частичное дешифрование шифртекстов с последующим использованием вышеописанного метода для нахождения всех раундовых ключей.
Характеристики
Для определения возможных отличий полученных на i-м раунде шифртекстов используются раундовые характеристики.
N-раундовая характеристика представляет собой кортеж <math>\Omega \ = \ (\Omega_{P}, \Omega_{\Lambda}, \Omega_{T})</math>, составляется из различий открытого текста <math>\Omega_{P}</math>, различий шифртекста <math>\Omega_{T}</math> и набора <math>\Omega_{\Lambda} \ = \ (\Lambda_{1}, \Lambda_{2},\ ...\ , \Lambda_{n})</math> различий промежуточных результатов шифрования для каждого прошедшего раунда.
Характеристике присваивается вероятность, равная вероятности что случайная пара открытых текстов с различием <math>\Omega_{P}</math> в результате шифрования со случайными ключами имеет раундовые различия и различия шифртекстов, совпадающие с указанными в характеристике. Соответствующая характеристике пара открытых текстов называется «правильной». Не соответствующие характеристике пары открытых текстов зовутся «неправильными».
Примем значение разницы текстов на выходе предпоследнего цикла, используемое при определении возможного подключа последнего раунда, <math>\Delta A = \Omega_{T}</math>. В таком случая «правильная» пара текстов позволяет определить правильный ключ, в то время как «неправильная» пара определяет случайный ключ.
В атаке обычно одновременно используются несколько характеристик. Для экономии памяти обычно используются структуры.
- Квартет — структура из четырёх текстов, которая одновременно содержит в себе по две пары текстов для двух разных характеристик. Позволяет сэкономить 1/2 памяти для открытых текстов.
- Октет — структура из 16 текстов, содержащая 8 пар, по 4 на каждую характеристику. Позволяет сэкономить 2/3 памяти для открытых текстов.
Отношение сигнал/шум
Для всех вариантов ключа можно завести счётчики, и если какая-либо пара предлагает данный вариант в качестве верного ключа, будем увеличивать соответствующий счётчик. Ключ, которому соответствует самый большой счётчик, с высокой вероятностью является верным.
Для нашей расчётной схемы отношение числа правильных пар S к среднему значению счётчика N будем называть отношением сигнал/шум и будем обозначать <math>S/N</math>.
Чтобы найти правильный ключ и гарантировать наличие правильных пар, необходимы:
- характеристика, обладающая достаточной вероятностью;
- достаточное количество пар.
Число необходимых пар определяется:
- вероятностью характеристики;
- числом бит ключа (бит, которые мы хотим определить);
- уровнем идентификации ошибочных пар (пары не вносят вклада в счётчики, так как отбрасываются раньше).
Пусть размер ключа равен k бит, тогда нам понадобится <math>2^k</math> счётчиков. Если:
- m — число используемых пар;
- <math>\alpha</math> — средняя добавка к счётчикам для одной пары;
- <math>\beta</math> — отношение пар, которые вносят вклад в счётчики ко всем парам (в том числе отброшенным),
то среднее значение счётчика N равно:
- <math>N = \frac{m \cdot \alpha \cdot \beta}{2^{k}}.</math>
Если <math>p</math> — вероятность характеристики, то число правильных пар S равно:
- <math>S = m \cdot p.</math>
Тогда отношение сигнал/шум равно:
- <math>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>4</math> | <math>2^{4}</math> |
<math>6</math> | <math>2^{8}</math> |
<math>8</math> | <math>2^{16}</math> |
<math>9</math> | <math>2^{26}</math> |
<math>10</math> | <math>2^{35}</math> |
<math>11</math> | <math>2^{36}</math> |
<math>12</math> | <math>2^{43}</math> |
<math>13</math> | <math>2^{44}</math> |
<math>14</math> | <math>2^{51}</math> |
<math>15</math> | <math>2^{52}</math> |
<math>16</math> | <math>2^{58}</math> |
Устройство S-блоков также значительно влияет на эффективность дифференциального криптоанализа. S-блоки DES, в частности, оптимизированы для устойчивости к атаке.
Сравнение с другими методами
Дифференциальный криптоанализ и DES-подобные системы
В то время как полный 16-и раундовый DES оказался изначально спроектированным устойчивым к дифференциальному криптоанализу, атака показала себя успешной против широкой группы DES-подобных шифров[2].
- Lucifer, укороченный до восьми раундов, взламывается с использованием менее 60 шифртекстов.
- FEAL-8 взламывается с использованием менее 2000 шифртекстов.
- FEAL-4 взламывается с использованием 8-и шифртекстов и одного открытого текста.
- FEAL-N и FEAL-NX могут быть взломаны при количестве раундов <math>N \leq 31</math>.
Дифференциальный криптоанализ также применим против хеш-функций.
После публикации работ по дифференциальному криптоанализу в начале 1990-х годов последующие шифры проектировались устойчивыми к этой атаке.
Недостатки метода
Метод дифференциального криптоанализа в большей степени является теоретическим достижением. Его применение на практике ограничено высокими требованиями к времени и объёму данных.
Являясь, в первую очередь, методом для вскрытия с выбранным открытым текстом, дифференциальный криптоанализ трудно реализуем на практике. Он может быть использован для вскрытия с известным открытым текстом, но в случае полного 16-этапного DES это делает его даже менее эффективным, чем вскрытие грубой силой.
Метод требует большого объема памяти для хранения возможных ключей. Эффективность метода также сильно зависит от структуры S-блоков взламываемого алгоритма.
См. также
Примечания
Литература
- ↑ Шаблон:Статья (subscription required)
- ↑ Шаблон:Статья