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

Австрийские и польские криптоаналитики представили модель атаки на российский криптографический стандарт ГОСТ Р34.11-94, в ходе которой намного сокращается процесс поиска коллизий.

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

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

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

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

Читайте также

• Украинских пользователей «Вконтакте» полиция не будет ставить на учет
• Блокировка соц.сетей РФ в Украине - А что Вы думаете по поводу?
• В Украине установили первый банкомат для биткойнов
• Польша экстрадирует в США украинца по делу о нарушении авторских правах