ГОСТ Р 34.11-94

ГОСТ Р34.11-94 — российский криптографический стандарт вычисления хеш-функции.

• Дата введения: 23 мая 1994 года
• Размер хеша: 256 бит
• Размер блока входных данных: 256 бит
• Разработчик: ГУБС ФАПСИ и Всероссийский научно-исследовательский институт стандартизации

Стандарт определяет алгоритм и процедуру вычисления хеш-функции для последовательности символов. Этот стандарт является обязательным для применения в качестве алгоритма хеширования в государственных организациях РФ и ряде коммерческих организаций.

ЦБ РФ требует использовать ГОСТ Р 34.11-94 для электронной подписи предоставляемых ему документов.

Вводные обозначения

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

• ${\mathcal {f}}0{\mathcal {g}}^{j}$ — блок длиной j бит, заполненный нулями.
• ${\mathcal {j}}M{\mathcal {j}}$ — длина блока M в битах по модулю 2²⁵⁶.
• ${\mathcal {k}}$ — слияние (конкатенация) двух блоков в один.
• $+$ — сложение двух блоков длиной 256 бит по модулю 2²⁵⁶
• $\oplus$ — побитное сложение (XOR) двух блоков одинаковой длины.

Далее будем считать, что младший (нулевой) бит в блоке находится справа, старший — слева.

Описание

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

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

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

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

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

h — значение хеш-функции сообщения M

Алгоритм

1. Инициализация:
   1. $h\ :=H_{1}$ — Начальное значение хеш-функции. То есть — 256 битовый IV вектор, определяется пользователем.
   2. $\Sigma \ :=\ 0$ — Контрольная сумма
   3. $L\ :=\ 0$ — Длина сообщения
2. Функция сжатия внутренних итераций: для i = 1 … n — 1 выполняем следующее (пока $|M|>256$):
   1. $h\ :=\ f(h,\ m_{i})$ — итерация метода последовательного хеширования
   2. $L\ :=\ L\ +\ 256$ — итерация вычисления длины сообщения
   3. $\Sigma \ :=\ \Sigma \ +\ m_{i}$ — итерация вычисления контрольной суммы
3. Функция сжатия финальной итерации:
   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 )$
4. Выход. Значением хеш-функции является h,

Замечание: так как длина сообщения участвует в хешировании, то нет необходимости указывать в передаваемом сообщении количество добавленных нулей к блоку $m_{n}$.

Особенности ГОСТ Р 34.11-94

• При обработке блоков используются преобразования по алгоритму ГОСТ 28147—89;
• Обрабатывается блок длиной 256 бит, и выходное значение тоже имеет длину 256 бит.
• Применены меры борьбы против поиска коллизий, основанном на неполноте последнего блока.
• Обработка блоков происходит по алгоритму шифрования ГОСТ 28147—89, который содержит преобразования на S-блоках, что существенно осложняет применение метода дифференциального криптоанализа к поиску коллизий.

Алгоритм вычисления шаговой функции хеширования

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

• Генерирование ключей $K_{1},\ K_{2},\ K_{3},\ K_{4}$
• Шифрующее преобразование — шифрование $\ H_{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}$ — подблоки блока Y длины 64 бит.
  • Преобразование $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,\ i=0,\dots ,3,\ k=1,\dots ,8$, а $y_{32},\ y_{31},\ \dots ,\ y_{1}$ — подблоки блока Y длины 8 бит.

• Три константы:

C2 = 0
C3 = 0xff00ffff000000ffff0000ff00ffff0000ff00ff00ff00ffff00ff00ff00ff00
C4 = 0

Алгоритм:

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

Для описания процесса преобразования сначала необходимо определить функцию ψ, которая производит элементарное преобразование блока длиной 256 бит в блок той же длины: $\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}$, где $y_{16},y_{15},...,y_{2},y_{1}$ — подблоки блока Y длины 16 бит.

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

Параметры алгоритма

