GOST (hash funkce) - GOST (hash function)

The Funkce hash GOST, definované v normách GOST R 34.11-94 a GOST 34.311-95 je 256 bitů kryptografická hashovací funkce. To bylo původně definováno v ruském národním standardu GOST R 34,11-94 Informační technologie - kryptografická bezpečnost informací - hashovací funkce. Ekvivalentní standard používaný jinými členskými státy EU SNS je GOST 34.311-95.

Tuto funkci nelze zaměňovat s jinou Streebog hashovací funkce, která je definována v nové revizi normy GOST R 34.11-2012.^[2]

Funkce hash GOST je založena na Bloková šifra GOST.

Algoritmus

GOST zpracovává zprávy s proměnnou délkou do výstupu s pevnou délkou 256 bitů. Vstupní zpráva je rozdělena na bloky 256bitových bloků (osm 32bitových) malý Endian celá čísla); zpráva je polstrovaný připojením k ní tolik nul, kolik je potřeba, aby se délka zprávy zvýšila 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í notace

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

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

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

Popis

Vstupní zpráva ${ displaystyle M}$ je rozdělena na 256bitové bloky ${ displaystyle m_ {n}, m_ {n-1}, m_ {n-2}, ..., m_ {1}}$V případě posledního bloku ${ displaystyle m_ {n}}$ obsahuje méně než 256 bitů, je doplněn o nula bitů, aby se dosáhlo požadované délky.

Každý blok je zpracován funkcí hash kroku ${ displaystyle H_ {out} = f (H_ {in}, m)}$,kde ${ displaystyle H_ {out}}$, ${ displaystyle H_ {in}}$, ${ displaystyle m}$ jsou 256bitové bloky.

Každý blok zpráv, počínaje prvním, je zpracován funkcí hash kroku ${ displaystyle f}$, pro výpočet mezilehlé hodnoty hash
${ displaystyle ! H_ {i + 1} = f (H_ {i}, m_ {i})}$
The ${ displaystyle H_ {1}}$ hodnota může být libovolně zvolena a obvykle je ${ displaystyle 0 ^ {256}}$.

Po ${ displaystyle H_ {n + 1}}$ je vypočtena, výsledná hodnota hash se získá následujícím způsobem

• ${ displaystyle H_ {n + 2} = f (H_ {n + 1}, L)}$, kde L - je délka zprávy M v bitech modulo ${ 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}}$

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

Algoritmus tedy funguje následovně.

1. Inicializace:
   1. ${ displaystyle h : = počáteční}$ - 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. Funkce komprese interních iterací: pro i = 1… n - 1 proveďte následující (zatímco ${ 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. Funkce komprese finální iterace:
   1. ${ displaystyle L : = L + { mathcal {j}} m_ {n} { mathcal {j}}}$ - vypočítat celou délku zprávy v bitech
   2. ${ displaystyle m_ {n} : = {0} ^ {256 - { mathcal {j}} m_ {n} { mathcal {j}}} { mathcal {k}} m_ {n} }$ - vlož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ílení hashováním délky zprávy
   6. ${ displaystyle h : = f (h, Sigma)}$ - kontrolní hash součet
4. Výstupní hodnota je ${ displaystyle h}$.

Krokovací hash funkce

Funkce hash kroku ${ displaystyle f}$ mapuje dva 256bitové bloky do jednoho: ${ displaystyle H_ {out} = f (H_ {in}, m)}$Skládá se ze tří částí:

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

Generování klíčů

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

• Dvě transformace 256bitových bloků:
  • Proměna ${ 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}}$, kde ${ displaystyle y_ {1}, y_ {2}, y_ {3}, y_ {4}}$ jsou 64bitové dílčí bloky Y.
  • Proměna ${ displaystyle P (Y) = P (y_ {32} { mathcal {k}} y_ {31} { mathcal {k}} tečky { mathcal {k}} y_ {1}) = y _ { varphi (32)} { mathcal {k}} y _ { varphi (31)} { mathcal {k}} tečky { mathcal {k}} y _ { varphi (1)}}$, kde ${ displaystyle varphi (i + 1 + 4 (k-1)) = 8i + k, i = 0, tečky, 3, k = 1, tečky, 8}$, a ${ displaystyle y_ {32}, y_ {31}, tečky, y_ {1}}$ jsou 8bitové dílčí bloky Y.
• Tři konstanty:
  • C₂ = 0
  • C₃ = 0xff00ffff000000ffff0000ff00ffff0000ff00ff00ff00ffff00ff00ff00ff00
  • 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 )}$

