Криптоанализ алгоритма / Rijndael_ca_rus.doc

Криптоанализ алгоритма Rijndael.

Niels Ferguson, John Kelsey, Stefan Lucks, Bruce Schneier, Mike Stay, David Wagner, and Doug Whiting.

Перевод Алексея Гончарова.

Москва, 2000

Криптоанализ алгоритма Rijndael.

Rijndael - один из пяти шифров, прошедших во второй раунд конкурса на получение статуса AES. В своей структуре он имеет 10, 12, или 14 тактов криптопреобразования в зависимости от длины ключа. Ранее был известен метод, позволяющий взломать до 6-ти тактов алгоритма. В этой работе описывается атака на 7-ой такт Rijndael.

В разделе 2 описывается техника "частичных сумм", которая позволяет очень сильно снизить сложность осуществления шеститактовой атаки. Также показывается, как применить эту идею для атак на 7-ой и 8-ой такты криптопреобразования, используя дополнительные открытые тексты (если это возможно), чтобы снизить сложность атаки. Атаки на семитактовый Rijndael со 128-битным ключом и на восьмитактовый со 192-битным и 256-битным ключом требуют почти полный набор шифров (2¹²⁸-2¹¹⁹ известных открытых текстов); поэтому они не имеют практического применения вследствие недоступности необходимых вычислительных мощностей. Все эти атаки используют расширение специализированной Square - атаки, названной по имени алгоритма Square (предтечи Rijndael), для которого она разрабатывалась.

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

В заключение, в разделе 4 используется слабая диффузия ключеформирования в Rijndael для разработки зависящей о ключа атаки, которая может быть применена к девятитактовому Rijndael с 256-битным ключом.

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

CP - открытые тексты (Chosen Plaintext),

RK-CP - открытые тексты, зависящие от ключа.

Таблица 1. Результаты атак на Rijndael.

Техника, рассматриваемая далее, впервые была задействована при разработке атаки на блочный шифр Square; она применима ко всем блочным шифрам с любой длиной ключа.

Обозначим через m^(r), b^(r) и t^(r) значения текста, используемые в такте r после операций перемешивания столбцов (MixColumn), добавления ключа (key addition) и сдвига строк (ShiftRow) соответственно. Обозначим через k^(r) тактовый ключ цикла r, через k^(r)' - эквивалентное значение тактового ключа, которое может быть XORено с данными перед операцией перемешивания столбцов, а не после. При необходимости посмотрите в приложении А более подробное объяснение используемых обозначений.

Атака начинается с получения 256-ти криптограмм, различающихся только в одном байте m⁽¹⁾, которые охватывают все возможные значения данного байта. Один байт m⁽¹⁾ зависит от 4-х байтов открытого текста и от 4-х байтов ключа k⁽⁰⁾. Для этого выберем 2³² открытых текстов, с фиксированной общей частью и варьирующейся частью размером в 4 байта, охватывающей все возможные 2³² значений. Затем задаемся произвольными значениями 4-х байтов ключа. Для каждого возможного значения байтов ключа можно найти 2²⁴ групп по 256 открытых текстов, которые, будучи подвергнуты операции перемешивания столбцов, внутри своей группы будут отличаться только одним байтом из m⁽¹⁾; так как открытые тексты были различны, то этот байт из m⁽¹⁾ примет все 256 возможных значений.

Отслеживая изменения внутри шифра, заметим, что каждый из байтов t⁽⁴⁾ примет все возможные значения. Если мы просуммируем значения каждого из этих байтов по всем 256 криптограммам, то получим ноль. Это свойство характерно для линейной функции, поэтому каждый из байтов из m⁽⁴⁾ и из b⁽⁴⁾ также дадут ноль при суммировании их значений во всех 256-ти криптограммах.

