ГОСТ (хеш-функция) - GOST (hash function)

ГОСТ Р 34.11-94

Общий
Дизайнеров	ФАПСИ и ВНИИстандарт (СССР )
Впервые опубликовано	1994-05-23 (рассекречено)
Происходит от	Блочный шифр ГОСТ
Преемники	Стрибог
Сертификация	ГОСТ ГОСТ
Деталь
Размеры дайджеста	256 бит
Раундов	32
Лучшая публика криптоанализ
Атака 2008 года нарушает хеш-функцию полного цикла. В статье представлена столкновение через 2^105 время и атака на прообраз через 2^192 время.[1]

В Хеш-функция ГОСТ, определенные в стандартах ГОСТ Р 34.11-94 и ГОСТ 34.311-95 256-битный криптографическая хеш-функция. Первоначально он был определен в российском национальном стандарте. ГОСТ Р 34.11-94 Информационные технологии - Криптографическая информационная безопасность - Хеш-функция. Эквивалентный стандарт, используемый другими государствами-членами СНГ ГОСТ 34.311-95.

Эту функцию не следует путать с другим Стрибог хэш-функция, которая определена в новой редакции стандарта ГОСТ Р 34.11-2012.^[2]

Хеш-функция ГОСТ основана на Блочный шифр ГОСТ.

Алгоритм

ГОСТ преобразует сообщение переменной длины в выходной файл фиксированной длины в 256 бит. Входное сообщение разбивается на части по 256-битных блоков (восемь 32-битных прямой порядок байтов целые числа); сообщение мягкий добавляя к нему столько нулей, сколько требуется для увеличения длины сообщения до 256 бит. Остальные биты заполняются 256-битной целочисленной арифметической суммой всех ранее хешированных блоков, а затем 256-битным целым числом, представляющим длину исходного сообщения в битах.

Основные обозначения

В описании алгоритма используются следующие обозначения:

• ${\displaystyle {\mathcal {f}}0{\mathcal {g}}^{j}}$ - j-битовый блок, заполненный нулями.
• ${\displaystyle {\mathcal {j}}M{\mathcal {j}}}$ - длина блока M в битах по модулю 2²⁵⁶.
• ${\displaystyle {\mathcal {k}}}$ - соединение двух блоков.
• ${\displaystyle +}$ - арифметическая сумма двух блоков по модулю 2²⁵⁶
• ${\displaystyle \oplus }$ - логический xor двух блоков

Далее мы считаем, что бит младшего разряда расположен слева от блока, а бит старшего разряда - справа.

Описание

Входное сообщение ${\displaystyle M}$ разбивается на 256-битные блоки ${\displaystyle m_{n},m_{n-1},m_{n-2},...,m_{1}}$.В случае, если последний блок ${\displaystyle m_{n}}$ содержит менее 256 бит, слева к нему добавляются нулевые биты для достижения желаемой длины.

Каждый блок обрабатывается пошаговой хеш-функцией ${\displaystyle H_{out}\ =\ f(H_{in},m)}$,куда ${\displaystyle H_{out}}$, ${\displaystyle H_{in}}$, ${\displaystyle m}$ представляют собой 256-битные блоки.

Каждый блок сообщения, начиная с первого, обрабатывается пошаговой хеш-функцией. ${\displaystyle f}$, чтобы вычислить промежуточное значение хеш-функции
${\displaystyle \!H_{i+1}=f(H_{i},m_{i})}$
В ${\displaystyle H_{1}}$ значение может быть выбрано произвольно и обычно равно ${\displaystyle 0^{256}}$.

После ${\displaystyle H_{n+1}}$ рассчитывается, окончательное значение хеш-функции получается следующим образом

• ${\displaystyle H_{n+2}\ =\ f(H_{n+1},\ L)}$, где L - длина сообщения M в битах по модулю ${\displaystyle 2^{256}}$
• ${\displaystyle h\ =\ f(H_{n+2},\ K)}$, где K - 256-битная контрольная сумма M: ${\displaystyle m_{1}+m_{2}+m_{3}+...+m_{n}}$

В ${\displaystyle h}$ - желаемое значение хэш-функции сообщения M.

Итак, алгоритм работает следующим образом.

1. Инициализация:
   1. ${\displaystyle h\ :=initial}$ - Начальное 256-битное значение хеш-функции, определяемое пользователем.
   2. ${\displaystyle \Sigma \ :=\ 0}$ - Контрольная сумма
   3. ${\displaystyle L\ :=\ 0}$ - Длина сообщения
