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

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

Эту функцию не следует путать с другой хэш-функцией Streebog , которая определена в новой редакции стандарта ГОСТ Р 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 двух блоков

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

Описание [ править ]

Входное сообщение разбивается на блоки по 256 бит . В случае, если последний блок содержит менее 256 бит, перед ним добавляются нулевые биты для достижения желаемой длины.${\ displaystyle M}$${\ 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}$

Каждый блок сообщения, начиная с первого, обрабатывается пошаговой хеш-функцией , чтобы вычислить промежуточное значение хеш-функции . Значение может быть выбрано произвольно, и обычно это так .${\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}}$

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

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

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}$

Пошаговая хеш-функция [ править ]

Хэш - функция шага отображает два 256-битовых блоков в один: . Он состоит из трех частей:${\displaystyle f}$${\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-битных блоков:
  • Преобразование , где являются 64-разрядными суб-блоки Y .${\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}}$
  • Преобразование , где и являются 8-битные суб-блоки 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}}$
• Три константы:
  • С ₂ = 0
  • C ₃ = 0xff00ffff000000ffff0000ff00ffff0000ff00ff00ff00ffff00ff00ff00ff00
  • С ₄ = 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)}$

Преобразование шифрования [ править ]

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

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

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

Сначала мы определим функцию ф, делая LFSR на 256-битовый блоке в: , где находятся 16-разрядные суб-блоки Y .${\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}}$

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

Начальные значения [ править ]

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

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

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

S-блок "Параметры теста" [ править ]

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

КриптоПро S-box [ править ]

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

Криптоанализ [ править ]

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

Векторы хеш-тестов ГОСТ [ править ]

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

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

ГОСТ ( «быстрая коричневая лиса прыгает через ленивый г OG») = 77b7fa410c9ac58a25f49bca7d0468c9296529315eaca76bd1a10f376d1f4294

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

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

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

ГОСТ («Это сообщение, длина = 32 байта») = b1c466d37519b82e8319819ff32595e047a28cb6f83eff1c6916a815a637fffaГОСТ («Предположим, что исходное сообщение имеет длину = 50 байт») = 471aba57a60a770d3a76130635c1fbea4ef14de51f78b4ae57dd893b62f55208

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

ГОСТ ("") = ce85b99cc46752fffee35cab9a7b0278abb4c2d2055cff685af4912c49490f8dГОСТ ("а") = d42c539e367c66e9c88a801f6649349c21871b4344c6a573f849fdce62f314ddГОСТ ("дайджест сообщения") = ad4434ecb18f2c99b60cbe59ec3d2469582b65273f48de72db2fde16a4889a4dГОСТ (128 знаков 'U') = 53a3a3ed25180cef0c1d85a074273e551c25660a87062a52d926a9e8fe5733a4ГОСТ (1000000 знаков 'а') = 5c00ccc2734cdd3332d3d4749576e3c1a7dbaf0e7ea74e9fa602413c90a129fa

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

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

ГОСТ ("") = 981e5f3ca30c841487830f84fb433e13ac1101569b9c13584ac483234cd656c0ГОСТ ("а") = e74c52dd282183bf37af0079c9f78055715a103f17e3133ceff1aacf2f403011ГОСТ ("abc") = b285056dbf18d7392d7677369524dd14747459ed8143997e163b2986f92fd42cГОСТ ("дайджест сообщения") = bc6041dd2aa401ebfa6e9886734174febdb4729aa972d60f549ac39b29721ba0ГОСТ («Быстрая коричневая лисица перепрыгивает через ленивую собаку») = 9004294a361a508c586fe53d1f1b02746765e71b765472786e4770d565830a76ГОСТ ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") = 73b70a39497de53a6e08c67b6d4db853540f03e9389299d9b0156ef7e85d0f61ГОСТ («12345678901234567890123456789012345678901234567890123456789012345678901234567890») = 6bc7b38989b28cf93ae8842bf9d752905910a7528a61e5bce0782de43e610c90ГОСТ («Это сообщение, длина = 32 байта») = 2cefc2f7b7bdc514e18ea57fa74ff357e7fa17d652c75f69cb1be7893ede48ebГОСТ («Предположим, что исходное сообщение имеет длину = 50 байт») = c3730c5cbccacf915ac292676f21e8bd4ef75331d9405e5f1a61dc3130a65011ГОСТ (128 "У") = 1c4ac7614691bbf427fa2316216be8f10d92edfd37cd1027514c1008f649c4e8ГОСТ (1000000 от "а") = 8693287aa62f9478f7cb312ec0866b6c4e4a0f11160441e8f4ffcd2715dd554f

См. Также [ править ]

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

Ссылки [ править ]

Дальнейшее чтение [ править ]

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

Внешние ссылки [ править ]

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