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

В 1990 году Эли Бихам и Ади Шамир ввели понятие дифференциального криптоанализа [167, 168, 171, 172]. Это был новый, ранее неизвестный метод криптоанализа. Используя этот метод, Бихам и Шамир нашли способ вскрытия DES с использованием выбранного открытого текста, который был эффективнее вскрытия грубой силой.

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

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

Подробности гораздо сложнее. На Рис. 12-5 представлена функция одного этапа DES. Представьте себе пару входов, X и X', с различием DX. Выходы, Y и Y' известны, следовательно, известно и различие между ними DY. Известны и перестановка с расширением, и P-блок, поэтому известны DA и DC. B и B' неизвестны, но их разность DB известна и равна DA. (При рассмотрении различия XOR K_i с A и A' нейтрализуются.) Пока все просто. Фокус вот в чем: для любого заданного DA не все значения DC равновероятны. Комбинация DA и DC позволяет предположить значения битов для A XOR K_i и A' XOR K_i. Так как A и A' известны, это дает нам информацию о K_i.

Рис. 12-5. Функция этапа DES.

Взглянем на последний этап DES. (При дифференциальном криптоанализе начальная и заключительная перестановки игнорируются. Они не влияют на вскрытие, только затрудняя объяснение.) Если мы сможем определить K₁₆, то мы получим 48 битов ключа. (Не забывайте, на каждом этапе подключ состоит из 48 битов 56-битового ключа.) Оставшиеся 8 битов мы можем получить грубым взломом. K₁₆ даст нам дифференциальный криптоанализ.

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

Эти характеристики можно найти, создав таблицу, строки которой представляют возможные входы XOR (XOR двух различных наборов входных битов), столбцы - возможные результаты XOR, а элементы - сколько раз конкретный результат XOR встречается для заданного входа XOR. Такую таблицу можно сгенерировать для каждого из восьми S-блоков DES.

Например, на Рис. 12-6a показана характеристика одного этапа. Входное различие слева равно L, оно может быть произвольным. Входное различие справа равно 0. (У двух входов одинаковая правая половина, поэтому их различие - 0.) Так как на входе функции этапа нет никаких различий, то нет различий и на выходе функции этапа. Следовательно, выходное различие левой части - L Å 0 = L, а выходное различие правой части - 0. Это тривиальная характеристика, она истинна с вероятностью 1.

На Рис. 12-6б показана менее очевидная характеристика. Снова, различие L левых частей произвольно. Входное различие правых частей равно 0x60000000, два входа отличаются только первым и третьим битами. С вероятностью 14/64 различие на выходе функции этапа равно L Å 0x00808200. Это означает, что выходное различие левых половин равно L Å 0x00808200, а выходное различие правых половин - 0x60000000 (с вероятностью 14/64)

Рис. 12-6. Характеристики DES.

Различные характеристики можно объединять. Также, при условии, что этапы независимы, вероятности могут перемножаться. На Рис. 12-7 объединяются две ранее описанных характеристики. Входное различие слева равно 0x00808200, а справа - 0x60000000. В конце первого этапа входное различие и результат функции этапа нейтрализуют друг друга, и выходное различие равно 0. Это различие поступает на вход второго этапа, окончательное выходное различие слева равно 0x60000000, а справа - 0. Вероятность этой двухэтапной характеристики - 14/64.

Рис. 12-7. Двухэтапная характеристика DES.

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

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

Итак, дифференциальное основное вскрытие n-этапного DES дает 48-битовый подключ, используемый на этапе n, а оставшиеся 8 битов ключа получаются с помощью грубого взлома.

Но ряд заметных проблем все же остается. Во первых, пока вы не перейдете через некоторое пороговое значение, вероятность успеха пренебрежимо мала. То есть, пока не будет накоплено достаточное количество данных, выделить правильный подключ из шума невозможно. Кроме того, такое вскрытие не практично. Для хранения вероятностей 2⁴⁸ возможных ключей необходимо использовать счетчики, и к тому же для вскрытия потребуется слишком много данных.

