GOST (hashovací funkce) - GOST (hash function)

GOST R 34,11-94

Všeobecné
Designéři	FAPSI a VNIIstandart ( SSSR )
Poprvé publikováno	1994-05-23 (odtajněno)
Odvozený od	Bloková šifra GOST
Nástupci	Streebog
Osvědčení	GOST standard
Detail
Velikosti digestu	256 bitů
Kola	32
Nejlepší veřejná kryptoanalýza
Útok z roku 2008 narušuje funkci hash celého kola. Příspěvek představuje kolizní útok na 2 105 času a nalezení vzoru útoků v 2 192 čase.

GOST hašovací funkce , které jsou definovány v normách GOST R 34,11-94 a GOST 34.311-95 je 256-bitový šifrovací hash funkce . Původně byla definována v ruském národním standardu GOST R 34.11-94 Informační technologie-Zabezpečení kryptografických informací-Funkce hash . Ekvivalentní standard používaný jinými členskými státy SNS je GOST 34.311-95.

Tato funkce nesmí být zaměňována s jinou hašovací funkcí Streebog , která je definována v nové revizi standardu GOST R 34.11-2012 .

Hašovací funkce GOST je založena na blokové šifře GOST .

Algoritmus

GOST zpracovává zprávu s proměnnou délkou na výstup s pevnou délkou 256 bitů. Vstupní zpráva je rozdělena na bloky 256bitových bloků (osm 32bitových malých endiánových celých čísel); zpráva je vyplněna připojením tolika nul, kolik je potřeba k prodloužení délky zprávy až na 256 bitů. Zbývající bity jsou vyplněny 256bitovým celočíselným aritmetickým součtem všech dříve hašovaných bloků a poté 256bitovým celým číslem představujícím délku původní zprávy v bitech.

Základní zápis

Popisy algoritmů používají následující zápisy:

• ${\ displaystyle {\ mathcal {f}} 0 {\ mathcal {g}}^{j}}$ -j-bitový blok vyplněný nulami.
• ${\ displaystyle {\ mathcal {j}} M {\ mathcal {j}}}$- délka bloku M v bitech modulo 2 ²⁵⁶ .
• ${\ displaystyle {\ mathcal {k}}}$ - zřetězení dvou bloků.
• ${\ displaystyle +}$- aritmetický součet dvou bloků modulo 2 ²⁵⁶
• ${\ displaystyle \ oplus}$ - logický x nebo dva bloky

Dále uvažujeme, že bit malého řádu je umístěn vlevo od bloku a bit vysokého řádu vpravo.

Popis

Vstupní zpráva je rozdělena do 256bitových bloků . V případě, že poslední blok obsahuje méně než 256 bitů, je před dosažením požadované délky ponechán před nulou. ${\ displaystyle M}$${\ Displaystyle m_ {n}, m_ {n-1}, m_ {n-2}, ..., m_ {1}}$${\ displaystyle m_ {n}}$

Každý blok je zpracován krokem hashovací funkce , kde , , jsou 256-bitových bloků. ${\ displaystyle H_ {out} \ = \ f (H_ {in}, m)}$${\ displaystyle H_ {out}}$${\ displaystyle H_ {in}}$${\ displaystyle m}$

Každý blok zprávy, počínaje první, je zpracován pomocí hash funkce kroku , pro výpočet střední hodnoty hash hodnota může být libovolný zvolený, a obvykle je . ${\ displaystyle f}$
${\ displaystyle \! H_ {i+1} = f (H_ {i}, m_ {i})}$
${\ displaystyle H_ {1}}$${\ displaystyle 0^{256}}$

Poté, co se vypočítá, se konečná hodnota hash získá následujícím způsobem ${\ displaystyle H_ {n+1}}$

• ${\ Displaystyle H_ {n+2} \ = \ f (H_ {n+1}, \ L)}$, kde L - je délka zprávy M v modulech bitů ${\ displaystyle 2^{256}}$
• ${\ Displaystyle h \ = \ f (H_ {n+2}, \ K)}$, kde K-je 256bitový kontrolní součet M: ${\ displaystyle m_ {1}+m_ {2}+m_ {3}+...+m_ {n}}$

Je požadovaná hodnota hashovací funkce zprávy M. ${\ displaystyle h}$