Параметром используемого в качестве шифрующего преобразования $E(h,K)$ алгоритма ГОСТ 28147-89 является таблица из восьми узлов замены (S-блоков). ГОСТ Р 34.11-94 не фиксирует значения S-блоков и стартового вектора H₁, что породило несовместимые реализации хеш-функции.

Широкое распространение получили два набора параметров, полагающие стартовый вектор равным нулю:

H1=0x00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000,

но имеющие значения S-блоков, указанные ниже.

«Тестовый» набор S-блоков

В «приложении А» стандарта приводятся тестовые параметры, с рекомендацией использовать их только в указанных проверочных примерах. Тем не менее, они получили большое распространение. Например, они описаны в RFC 5831 и их использует в своих приложениях ЦБ РФ.

Номер 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-блоков компании CryptoPro

Российская компания CryptoPro написала собственный «информационный» RFC 4357. Согласно ему реализации ГОСТ Р 34.11-94 должны использовать набор S-блоков разработанный этой компанией. В известной открытой библиотеке OpenSSL начиная с версии 1.0.0 в качестве плагина появилась хеш функция ГОСТ Р 34.11-94 именно с этими параметрами.

Номер 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
2	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

Формат вывода

Согласно ГОСТ стандарту, результатом хеш-функции является 256-битное число. Стандарт не указывает, как оно должно выводиться. Разные реализации используют различные форматы вывода, что вкупе с двумя распространёнными S-блоками усиливает путаницу.

ГОСТ Р 34.11-94 в «приложении А» оперирует с Little-endian числами. Многие реализации (в частности rhash, mhash library, консольная утилита openssl) выводят 32 байта результирующего хеша в шестнадцаричном представлении, в порядке, в каком они располагаются в памяти — младшие байты первыми. Данное представление оправдывается тем, что оно же используется при выводе хеш сумм широко распространённых западных алгоритмов MD5, SHA1, Tiger, Whirlpool и др.

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

В приведённых в стандарте примерах, результирующий хеш записывается, как шестнадцатеричное представление 256-битного Little-endian числа. Тем самым, получается обратный порядок байт (старшие разряды первыми). Такой же порядок использует, в частности, программа gostsum поставляющяся с исходниками библиотеки OpenSSL.

H = FAFF37A6 15A81669 1CFF3EF8 B68CA247 E09525F3 9F811983 2EB81975 D366C4B1

Примеры

Подробный пример из стандарта

Вычислим хеш сообщения «This is message, length=32 bytes» с «тестовым» набором параметров.

Так как длина сообщения равна 256 битам, то нет необходимости дописывать нули. В шестнадцатеричном виде данное сообщение представляется последовательностью байт

54 68 69 73 20 69 73 20 6D 65 73 73 61 67 65 2C 20 6C 65 6E 67 74 68 3D 33 32 20 62 79 74 65 73

Эта последовательность рассматривается как Little-endian 256-битное число

 M = 0x73657479622032333D6874676E656C202C6567617373656D2073692073696854

Вычисляем $~H_{2}=f(H_{1},M)$:

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

K1=0x733D2C20 65686573 74746769 79676120 626E7373 20657369 326C6568 33206D54
K2=0x110C733D 0D166568 130E7474 06417967 1D00626E 161A2065 090D326C 4D393320
K3=0x80B111F3 730DF216 850013F1 C7E1F941 620C1DFF 3ABAE91A 3FA109F2 F513B239
K4=0xA0E2804E FF1B73F2 ECE27A00 E7B8C7E1 EE1D620C AC0CC5BA A804C05E A18B0AEC

• Шифрующее преобразование

S1=0x42ABBCCE 32BC0B1B
S2=0x5203EBC8 5D9BCFFD
S3=0x8D345899 00FF0E28
S4=0xE7860419 0D2A562D
S =0xE7860419 0D2A562D 8D345899 00FF0E28 5203EBC8 5D9BCFFD 42ABBCCE 32BC0B1B

