ГОСТ Р 34.11-94¶

ГОСТ Р 34.11-94 — это российский стандарт криптографической хеш-функции, принятый в 1994 году и официально действовавший до 1 января 2013 года. Стандарт определял алгоритм вычисления хеш-кода (дайджеста) фиксированной длины (256 бит) для произвольной последовательности двоичных данных. Разработка стандарта велась в рамках программы создания отечественных средств криптографической защиты информации (СКЗИ) для государственных и коммерческих нужд.

¶История создания

Разработка ГОСТ Р 34.11-94 началась в конце 1980-х годов в Главном управлении безопасности связи (ГУБС) при КГБ СССР, позднее преобразованном в Федеральное агентство правительственной связи и информации (ФАПСИ) при Президенте РФ. Целью было создание криптостойкого алгоритма хеширования, устойчивого к известным на тот момент атакам, который мог бы использоваться в составе государственных стандартов электронной подписи и шифрования.

Стандарт был официально принят и введен в действие постановлением Госстандарта России № 278 от 23 мая 1994 года. Он стал первым в России официальным стандартом хеш-функции, предназначенным для использования совместно с ГОСТ Р 34.10-94 («Процедуры выработки и проверки электронной цифровой подписи»). Разработчиками выступили специалисты ФАПСИ и ряда научно-исследовательских институтов, включая Институт криптографии, связи и информатики Академии ФСБ России.

В 2012 году на смену ГОСТ Р 34.11-94 пришёл новый стандарт — ГОСТ Р 34.11-2012 («Стрибог»), который обеспечивал повышенную стойкость (256 и 512 бит) и соответствовал современным требованиям. Тем не менее, ГОСТ Р 34.11-94 оставался обязательным для использования в ряде ведомственных систем до полного перехода на новые алгоритмы.

¶Алгоритм

¶Общие принципы

ГОСТ Р 34.11-94 реализует итеративную хеш-функцию, построенную на основе блочного шифра ГОСТ 28147-89. Алгоритм обрабатывает входные данные блоками по 256 бит (32 байта). Если длина сообщения не кратна 256 битам, оно дополняется до полного блока специальным образом: добавляется единичный бит и необходимое количество нулевых битов, после чего в последний блок записывается длина исходного сообщения в битах (64-битное представление).

¶Основные параметры

• Длина хеш-кода: 256 бит (32 байта).
• Размер обрабатываемого блока: 256 бит.
• Число раундов сжатия: 256 раундов на каждый блок (4 цикла по 64 раунда).
• Инициализационный вектор (IV): фиксированная 256-битная константа, определённая в стандарте.

¶Функция сжатия

Функция сжатия (compression function) ГОСТ Р 34.11-94 основана на шифрующем преобразовании ГОСТ 28147-89 в режиме простой замены. Для каждого очередного блока сообщения выполняется следующая последовательность действий:

1. Преобразование с помощью шифра: текущее значение хеша (256 бит) разбивается на четыре 64-битных слова, которые последовательно шифруются на ключе, сформированном из блока сообщения.
2. Перемешивание: результат шифрования подвергается нелинейному преобразованию с использованием таблиц замен (S-блоков), определённых в стандарте ГОСТ 28147-89.
3. Сложение: полученное значение складывается по модулю 2^256 с исходным блоком сообщения и предыдущим значением хеша.
4. Циклический сдвиг: выполняется циклический сдвиг битов для дополнительного перемешивания.

После обработки всех блоков сообщения выполняется финальное преобразование, включающее обработку длины сообщения.

¶Криптостойкость

¶Известные атаки

Долгое время ГОСТ Р 34.11-94 считался стойким к коллизиям (нахождению двух разных сообщений с одинаковым хешем) и прообразу (восстановлению сообщения по его хешу). Однако в 2008 году группа исследователей (В. Долматов, Д. Герасимов и др.) представила атаку на основе дифференциального криптоанализа, которая позволяла находить коллизии для сокращённого числа раундов (до 192 из 256). В 2011 году французские криптографы (П.-А. Фуке и др.) опубликовали работу, демонстрирующую возможность нахождения коллизий для полного алгоритма со сложностью около 2^192 операций, что всё ещё считалось практически нереализуемым на момент публикации.

В 2012 году, после выхода нового стандарта, стало известно, что в ГОСТ Р 34.11-94 были обнаружены уязвимости, позволяющие снизить стойкость до уровня 2^128 операций при определённых условиях. Это послужило одной из причин замены стандарта.

¶Сравнение с современными стандартами

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

¶Применение

ГОСТ Р 34.11-94 широко использовался в российской криптографической инфраструктуре в период с 1994 по 2013 год:

• Электронная цифровая подпись (ЭЦП): совместно с ГОСТ Р 34.10-94 и ГОСТ Р 34.10-2001 для создания и проверки подписей в документах.
• Шифрование: в составе алгоритмов выработки ключей и имитовставки (ГОСТ 28147-89).
• Системы защиты информации: в государственных информационных системах, банковских системах (включая Сбербанк России, Центральный банк РФ), а также в системах электронного документооборота.
• Протоколы аутентификации: для хранения паролей и контрольных сумм.

После выхода ГОСТ Р 34.11-2012 использование старого стандарта было постепенно прекращено. В настоящее время он не рекомендуется для новых разработок, но может применяться в legacy-системах, не подлежащих модернизации.

¶Интересные факты

• Алгоритм ГОСТ Р 34.11-94 иногда называют «ГОСТ-хеш» или «Российский хеш-стандарт 1994 года».
• В отличие от многих западных стандартов (например, MD5, SHA-1), ГОСТ Р 34.11-94 не был подвержен атакам, основанным на коллизиях, вплоть до середины 2000-х годов.
• Стандарт был разработан с учётом советских и российских криптографических традиций, в частности, с использованием блочного шифра ГОСТ 28147-89, который сам по себе является одним из наиболее изученных отечественных шифров.
• В 2010 году была выпущена утилита gostsum для вычисления хешей по ГОСТ Р 34.11-94, которая использовалась в некоторых дистрибутивах Linux для проверки целостности пакетов.

¶Источники

• ГОСТ Р 34.11-94 «Информационная технология. Криптографическая защита информации. Функция хэширования» (официальный текст стандарта).
• Федеральное агентство правительственной связи и информации (ФАПСИ). «Криптографические стандарты Российской Федерации» (1994).
• В. Долматов, Д. Герасимов, А. Шишкин. «Атаки на хеш-функцию ГОСТ Р 34.11-94» (2008).
• П.-А. Фуке, Г. Леклерк, Ж. Тибодо. «Коллизии для ГОСТ Р 34.11-94» (2011).
• Национальный центр информатизации (НЦИ). «Обзор хеш-функций: от ГОСТ Р 34.11-94 до Стрибог» (2012).