Бихам и Шамир предложили свой способ вскрытия. Вместо использования 15-этапной характеристики 16-этапного DES, они использовали 13-этапную характеристику и ряд приемов для получения последних нескольких этапов. Более короткая характеристика с большей вероятностью будет работать лучше. Они также использовали некоторые сложные математические приемы для получения вероятных 56-битовых ключей, которые и проверялись немедленно, таким образом устранялась потребность в счетчиках. Такое вскрытие достигает успеха, как только находится правильная пара. Это позволяет избежать порогового эффекта и получить линейную зависимость для вероятности успеха. Если у вас в 1000 раз меньше пар, то вероятность успеха в 1000 раз меньше. Это звучит ужасно, но это намного лучше, чем порог. Всегда есть некоторая вероятность немедленной удачи.

Результаты являются весьма интересными. В Табл. 12-14 проведен обзор лучших дифференциальных вскрытий DES с различным количеством этапов [172]. Первый столбец содержит количество этапов. Элементы следующих двух столбца представляют собой количество выбранных или известных открытых текстов, которые должны быть проверены для вскрытия, а четвертый столбец содержит количество действительно проанализированных открытых текстов. В последнем столбце приведена сложность анализа, после обнаружения требуемой пары.

Табл. 12-14. Вскрытие с помощью дифференциального криптоанализа

† Сложность анализа для этих вариантов может быть значительно уменьшена за счет использования примерно в четыре раза большего количество открытых текстов и метода группировок.

Наилучшее вскрытие полного 16-этапного DES требует 2⁴⁷ выбранных открытых текстов. Можно преобразовать его к вскрытию с известным открытым текстом, но для него потребуется уже 2⁵⁵ известных открытых текстов. При анализе потребуется 2³⁷ операций DES.

Дифференциальный криптоанализ эффективен против DES и аналогичных алгоритмов с постоянными S-блоками. Эффективность вскрытие сильно зависит от структуры S-блоков, блоки DES по счастливой случайности были оптимизированы против дифференциального криптоанализа. Для всех режимов работы DES - ECB, CBC, CFB и OFB - вскрытие с дифференциальным криптоанализом имеет одинаковую сложность [172].

Устойчивость DES может быть повышена путем увеличения количества этапов. Дифференциальный криптоанализ с выбранным открытым текстом для DES с 17 или 18 этапами потребует столько же времени, сколько нужно для вскрытия грубой силой [160]. При 19 и более этапах дифференциальный криптоанализ становится невозможным, так как для него потребуется более, чем 2⁶⁴ выбранных открытых текстов - не забудьте, DES использует блоки размером 64 битов, поэтому для него существует только 2⁶⁴ возможных открытых текстов. (В общем случае, вы можете доказать устойчивость алгоритма к дифференциальному криптоанализу, показав, что количество открытых текстов, необходимых для выполнения вскрытия, превышает количество возможных открытых текстов.)

Нужно отметить ряд важных моментов. Во первых, это вскрытие в значительной степени теоретическое. Огромные требования к времени и объему данных, необходимых для выполнения вскрытия с помощью дифференциального криптоанализа, находятся почти для всех вне пределов досягаемости. Чтобы получить нужные данные для выполнения такого вскрытия полного DES, вам придется почти три года шифровать поток выбранных шифротекстов 1.5 Мегабит/с. Во вторых, это в первую очередь вскрытие с выбранным открытым текстом. Оно может быть преобразовано к вскрытию с известным открытым текстом, но вам придется просмотреть все пары "открытый текст/шифротекст" в поисках полезных. В случае полного 16-этапного DES это делает вскрытие чуть менее эффективным по сравнению с грубой силой (вскрытие дифференциальным криптоанализом требует 2^55.1 операций, а вскрытие грубой силой - 2⁵⁵). Таким образом, правильно реализованный DES сохраняет устойчивость к дифференциальному криптоанализу.

Почему DES так устойчив к дифференциальному криптоанализу? Почему S-блоки оптимизированы так, что усложняют такое вскрытие насколько возможно? Почему используется ровно столько, а не больше этапов? Потому что создатели DES знали о дифференциальном анализе. Дон Копперсмит из IBM недавно писал [373, 374]:

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

Ади Шамир откликнулся, предложив Копперсмиту признаться, что с тех пор ему не удалось найти эффективного способа вскрытия DES. Копперсмит предпочел отмолчаться [1426].