Теперь посмотрим, как байт из b⁽⁴⁾ связан с байтами из криптограммы. Для анализа мы незначительно изменили структуру шифра и поместим добавление ключа перед преремешиванием столбцов в такте 5. Вместо перемешивания столбцов и добавления ключа k⁽⁵⁾ мы вначале добавим ключ k^(5)', а потом применим перемешивание столбцов. При такой конфигурации легче разглядеть, что любой байт из b⁽⁴⁾ зависят от шифртекста, 4-х байтов ключа k⁽⁶⁾ и одного байта псевдоключа k^(5)'. Мы предположим значения этих 5-ти байт ключа, вычислим значение байта из b⁽⁴⁾ для всех 256 криптограмм и найдем ту, для которой сумма соответствующих байт равна нулю.

Для каждой группы из 256 криптограмм такая фильтрация забракует 256 из 256-ти для всех неверных предположений о значении ключа. Если бы проверялись значения для всех 9-ти байтов ключа, то потребовалось бы 10 или более групп из 256 криптограмм, чтобы найти весь ключ.

В качестве обобщения заметим, что эта атака требует 2³² выбранных открытых текстов, 2³² ячеек памяти для хранения пар текст/шифрограмма, и 2⁷² шагов для выяснения 9-ти байтов ключа. Каждый шаг включает в себя частичную дешифрацию 256 криптограмм, но правильное упорядочивание вычислений может сделать это очень быстрым. Это сравнимо по времени с одиночным шифрованием. Общая вычислительная сложность этой атаки порядка 2⁷² шифрований.

Предыдущая атака может быть распространена на 7-тактовый шифр со 192-битным и 256-битным ключом. Достаточно угадать 16 байт последнего тактового ключа. Если действовать прямо, то это добавляет 128 бит к угадыванию ключа, а временные затраты возрастают до 2²⁰⁰; требования к открытым текстам и памяти не изменяются, несмотря на то, что необходимо использовать больше групп для проверки потенциальных ключей.

Эта процедура может быть усовершенствована. Ключеформирование обеспечивает зависимость между байтами расширенного ключа, и это можно использовать для атаки. Для 192-битного ключа угадывание последнего тактового ключа k⁽⁷⁾ дает 2 из 4-х байтов k^(6)', который должен быть отгадан, плюс байт из k^(5)', который также нужно отгадать. Это уменьшает размер угадываемого ключа на 24 бита, что дает общую сложность порядка 2¹⁷⁶. Для 256-битного ключа байты при ключеформировании выровнены другим образом. Угадывание всего k⁽⁷⁾ не дает никакой информации о k^(6)', но дает один байт из k^(5)'. Для этой длины ключа сложность атаки равна 2¹⁹².

Атака на 6-тактовый Rijndael, описанная в разделе 2.1, может быть улучшена. Вместо угадывания 4-х байтов k⁽⁰⁾ мы просто задействуем все 2³² открытых текста. Для любого значения первого тактового ключа эти криптограммы содержат 2²⁴ групп по 2⁸ криптограмм, различающихся только в одном байте m⁽¹⁾. Все, что будет делаться далее, аналогично предыдущей атаке: угадываем 5 байт ключа в конце шифра, частично дешифруем один байт b⁽⁴⁾, суммируем его значение со всеми остальными в криптограммах и проверяем на нулевой результат. По сравнению с первоначальной версией, мы узнаем только 40 бит ключа вместо 72. Но с другой стороны, мы должны затратить только 2²⁴ операций для каждого угадывания. Это усовершенствование уменьшает затраты на 2⁸, но требует около 6*2³² открытых текстов для обеспечения достаточного числа наборов, необходимых для однозначной идентификации истинного значения 5-ти байт ключа.