2. Функция сжатия внутренних итераций: для i = 1… n - 1 выполните следующие действия (пока ${\displaystyle |M|>256}$):
   1. ${\displaystyle h\ :=\ f(h,\ m_{i})}$ - применить пошаговую хеш-функцию
   2. ${\displaystyle L\ :=\ L\ +\ 256}$ - пересчитать длину сообщения
   3. ${\displaystyle \Sigma \ :=\ \Sigma \ +\ m_{i}}$ - рассчитать контрольную сумму
3. Функция сжатия последней итерации:
   1. ${\displaystyle L\ :=\ L\ +\ {\mathcal {j}}\ m_{n}\ {\mathcal {j}}}$ - вычислить полную длину сообщения в битах
   2. ${\displaystyle m_{n}\ :=\ {0}^{256\ -\ {\mathcal {j}}m_{n}{\mathcal {j}}}{\mathcal {k}}m_{n}}$ - дополнить последнее сообщение нулями
   3. ${\displaystyle \Sigma \ :=\ \Sigma \ +\ m_{n}}$ - обновить контрольную сумму
   4. ${\displaystyle h\ :=\ f(h,\ m_{n})}$ - обработать последний блок сообщения
   5. ${\displaystyle h\ :=\ f(h,\ L)}$ - MD - усилить за счет хеширования длины сообщения
   6. ${\displaystyle h\ :=\ f(h,\ \Sigma )}$ - контрольная сумма хеша
4. Выходное значение ${\displaystyle h}$.

Пошаговая хеш-функция

Пошаговая хеш-функция ${\displaystyle f}$ отображает два 256-битных блока в один: ${\displaystyle H_{out}\ =\ f(H_{in},\ m)}$Состоит из трех частей:

• Генерация ключей ${\displaystyle K_{1},\ K_{2},\ K_{3},\ K_{4}}$
• Преобразование шифрования ${\displaystyle \ H_{in}}$ используя ключи ${\displaystyle K_{1},\ K_{2},\ K_{3},\ K_{4}}$
• Преобразование в случайном порядке

Генерация ключей

В алгоритме генерации ключей используются:

• Два преобразования 256-битных блоков:
  • Трансформация ${\displaystyle A(Y)=A(y_{4}\ {\mathcal {k}}\ y_{3}\ {\mathcal {k}}\ y_{2}\ {\mathcal {k}}\ y_{1})=(y_{1}\oplus y_{2})\ {\mathcal {k}}\ y_{4}\ {\mathcal {k}}\ y_{3}\ {\mathcal {k}}\ y_{2}}$, куда ${\displaystyle y_{1},\ y_{2},\ y_{3},\ y_{4}}$ 64-битные подблоки Y.
  • Трансформация ${\displaystyle P(Y)=P(y_{32}{\mathcal {k}}y_{31}{\mathcal {k}}\dots {\mathcal {k}}y_{1})=y_{\varphi (32)}{\mathcal {k}}y_{\varphi (31)}{\mathcal {k}}\dots {\mathcal {k}}y_{\varphi (1)}}$, куда ${\displaystyle \varphi (i+1+4(k-1))=8i+k,\ i=0,\dots ,3,\ k=1,\dots ,8}$, и ${\displaystyle y_{32},\ y_{31},\ \dots ,\ y_{1}}$ 8-битные подблоки Y.
• Три константы:
  • C₂ = 0
  • C₃ = 0xff00ffff000000ffff0000ff00ffff0000ff00ff00ff00ffff00ff00ff00ff00
  • C₄ = 0

Алгоритм:

1. ${\displaystyle U\ :=\ H_{in},\quad V\ :=\ m,\quad W\ :=\ U\ \oplus \ V,\quad K_{1}\ =\ P(W)}$
2. За j = 2,3,4 выполните следующие действия:

   ${\displaystyle U:=A(U)\oplus C_{j},\quad V:=A(A(V)),\quad W:=U\oplus V,\quad K_{j}=P(W)}$

Преобразование шифрования

После генерации ключей шифрование ${\displaystyle H_{in}}$ делается с использованием ГОСТ 28147-89 в режиме простой подстановки на ключи ${\displaystyle K_{1},K_{2},K_{3},K_{4}}$Обозначим преобразование шифрования как E (Примечание: преобразование E шифрует 64-битные данные с использованием 256-битного ключа). Для шифрования ${\displaystyle H_{in}}$ разбит на четыре 64-битных блока: ${\displaystyle H_{in}=h_{4}{\mathcal {k}}h_{3}{\mathcal {k}}h_{2}{\mathcal {k}}h_{1}}$, и каждый из этих блоков зашифрован как:

• ${\displaystyle s_{1}=E(h_{1},K_{1})}$
• ${\displaystyle s_{2}=E(h_{2},K_{2})}$
• ${\displaystyle s_{3}=E(h_{3},K_{3})}$
• ${\displaystyle s_{4}=E(h_{4},K_{4})}$

