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

Данный метод атак на алгоритмы шифрования был изобретен в 1990 г. известными израильскими криптологами Эли Бихамом (Eli Biham) и Эди Шамиром (Adi Shamir) и опубликован в их работе [1]. Однако, не менее известный криптолог Брюс Шнайер в своей книге [4] утверждает, что дифференциальный криптоанализ был открыт существенно раньше, но не появлялся в открытой печати. Тем не менее, именно Бихам и Шамир до сих пор считаются изобретателями дифференциального криптоанализа.

Работа [1] посвящена атаке с помощью дифференциального криптоанализа на алгоритм DES. Перед описанием собственно данного криптоаналитического метода рассмотрим стандарт DES.

DES шифрует информацию блоками по 64 бита с помощью 64-битного ключа шифрования, в котором только 56 бит являются значащими.

Структура алгоритма приведена на рис. 1. Сначала над 64-битным блоком данных выполняется начальная перестановка согласно фиксированной таблице. Все определенные в стандарте DES таблицы не приведены здесь из-за их громоздкости. Подробное описание DES можно найти, например, в [4] или [3].

После начальной перестановки блок данных делится на 2 субблока по 32 бита (начальные значения которых обозначаются A₀ и B₀), над которыми выполняется 16 раундов преобразований:

A_i = B_i-1,

B_i = A_i-1 Å f(B_i-1, K_i),

где A_i и B_i – соответственно, значения левого и правого субблока после выполнения i-го раунда (i = 1…16),

K_i – фрагмент расширенного ключа для i-го раунда (расширение ключа будет описано ниже),

Å – побитовая логическая операция «исключающее или» (XOR),

а функция f(b, k) предусматривает выполнение следующих действий:

1.     Над 32-битным входным значением b выполняется расширяющая перестановка (EP), которая дает 48-битное значение be.

2.     be складывается с ключом раунда K_i операцией XOR; обозначим результат этой операции как bk.

3.     bk разбивается на 8 фрагментов по 6 бит, каждый из которых прогоняется через соответствующую таблицу замен (S1 … S8). Каждая таблица содержит по 4 строки, содержащих по 16 значений от 0 до 15. Входное значение интерпретируется следующим образом: два крайних бита формируют номер строки (от 0 до 3), из которой выбирается число, расположенное в столбце, номер которого соответствует значению четырех остальных бит входа. Например, при двоичном входе 101100 (десятичное число 44) выбирается значение шестой ячейки второй строки.

4.     Полученные в результате замен 4-битные значения объединяются в 32-битный субблок (обозначим его значение как bs), после чего над ними выполняется еще одна перестановка (P), которая завершает работу функции f().

После 16 раундов преобразований (последний раунд несколько отличается от предыдущих – в нем субблоки не меняются местами – см. рис. 1) выполняется еще одна табличная перестановка, называемая финальной.

Схема процедуры расширения ключа показана на рис. 2. Ее задача – формирование подключей для 16 раундов, которое выполняется следующим образом.

Прежде всего, из 64-битного ключа выбираются (в определенном порядке, т.е. с перестановкой относительно их исходного расположения) 56 значащих бит. 56-битный ключ делится на два 28-битных фрагмента, которые обозначаются как C и D.

Затем выполняется 16 раундов процедуры расширения ключа. Каждый раунд дает один из требуемых фрагментов K_i и состоит из следующих преобразований:

1.     Текущие значения C и D циклически сдвигаются влево на переменное число бит n, которое зависит от номера текущего раунда.

2.     C и D объединяются обратно в 56-битное значение, к которому применяется сжимающая перестановка, результатом которой является 48-битный ключ раунда K_i.

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

Теперь рассмотрим собственно дифференциальный криптоанализ. Данный метод основан на анализе пар открытых текстов, между которыми существует определенная разность (difference). При анализе различных алгоритмов разность текстов может быть определена различным образом. Для DES разность открытых текстов M₁ и M₂ определена как операция XOR между данными текстами:

D = M₁ Å M₂.

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

Выполняется такой анализ следующим образом. Предположим, имеется два открытых текста, которые на входе в функцию f() какого-либо раунда алгоритма имеют разность D_b (см. рис. 1):

D_b = b₁ Å b₂.

Разность D_bе = be₁ Å be₂, т.е. разность после обработки b₁ и b₂ расширяющей перестановкой EP, весьма легко определить, поскольку:

D_bе = EP(b₁) Å EP(b₂) = EP(b₁ Å b₂) = EP(D_b).

Наложение фрагмента ключа операцией XOR вообще не меняет разность, т.е.:

D_bk = D_bе.

Аналогично преобразованию EP, легко вычислить разность D_bp после перестановки P:

D_bp = P(bs₁) Å P(bs₂) = P(bs₁ Å bs₂) = P(D_bs).

Таким образом, единственной операцией из выполняемых функцией f(), существенно влияющей на значение разности, остается табличная замена. Значение D_bs зависит не только от разности D_bk, но и от конкретных входных значений bk₁ и bk₂. Здесь-то и проявляется влияние наложенного предыдущей операцией ключа шифрования.

