Диференційні характеристики шифру DES

1. Шифруется m пар (Pi, ) открытых текстов с Pi+ = .

2. Среди соответствующих  пар (Ci, ) зашифрованных текстов, подсчитывается число N таких, для которых Ci+ = . Затем, пользуются проверкой гипотез для получения решения: если N/m близко к p, то принимается решение, что функция, производящая зашифрованные тексты является примером блочного шифра. Если N/m близко к , то принимается решение, что это были произвольные перестановки.

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

Следуя работе [14], положим, что  является биективным m-битным отображением и пусть  будет множеством всех таких отображений. Пусть  будет значением XOR таблицы (её ячейки) для пары значений разностей входов и выходов , , , подстановки . XOR таблица представляет собой   матрицу , у которой , .

Для m-битной подстановки  π XOR таблица имеет следующую общую  форму:

                         

Будем рассматривать свойства подматрицы , , которая соответствует части XOR таблицы с ненулевыми ячейками.

Рассмотрим задачу определения  вероятности события, заключающегося в том, что значение дифференциальной таблицы случайно взятой подстановки  π  порядка  для перехода  входной разности   в соответствующую выходную разность будет равно 2k (значения ячеек XOR таблицы всегда четное). Как и в [14] эту вероятность обозначим .

В [14] приводится теорема 2.1, определяющая эту вероятность в  следующем виде.

Для любых ненулевых фиксированных  , в предположении, что подстановка π выбрана равновероятно из множества   и ,

 

                                            (3.2)

 

где функция    определяется выражением:

 

                                              (3.3)

 

Выражение  определяет вероятность  того, что в XOR таблице случайно взятой подстановки количество переходов  входной разности в выходную разность  будет равно 2k.

Но тогда становится понятным, что выражение для числа  переходов таблицы дифференциальных разностей подстановки порядка обусловленного типа, - а именно для среднего значения числа ненулевых характеристик , таких, что , может быть получено путем умножения выражения (3.1) на число ячеек подматрицы   таблицы равное , в результате чего получим выражение, позволяющее рассчитывать распределение средних значений максимумов в таблице XOR-разностей случайной подстановки:

         ,   (3.4)

 

где  – среднее значение максимума, которое встретится 2k раз  в таблице XOR-разностей,  размером 2m×2m элементов.

В таблице 3.1  приведены  расчеты, выполненные в соответствии с выражением (3.3). Как видно из данной таблицы, среднее значение максимума для случайной подстановки степени 2¹⁶ находится в пределах 18-20. Такое распределение переходов таблицы XOR-разностей и среднее значение максимума будем считать тем свойством, которым должен обладать БСШ, если он похож на случайную подстановку.

Таблица 2.1 - Закон распределения  переходов таблицы XOR-разностей для  случайной подстановки степени 216

Значение перехода 2k	Количество переходов (расчет)
0	2,6049´109
2	1,30245´109
4	3,25612´108
6	5,42687´107
8	6.78359´106
10	678359
12	56529,9
14	4037,85
16	252,366
18	14,0203
20	0,701016

 

 

 

 

4 РЕЗУЛЬТАТЫ ИССЛЕДОВАНИЙ

 

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

Выберем пару открытых текстов  с фиксированным различием. Можно  выбрать два открытых текста случайным  образом, лишь бы они отличались друг от друга определенным образом, криптоаналитику  даже не нужно знать их значений. (Для DES термин "различие" определяется с помощью XOR. Для других алгоритмов  этот термин может определяться по другому.) Затем, используя различия в получившихся шифротекстах, при-своим  различные вероятности различным  ключам. В процессе дальнейшего анализа  следующих пар шифротек-стов один из ключей станет наиболее вероятным. Это и есть правильный ключ.

Подробности гораздо сложнее. На Рис. 4.5 представлена функция одного этапа DES. Представьте себе пару входов, X и X', с различием DX. Выходы, Y и Y' известны, следовательно, известно и различие между ними DY. Известны и перестановка с расширением, и P-блок, поэтому известны DA и DC. B и B' неизвестны, но их раз-ность DB известна и равна DA. (При рассмотрении различия XOR Ki с A и A' нейтрализуются.) Пока все просто. Фокус вот в чем: для любого заданного DA не все значения DC равновероятны. Комбинация DA и DC позволяет предположить значения битов для A XOR Ki и A' XOR Ki. Так как A и A' известны, это дает нам информацию о Ki.

 

 

 

 

 

 

 

 

 

 

 

 

  

Рис. 4.5 Функция этапа DES

 

Взглянем на последний  этап DES. (При дифференциальном криптоанализе  начальная и заключительная пе-рестановки игнорируются. Они не влияют на вскрытие, только затрудняя объяснение.) Если мы сможем опре-делить K16, то мы получим 48 битов ключа. (Не забывайте, на каждом этапе подключ состоит из 48 битов 56-битового ключа.) Оставшиеся 8 битов  мы можем получить грубым взломом. K16 даст нам дифференциальный криптоанализ.

Определенные различия пар  открытых текстов обладают высокой  вероятностью вызвать определенные раз-личия получаемых шифротекстов. Эти различия называются характеристиками. Характеристики распростра-няются на определенное количество этапов и по существу определяют прохождение этих этапов. Существуют входное различие, различие на каждом этапе и выходное различие - с определенной вероятностью.

