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

где q = 1 или q = 2 определяется возможностью реализации NR-атаки с разным количеством циклов. Значением характеризуют сложность выполнения наиболее  ресурсоёмкого этапа дифференциального криптоанализа – подбора правильной пары открытых текстов. Правильная пара позволяет предположить значения бит подключа последнего цикла. Конечно, остается воспользоваться еще немалым количеством дополнительных приемов, чтобы восстановить все биты подключа (и ключа в целом).

 

2. Нова методология ускоренного криптоанализа, разрабатываемая на кафедре БИТ

 

На кафедре Безопасности информационных технологий Харьковского национального университета радиоэлектроники в последние годы разрабатывается  новая методология оценки стойкости блочных симметричных шифров к атакам дифференциального и линейного крипто анализа [ 9] .

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

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

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

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

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

Утверждение 1. Для каждого блочного симметричного шифра (из числа известных итеративных БСШ) существует определенное число циклов, после которого шифр приобретает свойства случайной подстановки. Дальнейшее наращивание числа циклов не влияет на итоговые дифференциальные свойства шифра. Это значение является одним и тем же для всех шифрующих преобразований с одинаковым размером битового входа.

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

То есть согласно методу оценки качества криптографических преобразований на основе определения количества циклов, которые нужны БСШ для получения свойств случайной подстановки можно сравнивать БСШ с одинаковым размером битового входа при выполнении экспертизы и проверке отдельных решений. Для этого нужно построить уменьшенные модели сравниваемых БСШ и поставить эксперимент для определения количества циклов, которые нужны каждому кандидату для достижения свойств случайной подстановки.

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

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

В новой методологии предлагается для оценки устойчивости БСШ к атакам дифференциального криптоанализа пользоваться не (максимумом средней дифференциальной вероятности) для некоторого фиксированного перехода входной разности в выхдную разность , а средним (по ключам) значением максимумов дифференциальных вероятностей (AMDP) ключезависимой функции . Выражения для средних вероятностей ADP и MADP и ключезависимой функции по n-битным входам x и n-битным выходам y (x , y, ), которые используются во многих публикациях по обоснованию показателей устойчивости блочных шифров приведены ниже. Также ниже дано определение предложенного показателя (определение 3).

Определение 1. Среднее значение дифференциальной вероятности (ADP) функции есть

                                                                 _(2.11)

Определение 2. Максимум среднего значения дифференциальной вероятности (MADP) функции есть

                                                                    (2.12)

Определение 3 (AMDP). Среднее (по множеству из ключей) значение максимальных дифференциальных вероятностей ключезависимой функции

 есть

                                      (2.10)

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

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

Очевидно неравенство:

                                                      MADP <AMDP.

Помимо большей адекватности оценок, которые формируются (значение оценок совпадают с соответствующими дифференциальными показателями случайных подстановок и характеризуют максимально достижимые значения дифференциальных вероятностей), в последнем случае обеспечиваются и значительные вычислительные преимущества (нет необходимости запоминать полностью все таблицы, а достаточно только определять и запомнить их максимальные значения). При этом обеспечивается уменьшение объема необходимой для вычислений памяти 2²ⁿ раз, где n - размер битового входа в шифр.

В новой методологии [10,11] рассматривались дифференциальные свойства случайных подстановок и было доказано утверждение.

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

                        ,        (2.13)

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

                                                     (2.14)

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

                                          (2.15)

Эта формула достаточно сложна для вычислений.

В методологии была предложена упрощенная формула для вычисления максимального значения дифференциальной вероятности, полученная на основе простого подбора. Она имеет вид:

                                                                                         (2.16)

Можно выполнять анализ значений переходов разниц не для всей дифференциальной таблицы шифра, а только для ее «пропорционально уменьшенной» части. Речь идет о рассмотрении, например, дифференциальной таблицы, получается при использовании шифра для  шифрования не n-битных блоков данных, а блоков, уменьшенных по размеру  в 2-4 раза.

В таких экспериментах  большой шифр используется как малый  для шифрования блоков данных уменьшенной  длины (зашифрованные блоки данных тоже усекаются до необходимого размера), при этом сохраняются все преобразования и внутренние связи большого шифра. Важным при таком подходе является то, что появляется возможность применить весь наработанный аппарат изучение показателей случайности малых версий шифров для изучения показателей случайности больших шифров.

В процессе экспериментов  необходимо осуществить шифрование 16-битовых блоков данных на случайно выбранных ключах. Полученные результаты усреднить по множеству ключей. Нужно  определиться с каждого цикла  шифрования шифр приходит к устойчивому  значение максимума полного дифференциала  повторяет соответствующее значение случайной подстановки степени 2¹⁶. Также нужно определиться зависит ли это асимптотическое значение от используемых ключей шифрование.

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

 

3. Описание БСШ DES

 

   Стандарт шифрования  данных DES (Data Encryption Standard), который ANSI называет Алгоритмом шифро-вания  данных DEA (Data Encryption Algorithm), а ISO - DEA-1, за 20 лет стал мировым стандартом. Хотя на нем и появился налет  старости, он весьма прилично  выдержал годы криптоанализа  и все еще остается безопасным  по отношению ко всем атакам.

DES представляет собой  блочный шифр, он шифрует данные 64-битовыми блоками. С одного  конца алго-ритма вводится 64-битовый  блок открытого текста, а с  другого конца выходит 64-битовый  блок шифротекста. DES является симметричным  алгоритмом: для шифрования и  дешифрирования используются одинаковые  алго-ритм и ключ (за исключением  небольших различий в использовании  ключа).

Длина ключа равна 56 битам. (Ключ обычно представляется 64-битовым  числом, но каждый восьмой бит используется для проверки четности и игнорируется. Биты четности являются наименьшими  значащими бита-ми байтов ключа.) На простейшем уровне алгоритм не представляет ничего большего, чем комбинация двух основных методов шифрования: смещения и диффузии. Фундаментальным строительным блоком DES является применение к тексту единичной комбинации этих методов (подстановка, а за ней - перестановка), зависящей от ключа.DES состоит из 16 этапов, одинаковая комбинация методов  применяется к открытому тексту 16 раз (см.рис.2.1).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

      Рис. 2.1 DES

         Алгоритм использует только стандартную  арифметику 64-битовых чисел и  логические операции, поэтому он  легко реализовывался в аппаратуре  второй половины 70-х. Изобилие  повторений в алгоритме делает  его идеальным для реализации  в специализированной микросхеме. Первоначальные программные реализации  были довольно неуклюжи, но сегодняшние  программы намного лучше.

      DES работает  с 64-битовым блоком открытого  текста. После первоначальной перестановки  блок разбивается на правую  и левую половины длиной по 32 бита. Затем выполняется 16 этапов  одинаковых действий, называе-мых  функцией f, в которых данные объединяются  с ключом. После шестнадцатого  этапа правая и левая поло-вины  объединяются и алгоритм завершается  заключительной перестановкой (обратной  по отношению к перво-начальной).

На каждом этапе (см. Рис. 2.2) биты ключа сдвигаются, и затем  из 56 битов ключа выбираются 48 битов. Правая половина данных увеличивается  до 48 битов с помощью перестановки с расширением, объединяется посредством XOR с 48 битами смещенного и переставленного  ключа, проходит через 8 S-блоков, образуя 32 новых бита, и переставляется снова. Эти четыре операции и выполняются  функцией f. Затем результат функции f объединяется с левой половиной  с помощью другого XOR. В итоге  этих действий появляется новая правая половина, а старая правая половина становится новой левой. Эти действия повторяются 16 раз, образуя 16 эта-пов DES.