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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Дифференциальный криптоанализ основан на изучении преобразования разностей между шифруемыми значениями на различных раундах шифрования. В качестве разности, как правило, применяется операция побитового суммирования по модулю 2, хотя существуют атаки и с вычислением разности по модулю 2^{32}. Является статистической атакой. Применим для взлома DES, FEAL и некоторых других шифров, как правило, разработанных ранее начала 90-х. Количество раундов современных шифров (AES, Camellia и др.) рассчитывалось с учетом обеспечения стойкости в том числе и к дифференциальному криптоанализу.

История[править | править исходный текст]

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

В 1994 году Дон Копперсмит из IBM опубликовал статью, в которой заявил, что метод дифференциального криптоанализа был известен IBM уже в 1974 году, и одной из поставленных целей при разработке DES была защита от этого метода. У IBM были свои секреты. Копперсмит объяснял:

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

DES оказался криптостойким к дифференциальному криптоанализу, в отличие от некоторых других шифров. Так, например, уязвимым оказался шифр FEAL. Состоящий из 4 раундов FEAL-4 может быть взломан используя всего лишь 8 подобранных открытых текстов, и даже 31-раундовый FEAL уязвим для атаки.

Дифференциальный криптоанализ DES[править | править исходный текст]

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

Схема взлома[править | править исходный текст]

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

Вспомогательные определения и леммы[править | править исходный текст]

Обозначения:

X, X^{*} : рассматриваемая пара на каком-либо этапе алгоритма шифрования

X^{'} :\ X^{'} = X \oplus X^{*}

P(X) : перестановка битов числа X

E(X) : функция расширения в DES

