id: Гость   вход   регистрация
текущее время 08:40 29/03/2024
Владелец: unknown (создано 05/11/2009 12:56), редакция от 09/11/2009 12:11 (автор: unknown) Печать
Категории: криптография, алгоритмы, хэширование, симметричное шифрование
http://www.pgpru.com/Новости/2009/КриптоанализНаСуперS-блокахОтвоёвываетЕщёОдинРаундТеоретическойСтойкостиУAES
создать
просмотр
редакции
ссылки

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


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


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


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


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


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


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


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


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


Источник: Cryptology ePrint Archive


 
Несколько комментариев (5) [показать комментарии/форму]
Общая оценка документа [показать форму]
страница еще не оценена