ГОСТ Р 34.11-94

Материал из Википедии — свободной энциклопедии

Черновик [показать страницу] (сравнить)

Данная версия статьи не досматривалась участниками с соответствующими правами. Вы можете прочитать последнюю досмотренную версию от 20 февраля 2009, однако она может значительно отличаться от текущей версии. Проверки требуют 26 правок.

Перейти к: навигация, поиск

Криптографическая хеш-функция
Название	ГОСТ Р34.11-94
Разработчик	ГУБС ФАПСИ и ВНИИС
Создан	1994
Опубликован	Январь 1995
Размер хеша	256 бит
Число раундов	1
Тип	хеш-функция

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

Дата введения: 01 января 1995 г.
Размер хэша: 256 бит
Размер блока входных данных: 256 бит
Разработчик: ГУБС ФАПСИ и ВНИИС

Стандарт определяет алгоритм и процедуру вычисления хэш-функции для последовательности символов.

Содержание

1 Вводные обозначения
2 Описание
3 Алгоритм вычисления шаговой функции хэширования
4 Ряд отличительных особенностей ГОСТ Р 34.11-94
5 Оценка криптостойкости
6 Использование
7 Примеры хэшей
- 7.1 Подробный пример из описания стандарта
- 7.2 Другие примеры
8 Примечания
9 Ссылки

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

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

$\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 o u t$ , $H i n$ , $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 в битах по модулю $2256$
$h\ =\ f(H_{n+2},\ K)$ , где K — Контрольная сумма сообщения M: $m 1 + m 2 + m 3 + ... + m n$

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

Алгоритм:

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

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

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

Шаговая функция хэширования H отображает два блока длиной 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 бит.

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

C₂ = 0
C₃ = 0xff00ffff000000ffff0000ff00ffff0000ff00ff00ff00ffff00ff00ff00ff00
C₄ = 0

Алгоритм:

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

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

[править] Ряд отличительных особенностей ГОСТ Р 34.11-94

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

[править] Оценка криптостойкости

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

[править] Использование

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

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

[править] Примеры хэшей

В качестве шифрующего преобразования преобразования в приводимых ниже примерах используется алгоритм ГОСТ 28147-89 в режиме простой замены. При этом заполнение узлов замены (S-box) следующее:

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

В качестве стартового вектора взято нулевое значение, то есть

H₁=0x00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000.

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

 M = 0x73657479622032333D6874676E656C202C6567617373656D2073692073696854

Т.к. длина сообщения равна 256 битам, то нет необходимости дописывать нули. Вычисляем $~H_{2} = f(H_{1}, M)$ :

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

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

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

S₁=0x42ABBCCE 32BC0B1B
S₂=0x5203EBC8 5D9BCFFD
S₃=0x8D345899 00FF0E28
S₄=0xE7860419 0D2A562D
S =0xE7860419 0D2A562D 8D345899 00FF0E28 5203EBC8 5D9BCFFD 42ABBCCE 32BC0B1B

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

H₂=0xCF9A8C65 ?35967A4 68A03B8C 42DE7624 D99C4124 883DA687 561C7DE3 3315C034

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

L = 0x00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000100

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

K₁=0xCF68D956 9AA09C1C 8C3B417D 658C24E3 50428833 59DE3D15 6776A6C1 A4248734
K₂=0x8FCF68D9 809AAC9C 3C8C3B41 C7658C24 BB504288 2859DE3D 666676A6 B3A42487
K₃=0x4E70CF97 3C8065A0 853C8CC4 57389A8C CABB50BD E3D7A6DE D1936788 6CB35B24
K₄=0x584E70CF C53C8065 48853C8C 1657389A EDCABB50 78E3D7A6 EED19867 7F5CB35B

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

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

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

H₃=0x2B6EC233 C7BC89E4 2ABC2692 5FEA7285 DD3848D1 C6AC997 24F74E2B 09A3AEF7

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

 = 0x73657479622032333D6874676E656C202C6567617373656D2073692073696854

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

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

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

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

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

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

Таким образом, результат хэширования:

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

[править] Другие примеры

M = 0x7365747962203035203D206874676E656C20736168206567617373656D206C616E696769726F206568742065736F70707553
H = 0x0852F5623B89DD57AEB4781FE54DF14EEAFBC1350613763A0D770AA657BA1A47