P : открытый текст. P и P^{*} — пара открытых текстов с разностью P^{'} = P \oplus P^{*}

T : шифротекст, соответствующий открытому тексту P. T и T^{*} — пара шифротекстов с разностью T^{'} = T \oplus T^{*}

Si : S — блоки функции Фейстеля S1, S2, ..., S8

Si_{EX},\ Si_{KX},\ Si_{IX},\ Si_{OX} : результат функции расширения E(X); 6-битный подключ; Si_{IX}\ = \ Si_{EX} \oplus Si_{KX} подается на вход S-блока; Si_{OX} \ = \ Si(Si_{IX}) — согласно алгоритму DES

Единственные нелинейные элементы в схеме — это S-блоки. Для каждого S-блока можно хранить таблицу, строки которой — разности на входе S-блока, столбцы — разности на выходе, а на пересечении — число пар Si_{IX}, имеющих данные входную и выходную разности, и где-то хранить сами эти пары.

Подбирая пары открытых текстов(пока размером 6 бит) и пропуская их через S-блок, будем знать выходную разность. Итак, мы знаем Si_{E}, Si^{*}_{EX} и Si^{'}_{O}, хотим найти Si_{K}. Независимо от Si_{K} всегда Si^{'}_{E} = Si^{'}_{I}, то из таблиц можно найти все возможные варианты для Si_{I}, а значит и соответствующие варианты для Si_{K} = Si_{E} \oplus Si_{I}. Выбрав несколько пар, получим несколько предложенных вариантов. Правильный вариант ключа обязаны предложить все пары. Так можно подобрать подключ для S-блока.

Определение Будем говорить, что разность X преобразуется в разность Y функцией Фейстеля F, если из всех возможных пар кодируемых всеми возможными подключами существует ненулевая доля p пар с входной разностью X и выходной разностью Y. В этом случае будем писать x \rightarrow y

Лемма

Если в DES x \rightarrow y с вероятностью p, то для каждой фиксированной входной пары Z и Z^{*} с разностью X вероятность выходной разности Y при кодировании всеми возможными подключами также равна p.

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

В качестве отличий в DES используются характеристики. Дадим им определение.

Определение n-раундовая характеристика — это кортеж \Omega \ = \ (\Omega_{P}, \Omega_{\Lambda}, \Omega_{T}), где \Omega_{P} и \Omega_{T} — m-битные числа и \Omega_{\Lambda} — вектор из n элементов \Omega_{\Lambda} \ = \ (\Lambda_{1}, \Lambda_{2},\ ...\ , \Lambda_{n}), где каждый элемент — \Lambda_{i} \ = \ (\lambda_{I}^{i}, \lambda_{O}^{i}), \lambda_{I}^{i} и \lambda_{O}^{i} — m/2 битные числа, m — размер блока в криптосистеме.

Характеристика удовлетворяет следующим условиям:

  1. \lambda^{1}_{I} — правая половина \Omega_{P}
  2. \lambda^{2}_{I} — левая половина \Omega_{P} \oplus \lambda^{1}_{O}
  3. \lambda^{n}_{I} — правая половина \Omega_{T}
  4. \lambda^{n-1}_{I} — левая половина \Omega_{T} \oplus \lambda^{n}_{O}
  5. \lambda^{i}_{O} = \lambda^{i-1}_{I} \oplus \lambda^{i+1}_{I} для всех 2 \leq i \leq n-1

Определение Правильная пара по отношению к n-раундовой характеристике \Omega \ = \ (\Omega_{P}, \Omega_{\Lambda}, \Omega_{T}) и независимому ключу K — это пара (P, P^{*}), для которой P^{'} = \Omega_{P} и для первых n раундов шифрования с использованием ключа K входная разность i-ого раунда равна \lambda^{i}_{I}, а разность на выходе из функции Фейстеля равна \lambda^{i}_{O}. Остальные пары будем называть ошибочными.

Определение Раунд i характеристики \Omega имеет вероятность p^{\Omega}_{i}, если \lambda^{i}_{I} \rightarrow \lambda^{i}_{O} с вероятностью p^{\Omega}_{i}.

Определение n-раундовая характеристика \Omega имеет вероятность p^{\Omega}, если p^{\Omega} =  \prod_{i=1}^n p^{\Omega}_{i}

Теорема

Вероятность n-раундовой характеристики в точности равна вероятности того, что любая пара, удовлетворяющая P^{'} = \Omega_{P} является правильной парой, если используют

Рис 1. Простейшая однораундовая характеристика с вероятностью 1

ся случайные независимые ключи.

Пример 1

На рис. 1 приведен пример простейшей однораундовой характеристики, имеющей вероятность 1.

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

Отношение сигнал/шум[править | править исходный текст]

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

Определение Отношение числа правильных пар к среднему значению счетчика будем называть отношением сигнал/шум для нашей расчетной схемы и будем обозначать S/N

Чтобы выделить правильный ключ, необходима характеристика с достаточной вероятностью и достаточное количество пар, чтобы гарантировать наличие среди них правильных пар. Число необходимых пар определяется вероятностью характеристики, числом бит ключа, которые мы хотим определить и уровнем идентификации ошибочных пар (они не вносят вклада в счетчики, так как отбрасываются раньше). Пусть мы ищем k бит ключа, тогда у нас 2^{k} счетчиков. Если m — число используемых пар, \alpha — средняя добавка к счетчикам для одной пары, \beta — отношение пар которые вносят вклад в счетчики ко всем парам (в том числе отброшенным). Среднее значение счетчика равно \frac{m \cdot \alpha \cdot \beta}{2^{k}}. Если p — вероятность характеристики, то число правильных пар равно m \cdot p. Тогда имеем следующее соотношение для отношения сигнал/шум: S/N = \frac{m \cdot p}{m \cdot \alpha \cdot \beta / 2^{k}} = \frac{2^{k} \cdot p}{\alpha \cdot \beta}

Заметим, что отношение сигнал/шум для расчетной схемы не зависит от общего числа пар. Число необходимых правильных пар — в общем, функция отношения сигнал/шум. Экспериментально было получено, что если S/N=1-2, необходимо 20-40 вхождений правильных пар. Если же отношение намного выше, то даже 3-4 правильных пары может быть достаточно. Наконец, когда оно сильно ниже, необходимо огромное число пар.

Структуры[править | править исходный текст]

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

Определение Квартет — структура из четырёх текстов, которая одновременно содержит в себе по две пары текстов для двух разных характеристик. Октет — структура, содержащая 8 пар, по 4 на каждую характеристику.

Пример

Следующие четыре текста образуют квартет, \psi_{1} и \psi_{2} — требуемые входные разности для характеристик(\Omega_{P})

  1. Случайный открытый текст P
  2. P \oplus \psi_{1}
  3. P \oplus \psi_{2}
  4. P \oplus \psi_{1} \oplus \psi_{2}

Две пары для первой характеристики: (1, 2) и (3, 4)

Две пары для второй характеристики: (1, 3) и (2, 4)

Таким образом, используя квартеты, можно сэкономить половину памяти для открытых текстов, а при использовании октетов — 2/3.

Взлом алгоритма шифрования DES из 4-х раундов[править | править исходный текст]

Рис. 2 4-раундовый DES

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

На первом раунде a^{'} = 0 \rightarrow A^{'} = 0 с вероятностью 1. Для остальных раундов введем аналогичные A, a обозначения B, b, C, c, D, d (на входе в функцию Фейстеля малые буквы, на выходе — большие).

Открытые тексты отличаются одним битом, и это начинает играть роль начиная со второго раунда. В следствие лавинного эффекта очень вероятно, что входные тексты во всех S-блоках четвёртого раунда отличаются.

28 бит B^{'} (для S-блоков S2, ... , S8) должны быть нулями, так как те же биты в b^{'} также являются нулями. Значение D^{'} может быть определено через a^{'}, B^{'} и T^{'}_{L} так: D^{'} = a^{'} \oplus B^{'} \oplus T^{'}_{L}. Кроме того, d = T_{R}. Так как a^{'}, T^{'}_{L} и 28 бит B^{'} известны, то мы знаем соответствующие 28 бит D^{'}.

Иными словами, мы знаем S_{Ed}, S^{*}_{Ed} и S^{'}_{Od} для 7 S-блоков четвёртого раунда. Можно перебрать все 64 возможных варианта для S_{Kd} и для каждого проверить выполнение условия S(S_{Ed} \oplus S_{Kd}) \oplus S(S^{*}_{Ed} \oplus S_{Kd}) = S^{'}_{Od}.

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

Итак, мы смогли найти 7 \cdot 6 = 42 бит подключа последнего раунда. Если подключи генерируются из одного 56-битного ключа (по алгоритму генерации ключей), то неизвестными остались лишь 14 бит ключа. Перебирая 2^{14} вариантов и расшифровывая шифротексты, найдем ключ, удовлетворяющий всем текстам.

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

Найдем оставшиеся 6 бит подключа K_{4} и подключ K_{3}, используя другую характеристику \Omega^{2} (Рис. 4). Постепенно находя подключи и уменьшая число раундов, избавляясь от соответствующих раундов, найдем все искомые подключи.

Рис. 3 Характеристика для взлома 4-раундового DES

Для данной атаки необходимо 16 выбранных открытых текстов, для экономии памяти можно использовать 2 октета.

Рис. 4 Вторая характеристика для взлома 4-раундового DES

Эффективность взлома[править | править исходный текст]

С увеличением числа раундов в DES увеличивается и сложность криптоанализа. Запишем в таблицу лучшие результаты, которые были получены для соответствующего числа раундов DES.

Выбранные открытые тексты — число текстов, необходимое для атаки на основе адаптивно подобранных открытых текстов

Известные открытые тексты — число текстов, необходимое для атаки на основе открытых текстов

Проанализированные тексты — число текстов, за исключением отброшенных на этапе анализа

Число раундов Выбранные открытые тексты Известные открытые тексты Проанализированные тексты Число операций DES
8 2^{14} 2^{38} 4 2^{9}
9 2^{24} 2^{44} 2 2^{32}
10 2^{24} 2^{43} 2^{14} 2^{15}
11 2^{31} 2^{47} 2 2^{32}
12 2^{31} 2^{47} 2^{21} 2^{21}
13 2^{39} 2^{52} 2 2^{32}
14 2^{39} 2^{51} 2^{29} 2^{29}
15 2^{47} 2^{56} 2^{7} 2^{37}
16 2^{47} 2^{55} 2^{36} 2^{37}

Повышение устойчивости к взлому[править | править исходный текст]

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

Недостатки метода[править | править исходный текст]

Отмечается, что метод дифференциального криптоанализа в большей степени является теоретическим достижением. Его применение на практике ограничено высокими требованиями к времени и объёму данных. Кроме того, этот метод в первую очередь применим для вскрытия с выбранным открытым текстом. Он может быть использован для вскрытия с известным открытым текстом, но в случае полного 16-этапного DES это делает его даже менее эффективным, чем вскрытие грубой силой.

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

Сравнение с другими методами[править | править исходный текст]

См. Известные атаки на DES

См. также[править | править исходный текст]

Литература[править | править исходный текст]