Algoritmus tedy funguje následovně.

1. Inicializace:
   1. ${\ displaystyle h \: = initial}$ -Počáteční 256bitová hodnota hashovací funkce určená uživatelem.
   2. ${\ displaystyle \ Sigma \: = \ 0}$ - Kontrolní součet
   3. ${\ Displaystyle L \: = \ 0}$ - Délka zprávy
2. Kompresní funkce interních iterací: pro i = 1… n - 1 proveďte následující (while ): ${\ displaystyle | M |> 256}$
   1. ${\ Displaystyle h \: = \ f (h, \ m_ {i})}$ - použít funkci hash kroku
   2. ${\ Displaystyle L \: = \ L \ +\ 256}$ - přepočítat délku zprávy
   3. ${\ displaystyle \ Sigma \: = \ \ Sigma \ +\ m_ {i}}$ - vypočítat kontrolní součet
3. Kompresní funkce konečné iterace:
   1. ${\ Displaystyle L \: = \ L \ +\ {\ mathcal {j}} \ m_ {n} \ {\ mathcal {j}}}$ - vypočítat plnou délku zprávy v bitech
   2. ${\ Displaystyle m_ {n} \: = \ {0}^{256 \ -\ {\ mathcal {j}} m_ {n} {\ mathcal {j}}} {\ mathcal {k}} m_ {n} }$ - vyplňte poslední zprávu nulami
   3. ${\ displaystyle \ Sigma \: = \ \ Sigma \ +\ m_ {n}}$ - aktualizovat kontrolní součet
   4. ${\ Displaystyle h \: = \ f (h, \ m_ {n})}$ - zpracovat poslední blok zpráv
   5. ${\ Displaystyle h \: = \ f (h, \ L)}$ - MD - posílit hashováním délky zprávy
   6. ${\ Displaystyle h \: = \ f (h, \ \ Sigma)}$ - kontrolní součet hash
4. Výstupní hodnota je .${\ displaystyle h}$

Krok hashovací funkce

Krok hašovací funkce mapuje dva 256-bitových bloků do jedné: . Skládá se ze tří částí: ${\ displaystyle f}$${\ Displaystyle H_ {out} \ = \ f (H_ {in}, \ m)}$

• Generování klíčů ${\ displaystyle K_ {1}, \ K_ {2}, \ K_ {3}, \ K_ {4}}$
• Šifrování transformace pomocí klíčů${\ displaystyle \ H_ {in}}$${\ displaystyle K_ {1}, \ K_ {2}, \ K_ {3}, \ K_ {4}}$
• Náhodná transformace

Generování klíčů

Algoritmus generující klíče používá:

• Dvě transformace 256bitových bloků:
  • Transformace , kde jsou 64-bitové dílčí bloky 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}}$
  • Transformace , kde a je 8-bitové dílčí bloky 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}, \ \ tečky, \ y_ {1}}$
• Tři konstanty:
  • C ₂ = 0
  • C ₃ = 0xff00ffff000000ffff0000ff00ffff0000ff00ff00ff00ffffffffffffffffffff00
  • C ₄ = 0

Algoritmus:

1. ${\ Displaystyle U \: = \ H_ {in}, \ quad V \: = \ m, \ quad W \: = \ U \ \ oplus \ V, \ quad K_ {1} \ = \ P (W)}$
2. Pro j = 2,3,4 proveďte následující:

   ${\ Displaystyle U: = A (U) \ oplus C_ {j}, \ quad V: = A (A (V)), \ quad W: = U \ oplus V, \ quad K_ {j} = P (W )}$

Šifrující transformace

Po vygenerování klíčů se šifrování provádí pomocí GOST 28147-89 v režimu jednoduché náhrady klíčů . Označme šifrující transformaci jako E (Poznámka: transformace E šifruje 64bitová data pomocí 256bitového klíče). Pro šifrování je soubor rozdělen do čtyř 64bitových bloků: a každý z těchto bloků je zašifrován jako: ${\ 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})}$

Poté se výsledné bloky jsou spojeny do jednoho bloku 256 bit: . ${\ Displaystyle S = s_ {4} {\ mathcal {k}} s_ {3} {\ mathcal {k}} s_ {2} {\ mathcal {k}} s_ {1}}$