Šifrování transformace

Po generování klíčů, šifrování ${ displaystyle H_ {in}}$ se provádí pomocí GOST 28147-89 v režimu jednoduchého nahrazování klíčů ${ displaystyle K_ {1}, K_ {2}, K_ {3}, K_ {4}}$Označme šifrovací transformaci jako E (Poznámka: E transformace šifruje 64bitová data pomocí 256bitového klíče). Pro zašifrování ${ displaystyle H_ {in}}$ je rozdělena do čtyř 64bitových bloků: ${ displaystyle H_ {in} = h_ {4} { mathcal {k}} h_ {3} { mathcal {k}} h_ {2} { mathcal {k}} h_ {1}}$a každý z těchto bloků je šifrován jako:

• ${ 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é jsou výsledné bloky zřetězeny do jednoho 256bitového bloku: ${ displaystyle S = s_ {4} { mathcal {k}} s_ {3} { mathcal {k}} s_ {2} { mathcal {k}} s_ {1}}$.

Náhodné proměny

V posledním kroku se použije náhodná transformace ${ displaystyle H_ {in}}$, S a m pomocí a Posuvný registr lineární zpětné vazby. Ve výsledku je střední hodnota hash ${ displaystyle H_ {out}}$ je získáno.

Nejprve definujeme funkci, LFSR na 256bitovém bloku: ${ 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 }}$, kde ${ displaystyle y_ {16}, y_ {15}, ..., y_ {2}, y_ {1}}$ jsou 16bitové dílčí bloky Y.

Shuffle transformace je ${ displaystyle H_ {out} = { psi} ^ {61} (H_ {in} oplus psi (m oplus { psi} ^ {12} (S)))}$, kde ${ displaystyle { psi} ^ {i}}$ označuje i-tou sílu ${ displaystyle psi}$ funkce.

Počáteční hodnoty

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

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

Ačkoli samotná norma GOST R 34.11 94 neurčuje počáteční hodnotu algoritmu ${ displaystyle H_ {1}}$ a S-box šifrovací transformace ${ displaystyle E}$, ale v sekcích ukázek používá následující „testovací parametry“.^[3]

"Testovací parametry" S-box

RFC 5831 určuje pouze tyto parametry, ale RFC 4357 pojmenuje je jako „testovací parametry“ a nedoporučuje je pro použití v produkčních aplikacích.

S-box CryptoPro

CryptoPro S-box pochází ze sady parametrů "připraveno k výrobě" vyvinuté společností CryptoPro, je také specifikováno jako součást RFC 4357, oddíl 11.2.

Kryptoanalýza

V roce 2008 byl zveřejněn útok, který narušuje komplexní hashovací funkci GOST. Příspěvek představuje a kolizní útok ve 2¹⁰⁵ čas a první a druhý preimage útoky ve 2¹⁹² čas (2ⁿ čas označuje přibližný počet, kolikrát byl algoritmus vypočítán při útoku).^[1]

Vektory hash testu GOST

Mřížky pro „testovací parametry“

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