Рассмотрим эту атаку более детально. Получив 2³² криптограмм, мы угадываем 5 байт ключа, частично дешифруем один байт b⁽⁴⁾ из всех криптограмм и суммируем эти байты по всем криптограммам. Рассмотрим эту частичную дешифрацию. В любом шифртексте мы используем только 4 байта. Каждый из них XORится c байтом ключа, затем к каждому байту применяется обратный S-box, и в завершении умножается на заданную часть инверсной MSD-матрицы. Четыре байта XORятся вместе, 5-ый байт ключа XORится с результатом применения обратного S-box`а, и полученные значения суммируются по всем шифртекстам.

Обозначим через c_i,j j-ый байт i-ой криптограммы. Для простоты поставим в соответствие байтам, используемым нами в каждом блоке шифртекста, номера от 0 до 3. Пусть k₀,…,k₄ соответствуют 5-ти байтам ключа, которые пытаемся отгадать. Мы хотим вычислить

(1),

где S₀,…,S₃ - биективные S-box`ы, каждый из которых содержит инверсный Rijndael-S-box и следующее за ним умножение на инверсную MDS-матрицу. Имея 2³² криптограмм и 2⁴⁰ возможных значений ключа, мы получим для суммирования 2⁷² различных значений, которое в грубой оценке требует затрат порядка 2⁶⁴ стандартных операций шифрования.

Мы можем организовать эту работу более производительно следующим образом: для каждого k мы поставим в соответствие каждой криптограмме c "частичную сумму" x_k, определяемую следующим образом:

.

Это даст нам отображение (с₀, с₁, с₂, с₃) (x_k, c_k+1,…,c₃), которое можно применить к каждому из шифртекстов, если мы знаем k₀,…,k_k.

Мы начинаем со списка из 2³² криптограмм, угадываем k₀ и k₁ и вычисляем, как часто каждая триада (x₁, c₂, c₃) попадает в список. C этой целью для каждого i вычислим 3-байтовое значение как функцию от шифртекста и угадываемого ключа, и подсчитаем, сколько раз каждое 3-байтовое значение появляется в процессе этих вычислений. Возможно появление 2²⁴ различных 3-байтовых значений, но нам не нужно хранить список всех значений; нам нужно только число появлений каждой триады. Мы угадаем k₂ и вычислим, как часто встречается пара (x₂, c₃); угадаем k₃ и вычислим, как часто встречается значение x₃. Наконец, мы угадаем k₄ и вычислим долгожданную сумму.

Так как все суммы берутся с использованием XOR, и так как для любых z, то этого достаточно только для подсчетов по модулю 2. Таким образом, для каждого счетчика достаточно одного бита, и для всех 2²⁴ счетчиков требуется 2²⁴ бит.

Как много времени на это затратится? На первом этапе мы угадываем 16 бит и обрабатываем 2³² криптограмм, что в сумме дает 2⁴⁸ операций. На следующем этапе мы угадываем еще 24 бита, но при этом обрабатываем только 2²⁴ триад, что в сумме дает 2⁴⁸ операций. В итоге, мы получаем 2⁴⁸ вычислений выражения (1), или порядка 2⁵⁰ вычислений S-box.

