Регистрация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-битовой хэш-функции для поиска второго прообраза потребовалось бы 2n или 2512 шагов, то в атаке исследователей для этого требуется всего n x 2n/2 или 2266 шагов. Это конечно недостижимое значение для демонстрации атаки на практике, но является существенным результатом, показывающим серьёзную ошибку в реализации конструкции HAIFA в российском хэш-алгоритме Stribog.
Источник: Cryptology ePrint Archive.
См. также: Интегральный криптоанализ хэш-функции ГОСТ Р 34.11-2012 Стрибог, STRIBOB: шифрование с аутентификацией на основе стандарта российской хэш-функции.
с родителями.Вы действительно не понимаете? Это же закладка! Тогда всё встаёт на свои места вместе с иллюминатами, которые известили о закладке через этот ёпринт. В России эту новость пропустят или заболтают, а потом соберут конференции, для своей души, где будут доказывать, что эта уязвимость и не уязвимость вовсе. Всё как с предыдущими гостами, в том числе действующими и взломанными.
комментариев: 9796 документов: 488 редакций: 5664
Если бы закатали внутреннию функцию не в Хайфу, а в губку, то такой глупой ошибки не возникло бы.
Два раза поксорить счётчик в один поток — это хуже, чем уязвимость. Это ошибка.
Вспомнились почему-то господа Рудской и Алексеев. Ещё поди снова придут сюда и будут орать, что это не практический взлом, поэтому пофиг.
комментариев: 9796 документов: 488 редакций: 5664
На слайдах опять истерика по поводу «ну и что, что теоретически взломан, это же не практический взлом!». Сами честно признаются, что лишь воруют «тренды», да занимаются переименованиями. Рудской такой рудской...
комментариев: 9796 документов: 488 редакций: 5664
комментариев: 9796 документов: 488 редакций: 5664
Есть ли какие-нибудь пояснения/обоснования? Как получен S-box? Диф. характеристика слабее чем у AESовского.
Запаса стойкости RC4 тоже хватает, чтобы обеспечить недешифруемость.
Вот только использовать обоих нужно с оглядкой, помня о свойствах.
Для этого его придётся обвешать огромным числом костылей и органичений.
Боитесь, что Кузнечик — обычная Саранча? Документ, конечно же, вородовый. Не могу понять эту больную на голову самобытность в форматировании. Впрочем, относительно аккуратно постарались сделать.