M = ""
H = 0xBD298BCFCAFB398D76E3FC8FA0951679D6B57BD782AC7Bf13C03C6848A351D89

M = "ГОСТ Р 34.11-94"
H = 0xB6A83547677B534FEDB3C68BC7207129F7454928554CF2847DD7E30165F1CF30

M = "The quick brown fox jumps over the lazy dog"
H = 0x94421F6D370FA1D16BA7AC5E31296529C968047DCA9BF4258AC59A0C41FAB777

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

M = "The quick brown fox jumps over the lazy cog"
H = 0x45C4EE4EE1D25091312135540D6702E6677F7A73B5DA31E10B8BB7AADAC4EBA3

[править] Примечания

↑ European cryptologists attack hash functions(англ.)
↑ Leontiev, S., Ed. and D. Shefanovskij, Ed. Using the GOST R 34.10-94, GOST R 34.10-2001 and GOST R 34.11-94 Algorithms with the Internet X.509 Public Key Infrastructure Certificate and CRL Profile (англ.) (May 2006). — RFC 4491. Проверено 12 июня 2009.
↑ Leontiev, S., Ed. and G. Chudov, Ed. Using the GOST 28147-89, GOST R 34.11-94, GOST R 34.10-94, and GOST R 34.10-2001 Algorithms with Cryptographic Message Syntax (CMS) (англ.) (May 2006). — RFC 4490. Проверено 12 июня 2009.
↑ Leontiev, S., Ed. and G. Chudov, Ed. GOST 28147-89 Cipher Suites for Transport Layer Security (TLS) (англ.) (December 2008). — Internet-Drafts, work in progress. Проверено 12 июня 2009.
↑ S. Leontiev, P. Smirnov, A. Chelpanov Using GOST 28147-89, GOST R 34.10-2001, and GOST R 34.11-94 Algorithms for XML Security (англ.) (December 2008). — Internet-Drafts, work in progress. Проверено 12 июня 2009.
↑ V.Dolmatov, Ed. Use of GOST signature algorithms in DNSKEY and RRSIG Resource Records for DNSSEC (англ.) (April 2009). — Internet-Drafts, work in progress. Проверено 12 июня 2009.

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

Хеш-функции

Adler-32 | CRC | HashCart | HAVAL | Keccak | LM-хеш | MD2 | MD4 | MD5 | MD6 | N-Hash | PJW-32 | RIPEMD-160 | RIPEMD-256 | RIPEMD-320 | SHA-1 | SHA-2 | Skein | Snefru | TTH | Whirlpool | ГОСТ Р 34.11-94

[0] European cryptologists attack hash functions(англ.)

[1] Leontiev, S., Ed. and D. Shefanovskij, Ed. Using the GOST R 34.10-94, GOST R 34.10-2001 and GOST R 34.11-94 Algorithms with the Internet X.509 Public Key Infrastructure Certificate and CRL Profile (англ.) (May 2006). — RFC 4491. Проверено 12 июня 2009.

[2] Leontiev, S., Ed. and G. Chudov, Ed. Using the GOST 28147-89, GOST R 34.11-94, GOST R 34.10-94, and GOST R 34.10-2001 Algorithms with Cryptographic Message Syntax (CMS) (англ.) (May 2006). — RFC 4490. Проверено 12 июня 2009.

[3] Leontiev, S., Ed. and G. Chudov, Ed. GOST 28147-89 Cipher Suites for Transport Layer Security (TLS) (англ.) (December 2008). — Internet-Drafts, work in progress. Проверено 12 июня 2009.

[4] S. Leontiev, P. Smirnov, A. Chelpanov Using GOST 28147-89, GOST R 34.10-2001, and GOST R 34.11-94 Algorithms for XML Security (англ.) (December 2008). — Internet-Drafts, work in progress. Проверено 12 июня 2009.

[5] V.Dolmatov, Ed. Use of GOST signature algorithms in DNSKEY and RRSIG Resource Records for DNSSEC (англ.) (April 2009). — Internet-Drafts, work in progress. Проверено 12 июня 2009.

[1]

[2]

[3]

[4]

[5]

[6]