id: Гость   вход   регистрация
текущее время 23:43 09/12/2018
Владелец: unknown (создано 01/09/2014 11:20), редакция от 02/09/2014 17:03 (автор: unknown) Печать
Категории: криптография, криптоанализ, алгоритмы, хэширование, атаки
http://www.pgpru.com/Новости/2014/ОшибкаВСтруктуреРоссийскойХэш-функцииStribogПривелаКЕёПолнораундовомуВзлому
создать
просмотр
редакции
ссылки

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


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


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


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


Stribog overall structure (34 Кб)


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


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


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


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


Compression function alternative view (5 Кб)


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


Two compression function with interacted counters (18 Кб)


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


Two compression functions with counter differences (9 Кб)


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


Counter differences formula (7 Кб)


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


Counter differences table (18 Кб)


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


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


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


 
Много комментариев (17) [показать комментарии/форму]
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3