8.4. Хеш-функция «Стрибог»

С 1 января 2013 года в России введён в действие обновлённый стандарт на криптографическую хеш-функцию ГОСТ Р 34.11-2012 [120]. Неофициально новый алгоритм получил название «Стрибог». При разработке хеш-функции авторы основывались на нескольких требованиях:

отсутствие уязвимостей к известным атакам;
использование только хорошо изученных конструкций и преобразований;
отсутствие лишних действий (каждое преобразование должно гарантировать выполнение определённых криптографических свойств);
при наличии нескольких вариантов реализации требуемого свойства – использование наиболее простого для анализа и реализации;
максимальная производительность программной реализации (процессоры архитектуры x64).

В соответствии с данными требованиями алгоритм новой хеш-функции основывается на хорошо изученных конструкциях Меркла — Дамгора (см. раздел 8.1) и Миагучи — Пренеля [77, 78, 105], во внешней своей структуре практически полностью повторяя режим HAIFA (англ. HAsh Iterative FrAmework, [13]), использовавшийся в хеш-функциях SHAvite-3 и BLAKE.

Рис. 8.8 — Использование структуры Меркла — Дамгора в хеш-функции «Стрибог»

Как показано на рис. 8.8, входное сообщение разбивается на блоки по 512 бит (64 байта). Последний блок слева дополняется последовательностью из нулей и одной единицы до 512 бит (длина дополнения не учитывается в дальнейшем, когда длина сообщения используется как аргумент функций). Для каждой части сообщения вычисляется значение функции $g_N(h, m)$, которая в качестве аргумента использует текущий номер блока (умноженный на 512), результат вычисления для предыдущего блока и очередной блок сообщения. Также есть два завершающих преобразования. Первое вместо блока сообщения использует количество обработанных бит N (то есть длину сообщения), а второе – арифметическую сумму значений всех блоков сообщения. В предположении, что функция $g_N(h, m)$ является надёжной для создания криптографически стойких хеш-функций, известно, что конструкция Меркла — Дамгора позволяет получить хеш-функцию со следующими параметрами:

сложность построения прообраза: $2^n$ операций;
сложность построения второго прообраза: $2^n / \left|M\right|$ операций;
сложность построения коллизии: $2^{n/2}$ операций;
сложность удлинения прообраза: $2^n$ операций.

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

В качестве функции $g_N(h, m)$ используется конструкция Миагучи — Пренеля (см. рис. 8.9), которая является стойкой ко всем атакам, известным для схем однонаправленных хеш-функций на базе симметричных алгоритмов, в том числе к атаке с «фиксированной точкой» [135]. Фиксированной точкой называется пара чисел $(h, m)$, для которой у заданной функции $g$ выполняется $g(h, m) = h$.

Рис. 8.9 — Использование структуры Миагучи — Пренеля в хеш-функции «Стрибог»

В качестве блочного шифра используется новый XSPL-шифр, изображённый на рис. 8.10, отдельные элементы и идеи которого позже войдут в новый стандарт «Кузнечик» (см. раздел 5.7). Шифр является примером шифра на основе SP-сети (сети замен и перестановок), каждый раунд которого является набором обратимых преобразований над входным блоком.

Рис. 8.10 — XSPL-шифр в хеш-функции «Стрибог»

Каждый раунд XSPL-шифра, кроме последнего, состоит из следующих обратимых преобразований:

$X\left[C\right]$ – побитовое сложение по модулю 2 с дополнительным аргументом $C$;
$S$ – нелинейная обратимая замена байтов;
$P$ – перестановка байтов внутри блока данных (транспонирование матрицы размером $8 \times 8$ из ячеек по одному байту каждая);
$L$ – обратимое линейное преобразование (умножение векторов на фиксированную матрицу).

Особенностью предложенного шифра является полная аналогия между алгоритмом развёртывания ключа и алгоритмом, собственно, преобразования открытого текста. В качестве «раундовых ключей» для алгоритма развёртывания ключа на первом раунде используется общее число уже обработанных бит хеш-функцией N, а на остальных раундах – 512-битные константы, заданные в стандарте.Новый алгоритм, согласно отдельным исследованиям, до полутора раз быстрее предыдущего стандарта ГОСТ Р 34.11-94 за счет использоавния 27 тактов на один байт входного сообщения (94 МиБ/с) против 40 для старого стандарта (64 МиБ/с)

Реализации тестировались на процессоре Intel Core i7-920 CPU 2,67 GHz и видеокарте NVIDIA GTX 580. См. [58]..

В 2014 году группа исследователей ([100]) обнаружила недостаток в реализации конструкции HAIFA в хеш-функции «Стрибог», который ведёт к уменьшению сложности атаки по поиску второго прообраза до $n \times 2^{n/2}$, то есть до $2^{266}$. Авторы работы получили первую премию в размере пятисот тысяч рублей на конкурсе по исследованию хеш-функции «Стрибог», проводившемся Российским Техническим комитетом по стандартизации «Криптографическая защита информации» (ТК 26) при участии Академии криптографии Российской Федерации и при организационной и финансовой поддержке ОАО «ИнфоТеКС».