22.03 // Улучшенная дифференциальная атака на полнораундовый ГОСТ 28147-89

Известный криптограф Николя Куртуа продолжает свою серию публикаций, посвящённых изучению возможностей взлома российского стандарта шифрования ГОСТ 28147-89. Этот блочный шифр долгое время считался общепризнанно стойким, но в последнее время в процессе попыток его международной стандартизации было обращено внимание на его уязвимости. Шифр был взломан с теоретической точки зрения (с позиций сертификационного криптоанализа). Такой взлом недостижим с помощью реально существующих вычислительных ресурсов и абсолютно непрактичен, но делает стандарт фактически устаревшим.

Несмотря на некоторую тенденциозность и предвзятость Куртуа и излишне язвительные и эмоциональные выпады, которые он допускает в своих работах, его результаты можно воспринимать достаточно серьёзно. Они были подтверждены группой исследователей во главе с Ади Шамиром, которые предложили альтернативный вариант дифференциального криптоанализа ГОСТа за 2¹⁹² операций при полном исчерпании кодовой книги (2⁶⁴ шифртекстов). Эта работа была представлена на конференции FSE 2012, сам результат был опубликован в октябре 2011 года.

С того момента Куртуа предложил атаку за 2¹⁸² операций на случайных ключах, а в новой работе он улучшил результат до 2¹⁷⁸ операций. Хотя такая атака по прежнему требует исчерпания кодовой книги и по определению непрактична, она демонстрирует быстрый прогресс в криптоанализе, которого можно достигнуть, если сосредоточить усилия на взломе нестойкого шифра. Интересны и теоретическое наблюдения: какие-бы стойкие S-блоки не выбирались для ГОСТа, из-за особенностей его структуры их совместное использование в раундовой функции не даёт защиты от криптоанализа. Иными словами, более слабые S-блоки могут лишь существенно ослабить ГОСТ, а более сильные не приведут к росту стойкости при существующей структуре остальных элементов (порядка использования операций XOR-ADD-Rotation). Это связано с тем, что существующая структура позволяет производить эффективные атаки с учётом взаимосвязи S-блоков, а не только на основе изучения свойств, описывающих их стойкость отдельно для каждого S-блока.

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