Это старая редакция страницы Новости / 2014 / Ошибка В Структуре Российской Хэш-функции Stribog Привела К Её Полнораундовому Взлому за 01/09/2014 11:20.
01.09 // Ошибка в структуре российской хэш-функции Stribog привела к её полнораундовому взлому
Хэш-функция «Стрибог» с размером выхода 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-разниц для каждого чётного счётчика будет всегда равно единице:
Тривиальная ошибка использования счётчика позволила исследователям осуществить атаку на полнораундовую функцию Stribog (полный теоретический взлом). Авторы работы смогли сконструировать не просто атаку нахождения коллизий, но более сильную атаку: атаку нахождения второго прообраза, когда для заданного сообщения M можно подобрать произвольное сообщение M', которое даст на выходе одинаковое хэш-значение.
Если для идеальной 512-битовой хэш-функции для поиска второго прообраза потребовалось бы 2n или 2512 шагов, то в атаке исследователей для этого требуется всего n x 2n/2 или 2266 шагов. Это конечно недостижимое значение для демонстрации атаки на практике, но является существенным результатом, показывающим серьёзную ошибку в реализации конструкции HAIFA в российском хэш-алгоритме Stribog.
Источник: Cryptology ePrint Archive