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

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

Дифференциальный криптоанализ основан на изучении преобразования разностей между шифруемыми значениями на различных раундахшифрования.В качестве разности, как правило, применяется операцияпобитового суммирования по модулю 2,хотя существуют атаки и с вычислением разностипо модулю$2^{32}$.Является статистической атакой. Применим для взлома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).При расшифровке необходимо только значение соответствующих пар шифртекстов.

На схеме изображенафункция Фейстеля.Пусть$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будем называть отношениемсигнал/шуми будем обозначать$S/N$.

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

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

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

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

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

• m— число используемых пар;
• $\ Alpha$— средняя добавка к счётчикам для одной пары;
• $\beta$— отношение пар, которые вносят вклад в счётчики ко всем парам (в том числе отброшенным),

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

$N={\frac {m\cdot \ Alpha \cdot \beta }{2^{k}}}.$

Если$p$— вероятность характеристики, то число правильных парSравно:

$S=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правильных пар может быть достаточно. Наконец, когда оно сильно ниже, число необходимых пар огромно.

S/N	Число необходимых пар
меньше 1	Велико
1—2	20—40
больше 2	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-подобных шифров.

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

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

После публикации работ по дифференциальному криптоанализу в начале 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.