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

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

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

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

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

Алгоритм [ править ]

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

Основные обозначения [ править ]

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

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

Далее считаем, что младший бит расположен слева от блока, а старший — справа.

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

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

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

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

\!H_{i+1}=f(H_{i},\,m_{i})

The $H_{1}$ значение может быть выбрано произвольно и обычно составляет $0^{256}$ .

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

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

The $h$ — искомое значение хеш-функции сообщения М.

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

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

Шаг хэш-функции [ править ]

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

Он состоит из трёх частей:

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

Генерация ключей [ править ]

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

Два преобразования 256-битных блоков:
- Трансформация $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}$ , где $y_{1},\,y_{2},\,y_{3},\,y_{4}$ являются 64-битными подблоками Y .
- Трансформация $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)}$ , где $\varphi (i+1+4(k-1))=8i+k,\quad i=0,\,\dots ,\,3,\quad k=1,\,\dots ,\,8$ , и $y_{32},\,y_{31},\,\dots ,\,y_{1}$ являются 8-битными подблоками Y .
Три константы:
- С ₂ = 0
- С ₃ = 0xff00ffff000000ffff0000ff00ffff0000ff00ff00ff00ffff00ff00ff00ff00
- С ₄ = 0

Алгоритм:

$U:=H_{\text{in}},\quad V:=m,\quad W:=U\ \oplus \ V,\quad K_{1}=P(W)$
Для j = 2, 3, 4 сделайте следующее:
$U:=A(U)\oplus C_{j},\quad V:=A(A(V)),\quad W:=U\oplus V,\quad K_{j}=P(W)$

Шифрование-преобразование [ править ]

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

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

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

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

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

Сначала мы определяем функцию ψ, выполняя LFSR на 256-битном блоке:

\psi (Y)=\psi (y_{16}{\mathcal {k}}y_{15}{\mathcal {k}}\ldots {\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}}\ldots {\mathcal {k}}y_{3}{\mathcal {k}}y_{2}

,

где $y_{16},y_{15},\ldots ,y_{2},y_{1}$ являются 16-битными субблоками Y .

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

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

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

H_{1}

= 0x00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 .

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

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

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

Номер S-box	Ценить
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-box [ править ]

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

Номер S-box	Ценить
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-значных шестнадцатеричных чисел.

Вот тестовые векторы для хеша ГОСТа с «параметрами теста»

GOST("The quick brown fox jumps over the lazy dog") =
 77b7fa410c9ac58a25f49bca7d0468c9296529315eaca76bd1a10f376d1f4294

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

GOST("The quick brown fox jumps over the lazy cog") =
 a3ebc4daaab78b0be131dab5737a7f67e602670d543521319150d2e14eeec445

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

GOST("This is message, length=32 bytes") =
 b1c466d37519b82e8319819ff32595e047a28cb6f83eff1c6916a815a637fffa

GOST("Suppose the original message has length = 50 bytes") =
 471aba57a60a770d3a76130635c1fbea4ef14de51f78b4ae57dd893b62f55208

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

GOST("") =
 ce85b99cc46752fffee35cab9a7b0278abb4c2d2055cff685af4912c49490f8d

GOST("a") =
 d42c539e367c66e9c88a801f6649349c21871b4344c6a573f849fdce62f314dd

GOST("message digest") =
 ad4434ecb18f2c99b60cbe59ec3d2469582b65273f48de72db2fde16a4889a4d

GOST( 128 characters of 'U' ) =
 53a3a3ed25180cef0c1d85a074273e551c25660a87062a52d926a9e8fe5733a4

GOST( 1000000 characters of 'a' ) =
 5c00ccc2734cdd3332d3d4749576e3c1a7dbaf0e7ea74e9fa602413c90a129fa

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

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

GOST("") = 981e5f3ca30c841487830f84fb433e13ac1101569b9c13584ac483234cd656c0

GOST("a") = e74c52dd282183bf37af0079c9f78055715a103f17e3133ceff1aacf2f403011

GOST("abc") = b285056dbf18d7392d7677369524dd14747459ed8143997e163b2986f92fd42c

GOST("message digest") =
  bc6041dd2aa401ebfa6e9886734174febdb4729aa972d60f549ac39b29721ba0

GOST("The quick brown fox jumps over the lazy dog") =
  9004294a361a508c586fe53d1f1b02746765e71b765472786e4770d565830a76

GOST("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") =
  73b70a39497de53a6e08c67b6d4db853540f03e9389299d9b0156ef7e85d0f61

GOST("12345678901234567890123456789012345678901234567890123456789012345678901234567890") =
  6bc7b38989b28cf93ae8842bf9d752905910a7528a61e5bce0782de43e610c90

GOST("This is message, length=32 bytes") =
  2cefc2f7b7bdc514e18ea57fa74ff357e7fa17d652c75f69cb1be7893ede48eb

GOST("Suppose the original message has length = 50 bytes") =
  c3730c5cbccacf915ac292676f21e8bd4ef75331d9405e5f1a61dc3130a65011

GOST(128 of "U") = 1c4ac7614691bbf427fa2316216be8f10d92edfd37cd1027514c1008f649c4e8

GOST(1000000 of "a") = 8693287aa62f9478f7cb312ec0866b6c4e4a0f11160441e8f4ffcd2715dd554f

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

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

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

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

Долматов, В. (март 2010 г.). Долматов, В (ред.). «ГОСТ Р 34.11-94 - Алгоритм хеш-функции» . IETF. дои : 10.17487/RFC5831 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
«Информационные технологии. Криптографическая безопасность данных. Функция хеширования» . 20 февраля 2010 г. Полный текст ГОСТ Р 34.11-94 (на русском языке).

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

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

[gost-2008-1] Jump up to: Перейти обратно: ^а ^б Мендель, Флориан; Прамсталлер, Норберт; Рехбергер, Кристиан; Контак, Марцин; Шмидт, Януш (2008). «Криптоанализ хеш-функции ГОСТ». В Вагнере, Дэвид (ред.). Достижения в криптологии – КРИПТО 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 - Хэш-функция Стрибог.

[gost-94-addition-A-3] Jump up to: Перейти обратно: ^а ^б «Стандарт ГОСТ Р 34.11-94. Информационные технологии. Криптографическая защита информации. Функция хеширования. Дополнение А». 1994. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[1]

[2]

[3]