WikiSort.ru - Не сортированное

ГОСТ Р 34.11-2012 «Информационная технология. Криптографическая защита информации. Функция хеширования» — действующий российский криптографический стандарт, определяющий алгоритм и процедуру вычисления хеш-функции. Разработан Центром защиты информации и специальной связи ФСБ России с участием ОАО «ИнфоТеКС» и введен в действие 1 января 2013 года.

Размер хеша — 256 или 512 бит; размер блока входных данных — 512 бит.

Стандарт определяет алгоритм и процедуру вычисления хеш-функции для последовательности символов. Этот стандарт разработан и введён в качестве замены устаревшему стандарту ГОСТ Р 34.11-94:

Необходимость разработки <…> вызвана потребностью в создании хеш-функции, соответствующей современным требованиям к криптографической стойкости и требованиям стандарта ГОСТ Р 34.10-2012 на электронную цифровую подпись.

— Текст стандарта. Введение.

Название хеш-функции — «Стрибог», по имени славянского божества, — часто используется вместо официального названия стандарта, хотя в его тексте явно не упоминается (см. ниже).

Концепции построения хеш-функции «Стрибог»

В соответствии с требованиями, высказанными на конференции РусКрипто-2010, в работе, посвящённой новой хеш-функции^[1]:

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

В той же работе вводятся «универсальные» требования, касающиеся трудоемкости атак на хеш-функцию:

Задача	Сложность
построение прообраза	${\displaystyle \gtrapprox }$ 2n
построение коллизии	${\displaystyle \gtrapprox }$ 2n/2
построение второго прообраза	${\displaystyle \gtrapprox }$ 2n/(длина сообщения)
удлинение прообраза	${\displaystyle \gtrapprox }$ 2n

Сравнение ГОСТ Р 34.11-2012 и ГОСТ Р 34.11-94

• В ГОСТ Р 34.11-2012 размер блоков сообщения и внутреннего состояния хеш-функции составляет 512 бит против 256 бит в ГОСТ Р 34.11-94.
• Новый стандарт определяет две функции хеширования с длинами хеш-кода 256 и 512 бит, в то время как в старом стандарте длина хеш-кода может быть только 256 бит. Возможность вариации выходного хеша может быть полезна в случае встроенных реализаций с ограниченными ресурсами или наличия каких-то дополнительных требований в области криптографии.
• Основное отличие современной хеш-функции от старой — функция сжатия. В ГОСТ Р 34.11-2012 используется функции сжатия, в основе которой лежат три преобразования: нелинейное биективное преобразование (обозначается S), перестановка байт (обозначается P), линейное преобразование (обозначается L). В ГОСТ Р 34.11-94 используется функция сжатия, основанная на симметричном блочном шифре ГОСТ Р 28147-89, также эта функция использует операции перемешивания.
• При вычислении новой хеш-функции, если размер сообщения не кратен размеру обрабатываемого блока (для современного стандарта — 512 бит, для старого стандарта — 256 бит), то такой блок дополняется вектором (00 … 01). При вычислении старой хеш-функции неполный блок дополняется значением (00 … 0). Считается, что дополнение (00 … 01) лучше, чем (00 … 0), с криптографической точки зрения, т.к. дополнения значением (00 … 0) приводит к атакам Оракула дополнения^[2]. В случае ненулевого дополнения была доказана стойкость к подобным атакам^[3].
• Ещё одно отличие состоит в том, что стандарт ГОСТ Р 34.11-94 не определял значение инициализационного вектора, в то время как в стандарте ГОСТ Р 34.11-2012 значение инициализационного вектора фиксировано и определено в стандарте: для хеш-функции с размером выходного хеша 512 бит это вектор (00 … 0), для хеш-функции с размером выходного хеш-кода 256 бит — (000000010 … 100000001) (все байты равны 1).

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