• Перемешивающее преобразование

H2=0xCF9A8C65 505967A4 68A03B8C 42DE7624 D99C4124 883DA687 561C7DE3 3315C034

Вычисляем $~H_{3}=f(H_{2},L)$:

L = 0x00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000100

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

K1=0xCF68D956 9AA09C1C 8C3B417D 658C24E3 50428833 59DE3D15 6776A6C1 A4248734
K2=0x8FCF68D9 809AAC9C 3C8C3B41 C7658C24 BB504288 2859DE3D 666676A6 B3A42487
K3=0x4E70CF97 3C8065A0 853C8CC4 57389A8C CABB50BD E3D7A6DE D1996788 5CB35B24
K4=0x584E70CF C53C8065 48853C8C 1657389A EDCABB50 78E3D7A6 EED19867 7F5CB35B

• Шифрующее преобразование

S =0x66B70F5E F163F461 468A9528 61D60593 E5EC8A37 3FD42279 3CD1602D DD783E86

• Перемешивающее преобразование

H3=0x2B6EC233 C7BC89E4 2ABC2692 5FEA7285 DD3848D1 C6AC997A 24F74E2B 09A3AEF7

Вычисляем $~H_{4}=f(H_{3},\Sigma \ )$:

$\Sigma \$ = 0x73657479622032333D6874676E656C202C6567617373656D2073692073696854

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

K1=0x5817F104 0BD45D84 B6522F27 4AF5B00B A531B57A 9C8FDFCA BB1EFCC6 D7A517A3
K2=0xE82759E0 C278D95E 15CC523C FC72EBB6 D2C73DA8 19A6CAC9 3E8440F5 C0DDB66A
K3=0x77483AD9 F7C29CAA EB06D1D7 641BCAD3 FBC3DAA0 7CB555F0 D4968080 0A9E56BC
K4=0xA1157965 2D9FBC9C 088C7CC2 46FB3DD2 7681ADCB FA4ACA06 53EFF7D7 C0748708

• Шифрующее преобразование

S =0x2AEBFA76 A85FB57D 6F164DE9 2951A581 C31E7435 4930FD05 1F8A4942 550A582D

• Применяя перемешивающее преобразование, получаем результат хеширования:

H4=0xFAFF37A6 15A81669 1CFF3EF8 B68CA247 E09525F3 9F811983 2EB81975 D366C4B1

Данное Little-endian число в машинной памяти представляется строкой байт:

B1 C4 66 D3 75 19 B8 2E 83 19 81 9F F3 25 95 E0 47 A2 8C B6 F8 3E FF 1C 69 16 A8 15 A6 37 FF FA

В записи «младшие байты первыми» имеем

ГОСТ("This is message, length=32 bytes") = B1C466D37519B82E8319819FF32595E047A28CB6F83EFF1C6916A815A637FFFA

Второй пример из стандарта

В Big-endian представлении

M = 0x7365747962203035203D206874676E656C20736168206567617373656D206C616E696769726F206568742065736F70707553
H = 0x0852F5623B89DD57AEB4781FE54DF14EEAFBC1350613763A0D770AA657BA1A47

Этот-же пример в Little-endian

ГОСТ("Suppose the original message has length = 50 bytes") = 471ABA57A60A770D3A76130635C1FBEA4EF14DE51F78B4AE57DD893B62F55208

Другие примеры

Примеры в этом разделе приведены в little-endian представлении, используемом программами mhash, RHash, ReHash.

ГОСТ хеш с «тестовым» набором параметров

