15.04.2022 16:15
DenisSivtsev 0 1500 Источник

Итак, как уже говорилось в предыдущей статье, идея ДК заключается в последовательном сравнении пар открытый/закрытый текст в результате их прохождения через алгоритмы шифрования. Учитывая, что вся информация представляется в двоичном виде, под разностью подразумевается сумма двух последовательностей по модулю два (побитовый XOR). В самом начале анализа алгоритма принято отбрасывать начальную и конечную перестановки (P- блоки), так как они линейны. Рассмотрим один раунд шифрования DES:

Рисунок 1 – Дифференциальный криптоанализ одного раунда шифрования DES
Рисунок 1 – Дифференциальный криптоанализ одного раунда шифрования DES

Введем следующие обозначения. Пусть нам будет задана входная пара x_1и x_2, имеющие разность \Delta X, а так же пара выходов y_1и y_2с разностью \Delta Y. Так как расширяющая перестановкаE с блокомP известны, мы можем посчитать разность на выходе после нее и записать как \Delta A. Эта разность после прохождения через S даст \Delta C, которая после перестановки даст \Delta Y. Остаётся вопрос о подключе. После выхода из сумматора XOR разность \Delta Bбудет равна \Delta A, потому что подключ будет складываться с самим собой. Иными словами:

E(x_1 \bigoplus k_i)\bigoplus E(x_2 \bigoplus k_i) = E(x_1)\bigoplus E(x_2)

Таким образом, подключ не влияет на конечную разность. Можно доказать, что соответствия между \Delta Aи \Delta Cносят не равновероятный характер в силу особенностей строения S - блоков. Знать соответствие между этими двумя значениями крайне важно, так как благодаря этому можно восстановить раундовый подключ. Как уже говорилось выше, длина раундового подключа равна 48 бит, однако, зная алгоритм развёртки ключа, можно восстановить целый 56 – битный ключ методом полного перебора, используя всего 2^{8}комбинаций. Метод ДК позволяет вскрывать подключ K_{16}. Так как наблюдается несходство различных пар \Delta Aи \Delta C, вероятность появления того или иного шифртекста также не равновероятная. В следующем пункте мы сформулируем алгоритм нахождения статистики и построим таблицы для каждого S - блока замены.

Если при определенном количестве пар у нас выявляется наибольшее количество совпадений, то в этом случае подключ подобран верно. В таком случае дана пара, которая соответствует разностям \Delta Aи \Delta C, называется правильной парой. Для того, чтобы отыскать нужный подключ, необходимо собрать как можно большее количество правильных пар. Далее, правильный подключ будет появляться чаще остальных.

Рисунок 2 – Однораундовая характеристика DES
Рисунок 2 – Однораундовая характеристика DES

Именно в этих операциях и заключается метод ДК. В одной из работ А. Шамира показано как, зная характеристику одного раунда шифрования, построить характеристику для нескольких раундов. На рисунке 2.7 изображена характеристика одного раунда шифрования. Входное значение разбито на две части P_L и P_R, причем, правая часть равна нулю. Это сделано с той целью, чтобы на выходе функции Fбыло нулевое значение. Это означает, что на выходе мы всегда получим эту же разность.

Если привести пример ненулевой входной разности, то он представлен на рисунке 3

Рисунок 3 – Однораундовая характеристика DES с ненулевой разностью
Рисунок 3 – Однораундовая характеристика DES с ненулевой разностью

Здесь в качестве входной разности берется значение L^{'}.04000000_h, где символ .означает конкатенацию строк. Она подобрана таким образом, чтобы на выходе из раундовой функции было значение 40080000_h. Соответственно, полученный шифртекст будет иметь значение L^{'}\bigoplus 40080000_h . 04000000_h. Причины подбора тех или иных цифр самим Шамиром не были объяснены.

Далее рассмотрим пример с несколькими раундами. На рисунке 2.9 приведена схема алгоритма DES с тремя раундами.

Рисунок 4 – Трехраундовый алгоритм DES
Рисунок 4 – Трехраундовый алгоритм DES