Как было сказано выше, таблицы замен меняют 6-битное входное значение на 4-битное. Это означает, что любой входной разности D_bk,n (где n – номер таблицы) соответствует 2⁶ = 64 возможных пар входных значений (обозначим их bk_1,n и bk_2,n). Соответственно, любой выходной разности D_bs,n соответствует 2⁴ = 16 возможных пар bs_1,n и bs_2,n. Дифференциальный криптоанализ алгоритма DES эксплуатирует тот факт, что, во-первых, каждое конкретное значение D_bk,n приводит не ко всем возможным 16 значениям D_bs,n, а во-вторых, данные значения D_bs,n имеют весьма различную вероятность. Бихам и Шамир в качестве примера рассматривают таблицу S1 и ее входную разность D_bk,1 = 34[1]. Возможные значения D_bs,1 и их вероятности (в количестве значений пар bk_1,1 и bk_2,1 из 64 возможных, которые приводят к данному значению D_bs,1) приведены в следующей таблице [1]:

Как с помощью всего этого можно определить ключ, рассмотрим на простейшем примере. Предположим, что в распоряжении криптоаналитика имеется пара текстов с D_bk,1 = 34. Кроме того, у криптоаналитика есть соответствующие им шифртексты (опять же, предположим, что для их зашифрования использовался однораундовый DES) с D_bs,1 = 4. Входные значения S1 при таких условиях известны [1] – это значения 13 и 27[2] (bk_1,1 = 13, а bk_2,1 = 27, или наоборот). Получается, что криптоаналитик знает значения be₁ и be₂ (поскольку ему известны открытые тексты), а также два варианта значений bk_1,1 и bk_2,1. В результате криптоаналитик может простейшей операцией XOR вычислить 2 возможных варианта первых шести бит K₁. Выбрать из двух вариантов правильный криптоаналитику поможет вторая пара открытых текстов, если таковая у него есть. Даже если такой пары нет, криптоаналитик существенно сузил область возможных значений ключа: в 2⁵ раз.

Понятно, что однораундовый DES не является реальным объектом для криптоанализа. Для вскрытия алгоритмов с большим числом раундов используют характеристики – такие разности открытых текстов, которые с высокой вероятностью вызывают определенные разности в получаемых шифртекстах [4]. В качестве примера рассмотрим следующую трехраундовую характеристику алгоритма DES (см. рис. 3) [1]:

1.     В первом раунде на вход функции f() подаются два субблока с разностью D_b = 60 00 00 00. Разность подобрана таким образом, чтобы после перестановки EP (наложение фрагмента ключа, как было сказано выше, не влияет на разность) быть нулевой на входе всех таблиц замен, кроме S1, на входе которой разность D_bk,1 = 0С. Эта разность обеспечивает выходную разность D_bs,1 = E с вероятностью 14/64, которая после перестановки P (с учетом нулевой разности на выходе остальных таблиц) приводит к разности D_bp = 00 80 82 00. Как видно, эта разность совпадает с разностью необработанных субблоков, т.е. D_a; в результате наложения результата функции f() на необработанный субблок получается нулевая разность на входе второго раунда.

2.     Нулевая разность D_b на входе функции f() во втором раунде дает также нулевую разность на выходе. Следовательно (см. рис. 3), разность на входе функции f() раунда № 3 полностью эквивалентна таковой в первом раунде.

3.     Получается, что разности третьего раунда и их вероятности аналогичны первому раунду. Таким образом, данная характеристика обеспечивает после трех раундов выходную разность D = 00 80 82 00 60 00 00 00 (равную входной разности) со следующей вероятностью:

p =(14/64) * 1 *(14/64)  =(14/64) ²» 0,048.

Характеристики используются следующим образом (на примере трехраундового DES и приведенной выше характеристики):

1.     Генерируется необходимое количество выбранных открытых текстов (пары которых соответствуют выбранной характеристике) и соответствующих им шифртекстов. Количество пар с требуемой разностью оценивается в [1] как «несколько» (several), умноженное на p^-1.

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

Версии алгоритма с большим числом раундов (включая полную 16-раундовую) вскрываются различными путями (см., например, [1] и [2]):

1.     Использованием характеристик, распространяющихся на большее число раундов (но с меньшей вероятностью). Например, в [1] приведена 5-раундовая характеристика с вероятностью 0,000095.

2.     Параллельное использование двух и более различных характеристик.

3.     Использование итеративных характеристик. Пример итеративной характеристики приведен на рис. 4. Итеративные характеристики могут «размножаться» на требуемое количество раундов (конечно, также с потерей в вероятности), поскольку их структура подразумевает, что в выходной разности значения D_a и D_b меняются местами относительно входной разности (что необходимо для «размножения» характеристики, поскольку субблоки в DES меняются местами в конце раунда).

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

1.          Biham E., Shamir A. Differential Cryptanalysis of DES-like Cryptosystems. // http://citeseer.ist.psu.edu – The Weizmann Institute of Science – July 19, 1990.

2.          Biham E., Shamir A. Differential Cryptanalysis of the full 16-round DES. // http://citeseer.ist.psu.edu – Technion, Haifa, Israel – 1991.

3.          FIPS 46-3. Data Encryption Standard (DES). // http://csrc.nist.gov – Reaffirmed 1999 October 25.

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

Об авторе:

Панасенко Сергей Петрович, нач. отдела разработки программного обеспечения фирмы АНКАД, кандидат технических наук.

С автором можно связаться:     

по телефонам (495)532-1313, (495)531-0000

или по E-mail develop@ancud.ru

http://www.panasenko.ru

Названия рисунков:

1.        Структура алгоритма DES.

2.        Процедура расширения ключа в алгоритме DES.

3.        Пример трехраундовой характеристики.

4.        Пример итеративной характеристики.

<<Страница 1