GOST („Rychlá hnědá liška skáče přes líné dog ") = 77b7fa410c9ac58a25f49bca7d0468c9296529315eaca76bd1a10f376d1f4294

I malá změna ve zprávě bude s naprostou pravděpodobností mít za následek úplně jiný hash kvůli lavinový efekt. Například změna d na C:

GOST („Rychlá hnědá liška skáče přes líné Cog ") = a3ebc4daaab78b0be131dab5737a7f67e602670d543521319150d2e14eeec445

Dva vzorky pocházející z normy GOST R 34.11-94:^[3]

GOST ("This is message, length = 32 bytes") = b1c466d37519b82e8319819ff32595e047a28cb6f83eff1c6916a815a637fffaGOST ("Předpokládejme, že původní zpráva má délku = 50 bajtů") = 471aba57a60a770d3a761306354

Další testovací vektory:

GOST ( "") = ce85b99cc46752fffee35cab9a7b0278abb4c2d2055cff685af4912c49490f8dGOST ( "A") = d42c539e367c66e9c88a801f6649349c21871b4344c6a573f849fdce62f314ddGOST ( "výtah ze zprávy") = ad4434ecb18f2c99b60cbe59ec3d2469582b65273f48de72db2fde16a4889a4dGOST (128 znaků 'U') = 53a3a3ed25180cef0c1d85a074273e551c25660a87062a52d926a9e8fe5733a4GOST (1000000 znaky 'a') = 5c00ccc2734cdd3332d3d4749576e3c1a7dbaf0e7ea74e9fa602413c90a129fa

Hash pro parametry CryptoPro

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

= 981e5f3ca30c841487830f84fb433e13ac1101569b9c13584ac483234cd656c0

GOST ( "A") = e74c52dd282183bf37af0079c9f78055715a103f17e3133ceff1aacf2f403011GOST ( "abc") = b285056dbf18d7392d7677369524dd14747459ed8143997e163b2986f92fd42cGOST ( "výtah ze zprávy") = bc6041dd2aa401ebfa6e9886734174febdb4729aa972d60f549ac39b29721ba0GOST ( "Rychle hnědé liščí skoky přes líný") = 9004294a361a508c586fe53d1f1b02746765e71b765472786e4770d565830a76GOST ( "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") = 73b70a39497de53a6e08c67b6d4db853540f03e9389299d9b0156ef7e85d0f61GOST ( "12345678901234567890123456789012345678901234567890123456789012345678901234567890") = 6bc7b38989b28cf93ae8842bf9d752905910a7528a61e5bce0782de43e610c90GOST ( "Toto je zpráva, délka = 32 bajtů") = 2cefc2f7b7bdc514e18ea57fa74ff357e7fa17d652c75f69cb1be7893ede48ebGOST ( "Předpokládejme, že původní zpráva má délka = 50 bajtů") = c3730c5cbccacf915ac292676f21e8bd4ef75331d9405e5f1a61dc3130a65011GOST (128 z "U") = 1c4ac7614691bbf427fa2316216be8f10d92edfd37cd1027514c1008f649c4e8GOST (1000000 "A") = 869 3287aa62f9478f7cb312ec0866b6c4e4a0f11160441e8f4ffcd2715dd554f

Viz také

• Kupyna
• Shrnutí zabezpečení funkce hash
• Normy GOST
• Seznam hashovacích funkcí

Reference

Další čtení

• "GOST R 34.11-94: Algoritmus hashovací funkce". IETF. Březen 2010.
• "Informační technologie. Zabezpečení kryptografických dat. Hašovací funkce". 2010-02-20. Plné znění normy GOST R 34.11-94 (v ruštině).

externí odkazy

• C implementační a testovací vektory pro hashovací funkci GOST od Markku-Juhani Saarinen, obsahuje také návrhy překladů norem GOST 28147-89 a GOST R 34.11-94 do angličtiny. Opravená verze, viz [1].
• Implementace C ++ s proudy STL^{[trvalý mrtvý odkaz ]}.
• RHash, an otevřený zdroj 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 JavaScript (Parametry CryptoPro )
• Stránka šifrování funkce hash GOST
• Online kalkulačka GOST