Будем исходить из того, что правая часть входной разности P _Rнулевая, так же как и в однораундовой характеристике. Это соответствует a=0 на рисунке 2. В таком случае Разность A также всегда будет нулевой, и на вход функции F второго раунда поступит разность P_L. На выходе мы будем иметь шифртекст P_L\bigoplus C.F_2(P_L). По значениям P_Lи C_Lнетрудно определить биты подключа последнего раунда, а после чего восстановить весь ключ.

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

Рисунок 5 – Трехраундовая характеристика алгоритма DES
Рисунок 5 – Трехраундовая характеристика алгоритма DES

Для того, чтобы провести атаку на полный 16 – раундовый DES Шамир предложил использовать двухраундовую характеристику и использовать такой дифференциал, который при прохождении через функцию F давал нулевую разность. Подобная структура отображена на рисунке 6. В качестве примера можем рассмотреть случай, когда входная разность равна 19600000_h. Что же будет происходить в функции F? В таком случае в каждом нечетном раунде на её вход будет поступать нулевая разность, что на выходе также даст нулевой результат. В каждом же четном раунде в раундовую функцию будет поступать результат сложения прежней левой части и выходной нулевой разности в нечетном раунде. В данном случае это 19600000_h. На вход первых трех S – блоков поступит 1_h, 9_hи 6_h. соответственно. На остальные S – блоки поступят нули. На выходе от разности 1_h, что равно 000011_2мы получим нули с вероятностью 14/64. Вероятность того, что на выходе второго S – блока будет нулевая разность составляет 8/64, а вероятность того, что на выходе третьего S – блока будет нулевая разность составляет 10/64.

Рисунок 6 – Двухраундовая характеристика алгоритма DES
Рисунок 6 – Двухраундовая характеристика алгоритма DES

Нетрудно посчитать, что суммарная вероятность получения нулевой разности по трем S – блокам составляет:P=(14/64)*(8/64)*(10/64)=1/2^{7.87}

Для анализа 16 – раундового DES было предложено использовать подобную характеристику 6 раз, - со 2- го по 13-ый раунды. В таком случае на вход 14- го раунда поступит нулевая разность. Так как нам известна выходная разность 14-го и 16-го раунда, мы можем определить разность 15-г раунда. Благодаря статистическим данным нам может стать известна разность после прохождения через F – функцию 16-го раунда. Последние три раунда всегда будут выполняться со стопроцентной вероятностью. Вероятность же выполнения шести двухраундовых характеристик равна:

p=(1/2^{7.87})^{6}=1/2^{47.22}

Следующий рисунок наглядно демонстрирует применение анализа к полному алгоритму DES

Рисунок 7 –Характеристика полного алгоритма DES
Рисунок 7 –Характеристика полного алгоритма DES

Учитывая, что правая часть входной разности равна 19600000_h, то всего существует 2^{12}возможных вариантов для её получения. Левая входная разность может принимать практически любые значения.

Для того чтобы начать искать подключ, необходимо собрать статистические данные о криптографических примитивах, входящих в исследуемый алгоритм шифрования. В данном случае, это будут S – блоки. Именно от них зависит стойкость шифра и степень лавинного эффекта на каждом раунде. В DES каждый S – блок принимает на вход 6 битов, а на выходе выдает 4. Ввиду подобной несбалансированности длина подключа изначально не соответствует размеру блока данных, с которым будет складываться. Для того, чтобы это обеспечить, используют E – блок, который расширяет подключ до 48 бит (по 6 бит на каждый из 8-ми S – блоков).

Итак, имеется необходимость построить таблицы соответствия входной и выходной разностей, – \Delta Aи \Delta Cсоответственно. Каждая разность \Delta Aможет иметь 64 различных значений. К примеру, при \Delta A=111010_2это может быть сумма 001011_2и 110001_2или же 101001_2и 010011_2и так далее. Теперь, если мы каждое из этих значений подвергнем преобразованию через первый S – блок, то увидим, что значению 001011_2соответствует 0010_2, значению 110001_2, - 0101_2. Это означает, что разности \Delta A=111010_2в одном из случаев соответствует \Delta C=0010_2 \bigoplus 0101_2=0111_2.