Эти характеристики можно  найти, создав таблицу, строки которой  представляют возможные входы XOR (XOR двух различных наборов входных  битов), столбцы - возможные результаты XOR, а элементы - сколько раз конкретный результат XOR встречается для заданного  входа XOR. Такую таблицу можно  сгенерировать для каждого из восьми S-блоков DES.

Например, на Рис. 4.6a показана характеристика одного этапа. Входное  различие слева равно L, оно может  быть произвольным. Входное различие справа равно 0. (У двух входов одинаковая правая половина, поэтому их различие - 0.) Так как на входе функции  этапа нет никаких различий, то нет различий и на выходе функции  эта-па. Следовательно, выходное различие левой части - L Å 0 = L, а выходное различие правой части - 0. Это три-виальная характеристика, она истинна с вероятностью 1.

На Рис. 4.6 б показана менее  очевидная характеристика. Снова, различие L левых частей произвольно. Входное  различие правых частей равно 0x60000000, два  входа отличаются только первым и  третьим битами. С вероятностью 14/64 различие на выходе функции этапа  равно L Å 0x00808200. Это означает, что выходное раз-личие левых половин равно L Å 0x00808200, а выходное различие правых половин - 0x60000000 (с вероятно-стью 14/64)

 

Рис. 4.6 Характеристики DES

Пара открытых текстов, соответствующих  характеристике, называется правильной парой, а пара открытых текстов, несоответствующих  характеристике - неправильной парой. Правильная пара подсказывает правильный ключ этапа (для последнего этапа  характеристики), неправильная пара - случайный  ключ этапа.

Чтобы найти правильный ключ этапа, нужно просто собрать достаточное  количество предположений. Один из подключей  будет встречаться чаще, чем все  остальные. Фактически, правильный подключ  возникнет из всех случайный возможных  подключей.

Итак, дифференциальное основное вскрытие n-этапного DES дает 48-битовый  подключ, используемый на этапе n, а  оставшиеся 8 битов ключа получаются с помощью грубого взлома.

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

Бихам и Шамир предложили свой способ вскрытия. Вместо использования 15-этапной характеристики 16-этапного DES, они использовали 13-этапную характеристику и ряд приемов для получения  последних несколь-ких этапов. Более  короткая характеристика с большей  вероятностью будет работать лучше. Они также исполь-зовали некоторые  сложные математические приемы для  получения вероятных 56-битовых ключей, которые и проверялись немедленно, таким образом устранялась потребность  в счетчиках. Такое вскрытие достигает  успе-ха, как только находится правильная пара. Это позволяет избежать порогового эффекта и получить линейную зависимость  для вероятности успеха. Если у  вас в 1000 раз меньше пар, то вероятность  успеха в 1000 раз мень-ше. Это звучит ужасно, но это намного лучше, чем  порог. Всегда есть некоторая вероятность  немедленной удачи.

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

 

Табл.4.1  Вскрытие с помощью  дифференциального криптоанализа

 

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

Наилучшее вскрытие полного 16-этапного DES требует 247 выбранных открытых текстов. Можно преобра-зовать его  к вскрытию с известным открытым текстом, но для него потребуется  уже 255 известных открытых текстов. При анализе потребуется 237 операций DES.

Дифференциальный криптоанализ эффективен против DES и аналогичных  алгоритмов с постоянными S-блоками. Эффективность вскрытие сильно зависит  от структуры S-блоков, блоки DES по счастливой случайно-сти были оптимизированы против дифференциального криптоанализа. Для всех режимов работы DES - ECB, CBC, CFB и OFB - вскрытие с дифференциальным криптоанализом имеет одинаковую сложность .

Устойчивость DES может быть повышена путем увеличения количества этапов. Дифференциальный крип-тоанализ с выбранным открытым текстом  для DES с 17 или 18 этапами потребует  столько же времени, сколько нужно  для вскрытия грубой силой . При 19 и  более этапах дифференциальный криптоанализ становится невозможным, так как  для него потребуется более, чем 264 выбранных открытых текстов - не забудьте, DES ис-пользует блоки размером 64 битов, поэтому для него существует только 264 возможных открытых текстов.

Нужно отметить ряд важных моментов. Во первых, это вскрытие в  значительной степени теоретическое. Огромные требования к времени и  объему данных, необходимых для выполнения  вскрытия с помощью диф-ференциального криптоанализа, находятся почти  для всех вне пределов досягаемости. Чтобы получить нужные данные для  выполнения такого вскрытия полного DES, вам придется почти три года шифровать  поток выбран-ных шифротекстов 1.5 Мегабит/с. Во вторых, это в первую очередь вскрытие с выбранным  открытым текстом. Оно может быть преобразовано к вскрытию с известным  открытым текстом, но вам придется просмотреть  все пары "открытый текст/шифротекст" в поисках полезных. В случае полного 16-этапного DES это делает вскры-тие  чуть менее эффективным по сравнению  с грубой силой (вскрытие дифференциальным криптоанализом требует 255.1 операций, а вскрытие грубой силой - 255). Таким  образом, правильно реализованный DES сохраняет устойчивость к дифференциальному  криптоанализу

 

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