Показана уязвимость хэш-функции российского криптостандарта

ГОСТ 34.11-94 определяет алгоритм и процедуру вычисления хэш-функции, используемой в России при реализации электронно-цифровой подписи (ЭЦП) и в других криптографических приложениях.

Хэш-функция h - детерминированная функция, отображающая строку битов произвольной длины в строку битов фиксированной длины. Хэш-функции должны обеспечивать неразрешимость задачи вычисления входной строки x по h(x). Кроме того, они должны быть устойчивы к коллизиям, то есть успешному поиску величин x и y, удовлетворяющих условиям "x не равно y" и "h(x) равна h(y)".

Исследователи из Университета Граца и Варшавского института математики и криптологии показали уязвимость российского стандарта ГОСТ 34.11-94 к атакам, направленным на писк коллизий и на вычисление как первого, так и второго прообраза, то есть соответственно двух или трех значений входной строки, для которых выходная строка совпадает.

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

В результате коллизионный поиск мог быть существенно сокращен. Сложность успешной атаки, направленной на поиск коллизий, составил 2¹⁰⁵ операций, на поиск второго прообраза - 2¹⁹³ операций (последний показатель в 2³³ раз сокращает время аналогичной атаки, показанной в этом же году Флорианом Менделем (Florian Mendel) с коллегами).