01.09 // Ошибка в структуре российской хэш-функции Stribog привела к её полнораундовому взлому

Хэш-функция «Стрибог» (ГОСТ Р 34.11-2012) с размером выхода 512/256 бит стала новым официальным российским стандартом, заменившим в 2013 году старый, теоретически взломанный ГОСТ Р 34.11-94 и была заявлена, как асимметричный ответ на SHA-3.

В основу данной функции положен 12-раундовый AES-подобный шифр с размером внутреннего состояния 8x8 байтов, предваряемый одним раундом нелинейного отбеливания в режиме сцепления. Функция сжатия работает в режиме Миагучи-Пренеля и внесена в расширенную область значений путём выполнения инструкции Меркла-Дамгарда на конечном шаге.

Внешняя структура хэш-функции практически полностью скопирована с режима HAIFA — HAsh Iterative FrAmework (HAIFA), которая использовалась в израильской хэш-функции SHAvite-3 и кандидате на конкурс SHA-3 BLAKE. Общий вид HAIFA-конструкции Stribog выглядит так:

При этом, в оригинальной публикации по режимам хэширования HAIFA не был опубликован формат использования межблокового счётчика и в разных HAIFA-хэшах он был реализован по разному.

По мнению исследователей Jian Guo, Jeremy Jean, Thomas Peyrin, Lei Wang (отдел математических наук, класс физических и математических наук, Наньянский технологический университет, Сингапур) и Gaetan Leurent (Французский государственный институт исследований в информатике и автоматике INRIA) в российском стандарте хэширования Stribog допущена грубая ошибка в использовании счётчика.

Вот так в общем виде выглядит функция сжатия Stribog со счётчиком итераций i:

Поскольку после текущего выполнения функции идёт следующий счётчик итераций i, то альтернативный взгляд может быть таким:

Поскольку функции идут последовательно встык друг за другом, то счётчики ксорятся между собой, в чём и состоит элементарная ошибка конструкции:

Поскольку счётчики на разных раундах не разделены между собой нелинейной функцией, то они связаны друг с другом простейшим линейным XOR-соотношением:

Формула этого соотношения достаточно тривиальна:

Неудивительно, что значение XOR-разниц для каждого чётного счётчика будет всегда равно единице:

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

Если для идеальной 512-битовой хэш-функции для поиска второго прообраза потребовалось бы 2ⁿ или 2⁵¹² шагов, то в атаке исследователей для этого требуется всего n x 2^n/2 или 2²⁶⁶ шагов. Это конечно недостижимое значение для демонстрации атаки на практике, но является существенным результатом, показывающим серьёзную ошибку в реализации конструкции HAIFA в российском хэш-алгоритме Stribog.

Источник: Cryptology ePrint Archive.
См. также: Интегральный криптоанализ хэш-функции ГОСТ Р 34.11-2012 Стрибог, STRIBOB: шифрование с аутентификацией на основе стандарта российской хэш-функции.