Náhodná transformace

V posledním kroku se náhodná transformace aplikuje na , S a m pomocí posuvného registru lineární zpětné vazby . Ve výsledku se získá přechodná hodnota hash . ${\ displaystyle H_ {in}}$${\ displaystyle H_ {out}}$

Nejprve jsme definovat funkci cp, dělá LFSR na 256-bitovým blokem: tam, kde jsou 16-bitové dílčí bloky 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}}$

Náhodná transformace je , kde označuje i-tou mocnost funkce. ${\ Displaystyle H_ {out} = {\ psi}^{61} (H_ {in} \ oplus \ psi (m \ oplus {\ psi}^{12} (S)))}$${\ displaystyle {\ psi}^{i}}$${\ Displaystyle \ psi}$

Počáteční hodnoty

Pro GOST R 34.11 94 existují dvě běžně používané sady počátečních parametrů. Počáteční vektor pro obě sady je

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

Ačkoli samotný standard GOST R 34.11 94 neurčuje počáteční hodnotu algoritmu a S-box šifrující transformace , ale v sekcích vzorků používá následující „testovací parametry“. ${\ displaystyle H_ {1}}$${\ displaystyle E}$

S-box „Testovací parametry“

RFC 5831 uvádí pouze tyto parametry, ale RFC 4357 je pojmenovává jako „testovací parametry“ a nedoporučuje je používat v produkčních aplikacích.

Číslo S-boxu	Hodnota
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

CryptoPro S-box

CryptoPro S-box pochází ze sady parametrů „production ready“ vyvinuté společností CryptoPro a je také specifikován jako součást RFC 4357, oddíl 11.2.

Číslo S-boxu	Hodnota
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

Kryptoanalýza

V roce 2008 byl zveřejněn útok, který narušuje úplnou hashovací funkci GOST. Článek představuje kolizní útok za 2 ¹⁰⁵ časů a první a druhý útok předobrazem za 2 ¹⁹² časů (2 ⁿ čas označuje přibližný počet případů, kdy byl algoritmus při útoku vypočítán).

Vektory pro testování hash GOST

Hash pro "testovací parametry"

256bitové (32bajtové) hodnoty GOST jsou obvykle reprezentovány jako 64místná hexadecimální čísla. Zde jsou testovací vektory pro hash GOST s „testovacími parametry“

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

I malá změna zprávy bude mít s drtivou pravděpodobností za následek úplně jiný hash kvůli lavinovému efektu . Například změna d na c :

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

Dva vzorky pocházející ze standardu GOST R 34.11-94:

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

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

Další testovací vektory:

GOST("") =
 ce85b99cc46752fffee35cab9a7b0278abb4c2d2055cff685af4912c49490f8d

GOST("a") =
 d42c539e367c66e9c88a801f6649349c21871b4344c6a573f849fdce62f314dd

GOST("message digest") =
 ad4434ecb18f2c99b60cbe59ec3d2469582b65273f48de72db2fde16a4889a4d

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

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

Hašování pro parametry CryptoPro

Algoritmus GOST s CryptoPro S-box generuje různé sady hodnot hash.

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

Viz také

• Kupyna
• Shrnutí zabezpečení funkce hash
• GOST standardy
• Seznam hašovacích funkcí

Reference

Další čtení

• „GOST R 34.11-94: Algoritmus funkce hash“ . IETF. Březen 2010.
• "Informační technologie. Zabezpečení kryptografických dat. Hashovací funkce" . 2010-02-20. Úplný text standardu GOST R 34.11-94 (v ruštině).

externí odkazy

• Implementační a testovací vektory C pro hashovací funkci GOST od Markku-Juhani Saarinen také obsahují návrhy překladů standardů GOST 28147-89 a GOST R 34.11-94 do angličtiny. Opravená verze, viz [1] .
• Implementace C ++ s toky STL .
• RHash , open source nástroj příkazového řádku, který dokáže vypočítat a ověřit hash GOST (podporuje obě sady parametrů).
• Implementace GOST R 34.11-94 v JavaScriptu ( parametry CryptoPro )
• Stránka Šifrování funkce GOST Hash
• Online kalkulačka GOST