После этого блоки результатов объединяются в один 256-битный блок: ${\displaystyle S=s_{4}{\mathcal {k}}s_{3}{\mathcal {k}}s_{2}{\mathcal {k}}s_{1}}$.

Преобразование в случайном порядке

На последнем шаге преобразование перемешивания применяется к ${\displaystyle H_{in}}$, S и m с помощью Регистр сдвига с линейной обратной связью. В результате промежуточное значение хеш-функции ${\displaystyle H_{out}}$ получается.

Сначала мы определяем ψ-функцию, выполняя LFSR на 256-битном блоке: ${\displaystyle \psi (Y)=\psi (y_{16}{\mathcal {k}}y_{15}{\mathcal {k}}...{\mathcal {k}}y_{2}{\mathcal {k}}y_{1})=(y_{1}\oplus y_{2}\oplus y_{3}\oplus y_{4}\oplus y_{13}\oplus y_{16}){\mathcal {k}}y_{16}{\mathcal {k}}y_{15}{\mathcal {k}}...{\mathcal {k}}y_{3}{\mathcal {k}}y_{2}}$, куда ${\displaystyle y_{16},y_{15},...,y_{2},y_{1}}$ являются 16-битными подблоками Y.

Преобразование в случайном порядке ${\displaystyle H_{out}={\psi }^{61}(H_{in}\oplus \psi (m\oplus {\psi }^{12}(S)))}$, куда ${\displaystyle {\psi }^{i}}$ обозначает i-ю степень ${\displaystyle \psi }$ функция.

Начальные значения

Для ГОСТ Р 34.11 94 обычно используются два набора начальных параметров. Начальный вектор для обоих наборов равен

${\displaystyle H_{1}}$= 0x00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000.

Хотя сам стандарт ГОСТ Р 34.11 94 не определяет начальное значение алгоритма. ${\displaystyle H_{1}}$ и S-коробка преобразования шифрования ${\displaystyle E}$, но использует следующие «параметры теста» в разделах примеров.^[3]

S-бокс "Параметры теста"

RFC 5831 указывает только эти параметры, но RFC 4357 называет их «тестовыми параметрами» и не рекомендует использовать их в производственных приложениях.

Номер S-бокса	Ценить
1	4	10	9	2	13	8	0	14	6	11	1	12	7	15	5	3
2	14	11	4	12	6	13	15	10	2	3	8	1	0	7	5	9
3	5	8	1	13	10	3	4	2	14	15	12	7	6	0	9	11
4	7	13	10	1	0	8	9	15	14	4	6	12	11	2	5	3
5	6	12	7	1	5	15	13	8	4	10	9	14	0	3	11	2
6	4	11	10	0	7	2	1	13	3	6	8	5	9	12	15	14
7	13	11	4	1	3	15	5	9	0	10	14	7	6	8	2	12
8	1	15	13	0	5	7	10	4	9	2	3	14	6	11	8	12

КриптоПро S-бокс

КриптоПро S-коробка исходит из набора параметров «готово к производству», разработанного компанией CryptoPro, он также указан как часть RFC 4357, раздел 11.2.

Номер S-бокса	Ценить
1	10	4	5	6	8	1	3	7	13	12	14	0	9	2	11	15
2	5	15	4	0	2	13	11	9	1	7	6	3	12	14	10	8
3	7	15	12	14	9	4	1	0	3	11	5	2	6	10	8	13
4	4	10	7	12	0	15	2	8	14	1	6	5	13	11	9	3
5	7	6	4	11	9	12	2	10	1	8	0	14	15	13	3	5
6	7	6	2	4	13	9	15	0	10	1	5	11	8	14	12	3
7	13	14	4	1	7	0	5	10	3	12	8	15	6	2	9	11
8	1	3	10	9	5	11	4	15	8	6	7	14	13	0	2	12

Криптоанализ

В 2008 году была опубликована атака, которая нарушает полноценную хеш-функцию ГОСТ. В статье представлена столкновение через 2¹⁰⁵ время, и первое и второе атака на прообраз через 2¹⁹² время (2^п время относится к приблизительному количеству вычислений алгоритма при атаке).^[1]

ГОСТ хэш-тестовые векторы

Хеши для "тестовых параметров"

256-битные (32-байтовые) хэши ГОСТ обычно представлены в виде 64-значных шестнадцатеричных чисел. Вот тестовые векторы для хэша ГОСТ с «параметрами теста».

