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

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

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

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

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

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

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

Третье требование выполняется  автоматически при выборе алгоритма  шифрования, режим работы которого рассчитан на длину блока открытого/закрытого  текста не менее 128 бит и длину  ключа не менее 128 бит.

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

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

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

Самой эффективной и самой  сложной является атака полного  перебора, или метод «грубой силы». Она основана на полном переборе всех возможных ключей. Эта атака эффективна при небольшом размере ключа, так как количество возможных  вариантов для ключа длиной n составляет 2n, т.е. для шифров, удовлетворяющих современным требованиям, сложность такой атаки составляет не менее 2^-128 операций шифрования.

Другой тип атаки –  атака методом встречи посередине. Если множество ключей криптоалгоритма  замкнуто относительно композиции, то для любых ключей z_i и z_j можно обнаружить ключ z_k такой, что результат шифрования любого текста последовательно на z_i и z_j будет равен шифртексту на ключе z_k, т.е:

              F(z_j,F(z_i, x))= F(z_k, x).                                                  (1.1)

 

       Можно  воспользоваться этим свойством.  Пусть нужно найти ключ z_{k .} Тогда для нахождения этого ключа, необходимо найти эквивалентную ему пару ключей z_i, z_{j .} Данный метод криптоанализа основан на "парадоксе днея рождения". Известно, что если считать, что дни рождения распределены равномерно, то в группе с 24 человек с достоверностью 0,5 у двух людей дни рождения совпадут. Пусть известен открытый текст x и его шифртекст у. Для текста x строим базу данных, которая содержит случайное множество ключей z| и соответствующих шифртекстов w=F(z|, x), и сортируем ее по шифртекстам w. Потом подбираем случайным образом ключи z|| для расшифрования текстов у и результат расшифрования v=F(z||, y) сравниваем с базой данных. Если текст v окажется равным одному из шифртекстов w, то ключи z| и z|| эквивалентны искомому ключу z. Этот же метод применяется, если множество ключей содержит в себе достаточно большое подмножество, являющееся полугруппой. Данный алгоритм является вероятностным. Тем не менее, существует и детерминированный аналог этого алгоритма. Он имеет название "giant step - baby step" и имеет такую же сложность .

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2 ИССЛЕДОВАНИЕ ДИФФЕРЕНЦИАЛЬНЫХ  СВОЙСТВ БСШ DES

 

2.1 Понятие о дифференциальном  криптоанализе

 

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

        Для  построения атаки подбираются  пары открытых текстов (Р, Р'), имеющие определенное различие, или разность (difference) [8]. Здесь символ "-" обозначает операцию, обратную операции введения в цикловую функцию шифра подключа. В шифре DES такой операцией является побитовая сумма по модулю 2 (англ. XOR). Для обозначения этой операции будем использовать символ « ». Целесообразность применения операции, обратной относительно введения в цикловую функцию шифра подключа, состоит в исключении зависимости значений сформированных разностей от ключевых бит. В частности, для шифра DES при побитовом сложении текстов Р і Р' с ключом по модулю 2, разность Р - Р' (побитовая разность совпадает с побитовой суммой) не изменяется [8]:

                                      (2.1)

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

            Успеху подхода Эли Бихама  и Ади Шамира содействовало  и то, что все преобразования  шифра, кроме S-блоков, оказались линейными (начальная и конечная перестановки I, табличные перестановки E и P, и другие промежуточные операции). Это означает, что такие преобразования не вносят неопределенности в прохождение разностей. Вероятностный характер проведения разностей через циклы шифра представляют нелинейные преобразования, которые осуществляются S-блоками. В результате, изучение свойств S-блоков стало одним из главных этапов осуществления атак дифференциального криптоанализа на DES и другие блочные симметричные шифры.

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

                                                                                                         (2.2)

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

               Уместно напомнить здесь правило  формирования для шифра DES слова ( ) в i-м цикле из слова ( ) в i-1-м цикле [8]:

                                            , .   (2.3)

Соответственно этого  правила для дифференциальных характеристик  шифра DES (Фейстель-подобного шифра) всегда выполняется условие:

                                                ,   (2.4)

или в новых обозначениях:

                                              .    (2.5)

Это означает, что в процессе прохождения разностей через  три соседних цикла  разности на выходах правых полублоков разнесенных (на один цикл) циклов и   должны быть сбалансированными с входной разностью [8]. Вероятность r-цикловой дифференциальной характеристики определяется как произведение вероятностей, которые составляют ее одноцикловые характеристики с помощью формулы:

                                                 .    (2.6)

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

             Пары  , которые определяются разностью на входе j-го цикла, и разностью после цикла j+i, называют i-цикловым дифференциалом, а последовательность значений , где каждое  – значение разности после k-го цикла, называется i-цикловой дифференциальной характеристикой, которая принадлежит i-цикловому дифференциалу . Вероятность i-циклового дифференциала   определяется как сумма вероятностей принадлежащих ему характеристик [8]:

. (2.7)

Поэтому всегда справедливо  такое неравенство:

                                                           .     (2.8)

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

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

Поскольку дифференциальный криптоанализ восстанавливает биты ключа на последнем цикле, то для  успешной атаки на шифр необходим  многоцикловый дифференциал (дифференциальная характеристика), покрывающий почти  все циклы шифра и обладающий вероятностью, которая значительно превышает значение 2^-n (n – размер ключа в битах). Соответственно вышесказанному, критерием защищенности r-циклового шифра от атак дифференциального криптоанализа считается выполнение неравенства:

 

                                            ,     (2.9)