В хеш-функции важным элементом является функция сжатия. В ГОСТ Р 34.11-2012 функция сжатия основана на конструкции Миагути — Пренеля. Схема конструкции Миагути — Пренеля: h, m — вектора, поступающие на вход функции сжатия; g(h, m) — результат функции сжатия; E — блочный шифр с длиной блока и ключа 512 бит. В качестве блочного шифра в хеш-функции ГОСТ Р 34.11-2012 взят XSPL-шифр. Этот шифр состоит из следующих преобразований:

• сложение по модулю 2;
• преобразование замены или подстановки. Обозначается S-преобразование;
• преобразование перестановки. Обозначается P-преобразование;
• линейное преобразование. Обозначается L-преобразование.

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

Важным параметром блочного шифра является то, как выбирается ключ, который будет использовать на каждом раунде. В блочном шифре, используемом в ГОСТ Р 34.11-2012, ключи ${\displaystyle K_{1}}$ , ${\displaystyle K_{2}}$ , … , ${\displaystyle K_{13}}$ для каждого из 13 раундов генерируются с помощью самой функции шифрования.

${\displaystyle C_{1}}$ , ${\displaystyle C_{2}}$ , … , ${\displaystyle C_{12}}$  — итерационные константы, которые являются 512 битовыми векторам. Их значения указаны в соответствующем разделе стандарта.

Описание

В основу хеш-функции положена итерационная конструкция Меркла — Дамгора с использованием MD-усиления. Под MD-усилением понимается дополнение неполного блока при вычислении хеш-функции до полного путём добавления вектора (0 … 01) такой длины, чтобы получился полный блок. Из дополнительных элементов нужно отметить следующие:

• завершающее преобразование, которое заключается в том, что функция сжатия применяется к контрольной сумме всех блоков сообщения по модулю 2⁵¹²;
• при вычислении хеш-кода на каждой итерации применяются разные функции сжатия. Можно сказать, что функция сжатия зависит от номера итерации.

Описанные выше решения позволяют противостоять многим известным атакам.

Кратко описание хеш-функции ГОСТ Р 34.11-2012 можно представить следующим образом. На вход хеш-функции подается сообщение произвольного размера. Далее сообщение разбивается на блоки по 512 бит, если размер сообщения не кратен 512, то оно дополняется необходимым количеством бит. Потом итерационно используется функция сжатия, в результате действия которой обновляется внутреннее состояние хеш-функции. Также вычисляется контрольная сумма блоков и число обработанных бит. Когда обработаны все блоки исходного сообщения, производятся ещё два вычисления, которые завершают вычисление хеш-функции:

• обработка функцией сжатия блока с общей длиной сообщения.
• обработка функцией сжатия блока с контрольной суммой.

В работе Александра Казимирова и Валентины Казимировой^[4] приведена графическая иллюстрация вычисления хеш-функции.

Анализ

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

• В конце текста стандарта приведены примеры пошагового вычисления хеша для нескольких исходных значений. Одно из таких значений — шестнадцатеричное число M₂ длины 576 байт из примера 2. На ЭВМ архитектуры x86 используется метод Little endian, и подобное число в памяти будет представлено в «перевёрнутом» виде. Если преобразовать этот массив байт в текст по правилам кодировки Windows-1251, то получится: «Се ветри, Стрибожи внуци, веютъ с моря стрелами на храбрыя плъкы Игоревы», что является немного изменённой строчкой из Слова о полку Игореве.

Примечания

Ссылки

• Текст официального стандарта ГОСТ Р 34.11-2012 в Викитеке
• RFC 6986 GOST R 34.11-2012: Hash Function
• Algebraic Aspects of the Russian Hash Standard GOST R 34.11-2012, 2013
• Reverse-Engineering the S-Box of Streebog, Kuznyechik and STRIBOBr1 (Full Version), 2016

Для улучшения этой статьи желательно: Проверить достоверность указанной в статье информации. Исправить статью согласно стилистическим правилам Википедии. Викифицировать статью. Добавить иллюстрации.