openPGP в России

05.11 // Криптоанализ на супер-S-блоках отвоёвывает ещё один раунд теоретической стойкости у AES

Проходящий конкурс НИСТ на новый стандарт хэш-функции SHA-3^[link1] в качестве побочного результата привлёк внимание исследователей и к блочным шифрам. Это связано с тем, что обычный блочный шифр может быть компонентом хэш-функции, входящим в раундовое преобразование. Также методы анализа раундовых преобразований в хэш-функциях, не являющихся в явном виде блочными шифрами, являются схожими.

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

Но при создании хэш-функций эта модель была расширена ещё больше. При работе хэш-функции противник может видеть не только вход и выход, а всё внутреннее состояние — на каждом раунде преобразования. Если перенести эту модель обратно на блочный шифр, то получается, что противник может знать и выбирать и открытый текст, и шифртекст и даже ключ. Эта модель получила название модель известного ключа. Криптоаналитическим взломом в такой модели считается нахождение любого различителя между идеальной псевдослучайной перестановкой при любых манипуляциях не только с текстами, но и с ключом. Такая модель делает шифр всё более похожим не на "чёрный", а на "стеклянный" ящик. Шифр, который удовлетворяет условиям такой модели, называется идеальный шифр.

Поскольку эта модель возникла относительно недавно из-за исследований в области хэш-функций, то широкораспространённые шифры не проектировались под модель идеального шифра. Исследователи Henri Gilbert и Thomas Peyrin в работе Super-Sbox Cryptanalysis: Improved Attacks for AES-like permutations^[link2] исследовали AES в рамках модели идеального шифра и нашли новые доказательства его несоответствия этой модели. Эта модель позволяет применить новые виды криптоанализа — например криптоанализ на S-блоках, когда объединяются функции от двух раундов и вместо рассмотрения 8-битного S-блока используется комбинированный 32-битный с предшествующим и последующим афинным преобразованием. Поскольку ключ известен, то результат ключевого расписания на каждом раунде не имеет значения. Зато сочетание этих двух факторов увеличивает количество степеней свободы. Это позволило получить различитель в рамках данной модели для 8 раундов AES-128 за 2⁴⁸ вычислительных шагов и 2³² затрат памяти. Ранее аналогичная атака работала только против семи из десяти раундов AES-128.

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

Однако, данное исследование имеет значение для конструирования на основе AES протоколов и других примитивов, например хэш-функций. Как предполагалось ранее, на основе предыдущих атак на AES, доказывающих его несоответствие модели идеального шифра, AES не стоит использовать в дизайне хэш-функций, что выяснилось уже в самом разгаре конкурса SHA-3. Авторы данной работы провели на основе полученного результата успешный криптоанализ двух кандидатов на SHA-3 — Gr0stl (хэш-функция, основанная на AES) и ECHO (функция, основанная на аналоге AES).

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

Интересно, что блочный шифр Threefish (лучшие атаки на который действуют против 33 раундов из 72 согласно данным на начало ноября 2009^[link3] и требуют неимоверно больших вычислительных затрат — 2³⁵² ) от комманды Брюса Шнайера, положенный в основу хэш-функции Skein^[link4], предусмотрительно создан с критерием соответствия модели идеального шифра и его создателями приведены доказательства необходимости такого дизайна.

Источник: Cryptology ePrint Archive^[link2]