ГОСТ («Быстрая коричневая лиса прыгает через ленивого dog ") = 77b7fa410c9ac58a25f49bca7d0468c9296529315eaca76bd1a10f376d1f4294

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

ГОСТ («Быстрая коричневая лиса прыгает через ленивого cog ") = a3ebc4daaab78b0be131dab5737a7f67e602670d543521319150d2e14eeec445

Два образца по ГОСТ Р 34.11-94:^[3]

GOST («Это сообщение, длина = 32 байта») = b1c466d37519b82e8319819ff32595e047a28cb6f83eff1c6916a815a637fffa

Еще тестовые векторы:

ГОСТ ( "") = ce85b99cc46752fffee35cab9a7b0278abb4c2d2055cff685af4912c49490f8dGOST ( "A") = d42c539e367c66e9c88a801f6649349c21871b4344c6a573f849fdce62f314ddGOST ( "дайджеста сообщения") = ad4434ecb18f2c99b60cbe59ec3d2469582b65273f48de72db2fde16a4889a4dGOST (128 символов 'U') = 53a3a3ed25180cef0c1d85a074273e551c25660a87062a52d926a9e8fe5733a4GOST (1000000 символов 'а') = 5c00ccc2734cdd3332d3d4749576e3c1a7dbaf0e7ea74e9fa602413c90a129fa

Хеши для параметров КриптоПро

Алгоритм ГОСТ с КриптоПро S-box генерирует другой набор хеш-значений.

= 981e5f3ca30c841487830f84fb433e13ac1101569b9c13584ac483234cd656c0

ГОСТ ( "а") = e74c52dd282183bf37af0079c9f78055715a103f17e3133ceff1aacf2f403011GOST ( "а") = b285056dbf18d7392d7677369524dd14747459ed8143997e163b2986f92fd42cGOST ( "дайджест сообщение") = bc6041dd2aa401ebfa6e9886734174febdb4729aa972d60f549ac39b29721ba0GOST ( "быстрая коричневая лиса прыгает через ленивую собаку") = 9004294a361a508c586fe53d1f1b02746765e71b765472786e4770d565830a76GOST ( "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") = 73b70a39497de53a6e08c67b6d4db853540f03e9389299d9b0156ef7e85d0f61GOST ( "12345678901234567890123456789012345678901234567890123456789012345678901234567890") = 6bc7b38989b28cf93ae8842bf9d752905910a7528a61e5bce0782de43e610c90GOST ( "Это сообщение, длина = 32 байта") = 2cefc2f7b7bdc514e18ea57fa74ff357e7fa17d652c75f69cb1be7893ede48ebGOST ( "Предположим, что исходное сообщение имеет длину 50 байт =") = c3730c5cbccacf915ac292676f21e8bd4ef75331d9405e5f1a61dc3130a65011GOST (128 "U") = 1c4ac7614691bbf427fa2316216be8f10d92edfd37cd1027514c1008f649c4e8GOST (1000000 от "а") = 869 3287aa62f9478f7cb312ec0866b6c4e4a0f11160441e8f4ffcd2715dd554f

Смотрите также

• Купына
• Сводка по безопасности хеш-функции
• Стандарты ГОСТ
• Список хэш-функций

Рекомендации

1. Мендель, Флориан; Прамсталлер, Норберт; Рехбергер, Кристиан; Контакт, Марчин; Шмидт, Януш (2008). «Криптоанализ хеш-функции ГОСТ». В Вагнер, Давид (ред.). Достижения в криптологии - CRYPTO 2008. Конспект лекций по информатике. 5157. Германия: Springer Berlin Heidelberg. С. 162–178. Дои:10.1007/978-3-540-85174-5_10. ISBN  978-3-540-85173-8.
2. ГОСТ Р 34.11-2012 - Хеш-функция Стрибога.
3. «Стандарт ГОСТ Р 34.11-94. Информационные технологии. Криптографическая защита данных. Функция хеширования. Дополнение А.» 1994.

дальнейшее чтение

• «ГОСТ Р 34.11-94 - Алгоритм хеш-функции». IETF. Март 2010 г.
• «Информационные технологии. Криптографическая безопасность данных. Функция хеширования». 2010-02-20. Полный текст стандарта ГОСТ Р 34.11-94.

внешняя ссылка

• Реализация C и тестовые векторы для хэш-функции ГОСТ от Маркку-Юхани Сааринен также содержит проекты переводов на английский язык стандартов ГОСТ 28147-89 и ГОСТ Р 34.11-94. Версия с ошибкой, см. [1].
• Реализация C ++ с потоками STL^{[постоянная мертвая ссылка ]}.
• RHash, Открытый исходный код инструмент командной строки, который может вычислять и проверять хеш-код ГОСТ (поддерживает оба набора параметров).
• Внедрение ГОСТ Р 34.11-94 в г. JavaScript (Параметры КриптоПро )
• Страница ГОСТ Хэш-функция Ecrypt
• Калькулятор ГОСТ