Это итоговая работа, неоходимая при единичной структуре из 2³² криптограмм. Первая структура уже очищена от подавляющего большинства неверных ключей, но мы все еще должны пройти первые шаги вычисления частичных сумм для каждой из шести структур, которые нами используются. Таким образом, общее число S-box`ов возрастает до 2⁵².

Используя приближенное равенство 2⁸ S-box'ов одному стандартному криптопреобразованию, получим, что 2⁵² S-box'ов сравнимы с 2⁴⁴ операций. Это значительное достижение по сравнению с предыдущим объемом работ 2⁷².

Мы можем применить усовершенствование к 7-тактовой атаке из раздела 2.2. Для выражения байта из b⁽⁴⁾ через ключ и шифртекст мы возьмем формулу, подобную (1), но трехуровневую, 16 байт криптограммы и 21 байт ключа. Техника "частичных сумм" поможет только во время последней части вычислений, потому что она сэкономит время, если мы имеем больше криптограмм, чем возможных значений промежуточного результата. При наличии в структуре 2³² пар текст/шифрограмма эта техника не поможет нигде за исключением последнего шага вычислений.

Для схемы со 192-битным ключом мы может сначала угадать 128 бит последнего тактового ключа. Эти биты будут также определять 2 из 4-х байт 6-го такта, и один байт ключа 5-го такта. Таким образом, после угадывания последнего тактового ключа мы можем уменьшить каждую структуру до 2²⁴ счетчиков с помощью техники "частичных сумм". Используя некоторые предварительно вычисленные таблицы, мы можем сделать это для каждой из 2¹²⁸ догадок примерно за 2³² обращений к памяти. Следующая стадия приносит еще один байт и требует 2²⁴ шагов для уменьшения частичных сумм до 2¹⁶ счетчиков, и последний этап дает последний оставшийся байт и получает конечный результат. Каждая из этих фаз занимает около 2¹⁶⁰ шагов. Мы имеем три этапа, каждый из которых требует 2¹⁶⁰ шагов, и нам нужно обработать три структуры, прежде чем начать выделение догадок для последнего тактового ключа, поэтому общие затраты на эту атаку составляют порядка 2¹⁶³ S-box'ов или около 2¹⁵⁵ обычных криптопреобразований.

Для 256-битного ключа выравнивание в процессе ключеформирования различное. Получение последнего тактового ключа не дает нам никакой информации о ключе 6-го раунда, но говорит немного больше о ключе 5-го такта. Работая с простой структурой как раньше, мы получим 128 бит последнего тактового ключа и вычислим 4 байта ключа 6-го такта для каждого из 2³² текстов за общее время порядка 2¹⁶⁰. На следующем этапе мы получим еще 16 бит ключа и результаты в 2²⁴ однобитовых счетчиках за общее время порядка 2¹⁷⁶. Дальнейшие фазы расчитываются аналогичным способом. Затраты времени на структуру составляют приблизительно 2¹⁷⁸ S-box'ов или 2¹⁷⁰ криптопреобразований. Необходимо пять структур, прежде чем начать отбрасывание догадок о последнем тактовом ключе, поэтому общая сложность этой атаки составляет примерно 2¹⁷².

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

Вначале будет показано, что 7-тактовый Rijndael может быть сломан при наличии 2¹²⁸ известных текстов при временных затратах порядка 2¹²⁰ обычных шифрований. Эти шифрования разделяются на 2⁹⁶ пакетов по 2³² шифрований в каждом, различающиеся только в четырех байтах m⁽¹⁾. Эти 4 байта находятся на местах, необходимых для применения атаки из раздела 2.3: конкретно каждый пакет из 2³² шифрований содержит 2²⁴ групп по 2⁸ шифрований, которые различаются только одним байтом m⁽²⁾. Соответственно, мы можем рассматривать содержимое набора из 2¹²⁸ шифрований как 2¹²⁰ групп по 2⁸ шифрований, которые отличаются только в одном байте m⁽²⁾. Это обеспечивает, что суммирование одного байта из b⁽⁵⁾ по всем 2⁸ криптограммам в группе даст ноль, и суммирование по всем 2¹²⁸ криптограммам также даст ноль. На этом простом свойстве и базируется атака, описываемая ниже.

Самый простой путь использования этого свойства- это угадать 5 байт ключа в конце шифра, частично расшифровать один байт b⁽⁵⁾ каждого блока шифртекста, просуммировать по всем 2¹²⁸ криптограммам и проверить на ноль. Однако этот простой путь непригоден. Любой неправильный ключ даст ноль после суммирования байта из b⁽⁵⁾ по всем 2¹²⁸ криптограммам, потому что для любого биективого 128-битного блочного шифра b⁽⁵⁾ (или любая другая промежуточная величина) принимает все возможные 128-битовые значения в течение своего цикла из 2¹²⁸ криптопреобразований. Следовательно, необходимо слегка модифицировать атаку.