Теперь можно сформулировать алгоритм анализа S – блоков, который можно будет применить не только к DES, но и к любому другому алгоритму шифрования:

  1. Возьмем дифференциал X. Подберем два таких открытых текста, для которых x_1 \bigoplus x_2=X

  2. Каждое значение прогоняем через анализируемый S–блок.

  3. Затем складываем между собой получившиеся значения.

  4. Далее подбираем другое значение x_1и x_2, которые так же в сумме дают исходный дифференциал и возвращаемся к пунктам 2 и 3.

  5. Так продолжаем 2^nраз, где n– разрядность входа S–блока.

  6. После подсчитываем число похожих выходных разностей.

  7. Берём следующий дифференциал и так 2^nраз.

Таблица 1 – Пример статистических данных для первого S–блока алгоритма DES
Таблица 1 – Пример статистических данных для первого S–блока алгоритма DES

На основе полученных таблиц мы можем сделать следующие выводы. Во-первых, сумма всевозможных значений разности \Delta C всегда равна 64. Для того, чтобы посчитать вероятность появления того или иного значения при заданных \Delta Aи \Delta Cнеобходимо поделить частоту появления на 64. Из таблиц видно, что максимально возможная вероятность появления \Delta Cравна 1/4. Также стоит обратить внимание на то, что все значения четные. Это объясняется тем, что каждому дифференциалу соответствует по две пары x_1 \bigoplus x_2и x_2 \bigoplus x_1.

Перво-наперво, определяем на какие S – блоки какие значения отправятся. Для этого заданный дифференциал подвергается  E – преобразованию. После этого становится очевидно, что только на вход второго S – блока поступит ненулевое значение, в то время как на остальные поступят нули. Далее, на основе полученных таблиц мы определяем, что дифференциалу \Delta A =001000_2с наибольшей вероятностью соответствует разность 1010_2. После этого полученный результат проходит через P – преобразование, что в итоге дает 40080000_h. Если в изначальной входной разности левая часть будет равна этому значению, то на вход второго раунда поступит нулевая разность.

Теперь рассмотрим другую разность, которая представлена на рисунке 5. Здесь точно также, после E – преобразования на все S – блоки, кроме первого, поступят нули. На вход первого S – блока поступит дифференциал \Delta A=001100_2, которому  соответствует разность 1110_2(с вероятностью 14/64). После P – преобразования полученная разность будет равна 00808200_h.

Рисунок 8 – Преобразование входной разности в функции F
Рисунок 8 – Преобразование входной разности в функции F

В работах Шамира было предложено использовать на самую наиболее вероятную пару по той причине, что в таком случае пришлось бы затрагивать большое количество S – блоков ввиду E – преобразования. Выбранный дифференциал 19600000_hявляется наиболее компромиссным вариантом, так как затрагивает лишь три блока замены. Нетрудно посчитать, что для этого будет использоваться лишь 2^{12}возможных значений. E – преобразование повторяет крайние биты для каждого из блоков замены, в связи с чем есть необходимость, чтобы два первых и два последних бита всегда были равны нулю. Таких комбинаций всего четыре: 000000_2, 000100_2, 001000_2 и 001100_2. Первая среди них всегда дает нулевое значение, а три остальные никогда не дают его ни для одного блока замены. Выше было установлено, что суммарная вероятность получения нулевой разности по трем S – блокам составляет: P=(14/64)*(8/64)*(10/64) =1/2^{7.87}

