29.11 // Прогресс в криптоанализе Keccak/SHA-3

В ходе конкурса на новый стандарт хэширования SHS/SHA-3 в качестве победителя был объявлен алгоритм Keccak.

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

Формально, он ещё не утверждён в виде стандарта, но отчёт о финале конкурса недавно стал доступен на сайте NIST. В этом документе в частности отмечается, что несмотря на то, что для всех участников финала было выявлено некоторое число теоретических атак-различителей, для SHA3 были известны сравнительно практические атаки (коллизии) только на версии с сокращённым числом раундов (4 из 24) для Keccak-224 и Keccak-256.

Но недавно эта же группа исследователей (Динур, Данкельман и Шамир) смогла распространить действие схожих атак на все версии SHA-3/Keccak. Для трёхраундовых версий атаки работают против Keccak-384 и Keccak-512. Быстрее парадокса дней рождения (хотя и за пределами практических возможностей) можно предпринять атаки на 4-раундовый Keccak-384, а на Keccak-256 количество атакованных раундов возросло до пяти.

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

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