GOST ("") = CE85B99CC46752FFFEE35CAB9A7B0278ABB4C2D2055CFF685AF4912C49490F8D
GOST ("a") = D42C539E367C66E9C88A801F6649349C21871B4344C6A573F849FDCE62F314DD
GOST ("abc") = F3134348C44FB1B2A277729E2285EBB5CB5E0F29C975BC753B70497C06A4D51D
GOST ("message digest") = AD4434ECB18F2C99B60CBE59EC3D2469582B65273F48DE72DB2FDE16A4889A4D
GOST (128 символов "U") = 53A3A3ED25180CEF0C1D85A074273E551C25660A87062A52D926A9E8FE5733A4
GOST (1000000 символов "a") = 5C00CCC2734CDD3332D3D4749576E3C1A7DBAF0E7EA74E9FA602413C90A129FA

Малейшее изменение сообщения в подавляющем большинстве случаев приводит к совершенно другому хешу вследствие лавинного эффекта. К примеру, при изменении в следующей фразе dog на cog получится:

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

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

Набор параметров CryptoPro

GOST("") = 981E5F3CA30C841487830F84FB433E13AC1101569B9C13584AC483234CD656C0
GOST("a") = E74C52DD282183BF37AF0079C9F78055715A103F17E3133CEFF1AACF2F403011
GOST("abc") = B285056DBF18D7392D7677369524DD14747459ED8143997E163B2986F92FD42C
GOST("message digest") = BC6041DD2AA401EBFA6E9886734174FEBDB4729AA972D60F549AC39B29721BA0
GOST("The quick brown fox jumps over the lazy dog") =
  9004294A361A508C586FE53D1F1B02746765E71B765472786E4770D565830A76
GOST("This is message, length=32 bytes") =
  2CEFC2F7B7BDC514E18EA57FA74FF357E7FA17D652C75F69CB1BE7893EDE48EB
GOST("Suppose the original message has length = 50 bytes") =
  C3730C5CBCCACF915AC292676F21E8BD4EF75331D9405E5F1A61DC3130A65011
GOST(128 символов "U") = 1C4AC7614691BBF427FA2316216BE8F10D92EDFD37CD1027514C1008F649C4E8
GOST(1000000 символов "a") = 8693287AA62F9478F7CB312EC0866B6C4E4A0F11160441E8F4FFCD2715DD554F

Оценка криптостойкости

В 2008 году командой экспертов из Австрии и Польши была обнаружена техническая уязвимость, сокращающая поиск коллизий в 2²³ раз. Количество операций, необходимое для нахождения коллизии, таким образом, составляет 2¹⁰⁵, что, однако, на данный момент практически не реализуемо. Проведение коллизионной атаки на практике имеет смысл только в случае цифровой подписи документов, причём если взломщик может изменять неподписанный оригинал.

Использование

Функция используется при реализации систем цифровой подписи на базе асимметричного криптоалгоритма по стандарту ГОСТ Р 34.10-2001. Сообщество российских разработчиков СКЗИ согласовало используемые в Интернет параметры ГОСТ Р 34.11-94, см. RFC 4357.

• Использование в сертификатах открытых ключей.
• Использование для защиты сообщений в S/MIME (Cryptographic Message Syntax, PKCS#7).
• Использование для защиты соединений в TLS (SSL, HTTPS, WEB).
• Использование для защиты сообщений в XML Signature (XML Encryption).
• Защита целостности Интернет адресов и имён (DNSSEC).

Ссылки

• Текст ГОСТ Р 34.11-94
• ГОСТ Р 34.11 — 94. Функция хеширования. Краткий анализ.
• Реализация алгоритма на языке C++ с комментариями
• Реализация алгоритма на языке C++ с потоками STL (Ultimate++)
• Реализация алгоритма хэширования на JavaScript (вариант с параметрами CryptoPro)
• Реализация алгоритма на Oracle PL/SQL
• RHash — консольная Open source утилита, способная вычислять и проверять ГОСТ Р 34.11-94, поддерживает оба набора параметров и оба формата вывода.
• ГОСТы для OpenSSL  (неопр.). — криптографический проект компании ООО «Криптоком» по добавлению российских криптографических алгоритмов в библиотеку OpenSSL. Дата обращения: 16 ноября 2008.