ГОСТ Р 34.11-94 — Википедия

ГОСТ Р 34.11-94
Создан	1994
Опубликован	23 мая 1994
Дата отмены	1 января 2013 года[1][2]
Преемник	ГОСТ Р 34.11-2012 «Стрибог», ДСТУ 7564:2014 «Kupyna»
Размер хеша	256 бит
Число раундов	1
Тип	хеш-функция

ГОСТ Р 34.11-94 «Информационная технология. Криптографическая защита информации. Функция хэширования» — устаревший российский криптографический стандарт вычисления хеш-функции, основанный на ГОСТ Р 34.10-94. В странах СНГ переиздан и используется как межгосударственный стандарт ГОСТ 34.311-95.

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

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

С 1 января 2013 года заменён РФ на ГОСТ Р 34.11-2012 «Стрибог»^[4], а с 1 июня 2019 года в странах СНГ на ГОСТ 34.11-2018^[5].

До 1 января 2022 года используется на Украине совместно с ДСТУ 4145-2002 для целей электронной цифровой подписи^[6].

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

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

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

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

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

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

После вычисления ${\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 — Контрольная сумма сообщения M: ${\displaystyle m_{1}+m_{2}+m_{3}+...+m_{n}}$

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

Алгоритм:

1. Инициализация:
   1. ${\displaystyle h\ :=H_{1}}$ — Начальное значение хеш-функции. То есть — 256 битовый IV вектор, определяется пользователем.
   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}\ :=\ {\mathcal {f}}0{\mathcal {g}}^{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. Выход. Значением хеш-функции является h,

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

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

Шаговая функция хеширования ${\displaystyle f}$ отображает два блока длиной 256 бит в один блок длиной 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}}$ — подблоки блока Y длины 64 бит.
  • Преобразование ${\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}}$ — подблоки блока Y длины 8 бит.
• Три константы:

C2 = 0 C3 = 0xff00ffff000000ffff0000ff00ffff0000ff00ff00ff00ffff00ff00ff00ff00 C4 = 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_{i}}$ (для ${\displaystyle i:=1,2,3,4}$), процедуру шифрования обозначим через E (Примечание: функция шифрования E по ГОСТ 28147 шифрует 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}}$.

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

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

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

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

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

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

OID: 1.2.643.2.2.30.0

Номер S-блока	Значение
	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
1	4	A	9	2	D	8	0	E	6	B	1	C	7	F	5	3
2	E	B	4	C	6	D	F	A	2	3	8	1	0	7	5	9
3	5	8	1	D	A	3	4	2	E	F	C	7	6	0	9	B
4	7	D	A	1	0	8	9	F	E	4	6	C	B	2	5	3
5	6	C	7	1	5	F	D	8	4	A	9	E	0	3	B	2
6	4	B	A	0	7	2	1	D	3	6	8	5	9	C	F	E
7	D	B	4	1	3	F	5	9	0	A	E	7	6	8	2	C
8	1	F	D	0	5	7	A	4	9	2	3	E	6	B	8	C

Эти узлы замены определены в «приложении А» стандарта ГОСТ Р 34.11-94 для целей тестирования^[7], с рекомендацией использовать их только в проверочных примерах. Тем не менее, они получили большое распространение. Например, они описаны в RFC 5831 и их использует в своих приложениях ЦБ РФ.^[8]

OID: 1.2.643.2.2.30.1

Номер S-блока	Значение
	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
1	A	4	5	6	8	1	3	7	D	C	E	0	9	2	B	F
2	5	F	4	0	2	D	B	9	1	7	6	3	C	E	A	8
3	7	F	C	E	9	4	1	0	3	B	5	2	6	A	8	D
4	4	A	7	C	0	F	2	8	E	1	6	5	D	B	9	3
5	7	6	4	B	9	C	2	A	1	8	0	E	F	D	3	5
6	7	6	2	4	D	9	F	0	A	1	5	B	8	E	C	3
7	D	E	4	1	7	0	5	A	3	C	8	F	6	2	9	B
8	1	3	A	9	5	B	4	F	8	6	7	E	D	0	2	C

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

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

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

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

В приведённых в стандарте примерах^[7] результирующий хеш записывается как шестнадцатеричное представление 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 

Вычисляем ${\displaystyle 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 

Вычисляем ${\displaystyle 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 809AA09C 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 

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

${\displaystyle \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 

Примеры^{[10][неавторитетный источник (обс.)]} в этом разделе приведены в 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 

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²³ раз.^[11][12] Количество операций, необходимое для нахождения коллизии, таким образом, составляет 2¹⁰⁵, что, однако, на данный момент практически не реализуемо. Проведение коллизионной атаки на практике имеет смысл только в случае цифровой подписи документов, причём, если взломщик может изменять неподписанный оригинал.

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

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

• Текст стандарта ГОСТ Р 34.11-94 «Информационная технология. Криптографическая защита информации. Функция хэширования»
• Текст стандарта ГОСТ 34.311-95 «Информационная технология. Криптографическая защита информации. Функция хэширования»
• ГОСТ Р 34.11 — 94. Функция хеширования. Краткий анализ.