Если мы переберем всевозможные значения, которые могут дать нулевую разность с вероятностью большей заданной, то получим 19600000_hи 1B600000_h. Поэтому, для анализа можно использовать эти два дифференциала. На основе этого алгоритма можно осуществить поиск правильных пар, а затем и искомого секретного ключа. Итак, на рисунке 7 представлена схема анализа алгоритма DES для всех 16-ти раундов. Здесь явно определена правая часть, равная 19600000_h, в то время как левая может принимать практически любые значения. Итак, на вход первого блока поступает разность 000011_2. По составленным таблицам определяем, что при этом значении на выходе никогда не получится разность 1001_2и 1111_2. Аналогично, для второго блока замены при значении 110010_2никогда не выйдет разность 1111_2, а для третьего блока, - 0100_2.

Рисунок 9 – Преобразование входной разности 19600000h в функции F
Рисунок 9 – Преобразование входной разности 19600000h в функции F

Так как в правой части значащими битами являются лишь первые 12, то всего может быть 2^{12}вариантов. Из них невозможными являются следующие значения: 1001********_2, 1111********_2, ****1111****_2и ********0100_2. Нетрудно посчитать, что число невозможных дифференциалов составляет 4*2^8=1024. За счет этого мы можем сократить время вычисления на (1024/4096)*100%=25%.

Конечная разность, получающаяся на выходе из раундовой функции, является результатом P – преобразования. В таблице 2 показано, какие из этих битов соответствуют первым 12 битам входной разности. Именно эти биты и должны подвергаться изменению. При этом необходимо помнить, что в левой части могут встречаться не все комбинации. Как уже отмечалось ранее, атака на полный алгоритм DES полностью строится на анализе двух последних раундов. На выходе мы имеем разность C_Lи C_R. Правая часть разности C_Rдолжна получиться в результате прохождения P_Rчерез функцию F. Как мы уже определили, эта разность может быть получена 3072 различными способами. Если же мы получим любую другую разность, - это будет означать, что выбрана пара заведомо не правильная.

Таблица 2 - P – преобразование в функции F
Таблица 2 - P – преобразование в функции F

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

Рисунок 10 – Преобразование входной разности 19600000h в функции F
Рисунок 10 – Преобразование входной разности 19600000h в функции F

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

  1. Для начала побираются правые части открытого текста X_{R1}и X_{R2}таким образом, чтобы X_{R1} \bigoplus X_{R2}=19600000_h.

  2. Подбирается левая часть P_L, на которую накладываются следующие ограничения:

a. 9, 23 и 31 одновременно не равны единице;

b. 2, 13, 18 и 28 биты одновременно не равны единице;

c. 6, 24 и 30 биты одновременно не равны нулю, а 16 бит – единице;

  1. Подбираются два значения X_{L1}и X_{L2}таким образом, чтобы X_{L1}\bigoplus X_{L2}=P_L.

  2. Далее, выбранные пары X_{L1}X_{R1}и X_{L2}X_{R2}подвергаются шифрованию, после чего на выходе получаются пары Y_{L1}Y_{R1}и Y_{L2}Y_{R2}.

  3. Теперь определяется правая часть C_R=Y_{R1}\bigoplus Y_{R2}Если она удовлетворяет критериям пункта 2, то приступаем к следующему шагу. В противном случае подбирается новая пара X_{L1}X_{R1}и X_{L2}X_{R2}

  4. Определяется левая часть C_{L}= Y_{L1}\bigoplus Y_{L2}. Если C_L\bigoplus196000_h удовлетворяет критериям пункта 2, то приступаем к следующему шагу. В противном случае подбирается новая пара X_{L1}X_{R1}и X_{L2}X_{R2}

  5. Далее все пункты повторяются для всех возможных значений X_{L1}и X_{R1}.

Так как вероятность нахождения ключа для полного алгоритма DES составляет 2^{-47.22}то по нижеприведенной мы можем определить минимальное число текстов, проанализировав которые можно с вероятностью 0.5 найти верный ключ:k=\sqrt{2*2^{64}ln2^{-47.22}}=2^{35}.

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

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

Рисунок 11 – Последний раунд шифрования DES
Рисунок 11 – Последний раунд шифрования DES

На рисунке 11 изображен последний раунд шифрования. Очевидно, что мы можем определить входное значение в функцию F, зная C_R. Также, мы можем найти значение выхода из этой функции, посчитав C_L\bigoplus 19600000_h. Применив E – преобразование к входной разности C_Rи обратное P – преобразование к выходной, мы можем найти соответствие между ними. На основе этого сформулируем алгоритм подбора секретного ключа:

  1. Определение разности на выходе из F-функции, сложив C_L\bigoplus19600000_h

  2. Применить обратное P - преобразование C_L\bigoplus19600000_hк этой разности.

  3. Применить E – преобразование к разностям Y_{R1}и Y_{R2}

  4. Сложить полученные значения E(Y_{R1})и E(Y_{R2})с произвольным ключом K_{ij} и подвергнуть S – преобразованию.

  5. Если значения S(Y_{R1})\bigoplus S(Y_{R2})равны P _{inv}(C_R), то счетчик ключа K_{ij}необходимо увеличить на единицу.

  6. Ключи, имеющие максимальное значение счетчиков, и будут наиболее вероятными.

Рисунок 12 – Функция F последнего раунда шифрования DES
Рисунок 12 – Функция F последнего раунда шифрования DES

Проанализировав таким образом все найденные правильные пары текстов, можно определить 48-битный подключ K_{16}после чего восстановить остальные 8 бит методом полного перебора. В таблице 7 показано соответствие между битами основного ключа и 16-го.

Таблица 3 – Соответствие битов основного ключа и подключа 16 раунда
Таблица 3 – Соответствие битов основного ключа и подключа 16 раунда

В предыдущих пунктах было определено, что левая часть входной разности P_L может принимать одно из 3072 значений. Согласно построенной статистике, не все эти значения могут быть равновероятны. Если проанализировать имеющиеся данные в таблицах, то мы увидим, что существует всего 7 значений, вероятность появления которых выше 1/8. Для первого блока это 0000_2и 0100_2, для второго, - 0010_2, 0111_2и 1010_2, а для третьего, - 0000_2и 1001_2. Нетрудно посчитать, что всего существует 12 различных комбинаций этих значений. При их анализе также необходимо учитывать, что после S – преобразования следует перестановка P.

Таблица 4 - Наиболее вероятные значения выходных разностей для первых трех S – блоков DES
Таблица 4 - Наиболее вероятные значения выходных разностей для первых трех S – блоков DES

Если проанализировать все 12 комбинаций этих значений, то получим разности, представленные в таблице 9. Именно среди этих разностей есть большая вероятность нахождения правильных пар.

Таблица 5 – Наиболее вероятные дифференциалы
Таблица 5 – Наиболее вероятные дифференциалы

Используемая литература:

  1. Шнайер Б. Прикладная криптография: Протоколы, алгоритмы, исходные тексты на языке СИ. – М.:ТРИУМФ. – 2002

  2. Heys H. M. A Tutorial on Linear and Differential Cryptanalysis [Электронный ресурс].  http://www.engr.mun.ca/~howard/PAPERS/ldc_tutorial.pdf

  3. D. Coppersmith The Data Encryption Standard (DES) and its strength against attacks VOL. 38 NO. 3 MAY 1994

  4. Бабенко Л. К., Ищукова Е. В. Особенности применения методов дифференциального криптоанализа к симметричным блочным шифрам Вопросы кибербезопасности №1(9) - 2015

  5. Сивцев Д. А. Подбор ключей симметричного алгоритма шифрования DES методом дифференциального криптоанализа. Тенденции инновационных процессов в науке: сборник статей Международной научно – практической конференции – Москва: РИО ЕФИР, 2015. стр. 29

  6. E. Biham, A. Shamir. Differencial Cryptoanalysis of DES-like Cryptosystems. The Weizmann Institute of Science Departament of Apllied Mathematics, July 19, 1990 p. 13

  7. E. Biham, A. Shamir. Differencial Cryptoanalysis of the Full 16-round DES p. 491

  8. Ященко В. В. Введение в криптографию – СПб.: Питер, 2001 стр. 78

Комментарии (0)