Stribog (hashovací funkce)

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 15. července 2021; kontroly vyžadují 6 úprav .
Stribog
Vývojáři FSB Ruska ,
OJSC "InfoTeKS"
zveřejněno 2012
Normy GOST 34.11-2018, GOST R 34.11-2012, ISO/IEC 10118-3:2018, RFC 6986
Velikost hash 256 nebo 512 bitů
Počet kol 12
Typ hashovací funkce

Stribog  ( STREEBOG  [ 1] ) je kryptografický algoritmus pro výpočet hashovací funkce s velikostí bloku vstupních dat 512 bitů a velikostí hash kódu 256 nebo 512 bitů .

Popsáno v GOST 34.11-2018 „Informační technologie. Kryptografická ochrana informací . Hašovací funkce „- aktuální mezistátní kryptografický standard .

Vyvinuto Centrem pro informační bezpečnost a speciální komunikaci Federální bezpečnostní služby Ruska za účasti JSC InfoTeKS na základě národního standardu Ruské federace GOST R 34.11-2012 a uvedeno v platnost 1. června 2019 příkazem Rosstandart č. 1060-st ze dne 4. prosince 2018 .

Norma GOST R 34.11-2012 byla vyvinuta a zavedena jako náhrada za zastaralou normu GOST R 34.11-94 :

Potřeba vývoje <...> je způsobena potřebou vytvořit hashovací funkci, která splňuje moderní požadavky na šifrovací sílu a požadavky normy GOST R 34.10-2012 pro elektronický digitální podpis .

— Text normy. Úvod.

Místo oficiálního názvu standardu se často používá název hashovací funkce - " Stribog ", podle jména slovanského božstva, i když to není v jeho textu výslovně uvedeno (viz níže ).

Koncepty pro konstrukci hashovací funkce Stribog

V souladu s požadavky vyjádřenými na konferenci RusCrypto-2010 v práci na nové hashovací funkci [2] :

Ve stejné práci jsou zavedeny „univerzální“ požadavky týkající se složitosti útoků na hashovací funkci:

Úkol Složitost
stavba prototypu 2n _
budování kolize 2n/ 2
konstrukce druhého prototypu 2 n /(délka zprávy)
prodloužení prototypu 2n _

Srovnání GOST R 34.11-2012 a GOST R 34.11-94

Funkce komprese

V hashovací funkci je důležitým prvkem kompresní funkce. V GOST R 34.11-2012 je funkce komprese založena na designu Miaguchi-Prenel . Schéma Miaguchi-Prenelova návrhu: h, m - vektory vstup do kompresní funkce; g(h, m) je výsledkem kompresní funkce; E je bloková šifra s délkou bloku a klíče 512 bitů. Šifra XSPL je v hašovací funkci GOST R 34.11-2012 brána jako bloková šifra. Tato šifra se skládá z následujících transformací:

Transformace použité v nové hashovací funkci by měly být dobře pochopeny. Proto bloková šifra E používá transformace X, S, P, L, které jsou dobře prostudované.

Důležitým parametrem blokové šifry je způsob výběru klíče, který se má použít v každém kole. V blokové šifře používané v GOST R 34.11-2012 jsou klíče , , ... , pro každé ze 13 kol generovány pomocí samotné šifrovací funkce.

, , … ,  jsou iterační konstanty, které jsou 512 bitovými vektory. Jejich význam je uveden v příslušné části normy.

Popis

Hašovací funkce je založena na Merkle-Damgorově iterativní konstrukci využívající MD zesílení. Amplifikace MD je chápána jako přidání neúplného bloku při výpočtu hašovací funkce k úplnému přidáním vektoru (0 ... 01) takové délky, že se získá úplný blok. Mezi další prvky je třeba poznamenat následující:

Výše popsaná řešení vám umožňují čelit mnoha známým útokům.

Stručný popis hashovací funkce GOST R 34.11-2012 lze uvést následovně. Vstupem hashovací funkce je zpráva libovolné velikosti. Dále je zpráva rozdělena na bloky po 512 bitech, pokud velikost zprávy není násobkem 512, tak je doplněna o požadovaný počet bitů. Poté je iterativně použita kompresní funkce, v důsledku čehož se aktualizuje vnitřní stav hašovací funkce . Vypočítá se také kontrolní součet bloku a počet zpracovaných bitů . Po zpracování všech bloků původní zprávy se provedou další dva výpočty, které dokončí výpočet hashovací funkce:

V práci Alexandra Kazimirova a Valentiny Kazimirové [5] je uvedena grafická ilustrace výpočtu hašovací funkce.

Analýza

Zabezpečení

Kryptoanalýza starého standardu odhalila některé jeho slabiny z teoretického hlediska. V jednom z článků [6] věnovaných kryptoanalýze GOST R 34.11-94 bylo tedy zjištěno, že složitost algoritmu konstrukce předobrazu se odhaduje na 2192 výpočtů kompresních funkcí, kolize 2105 , což je méně než "univerzální" odhady, které se pro GOST R 34.11-94 rovna 2256 a 2128 . Ačkoli od roku 2013 neexistuje velké množství prací věnovaných kryptografické síle nové hashovací funkce, na základě návrhu nové hashovací funkce můžeme vyvodit určité závěry o její kryptografické síle a předpokládat , že jeho kryptografická odolnost bude vyšší než u GOST R 34.11-94:

V roce 2013 publikoval web „Cryptology ePrint Archive: Listing for 2013“ dva články o kryptoanalýze nové hashovací funkce. Článek "Rebound attack on Stribog" [7] zkoumá robustnost hashovací funkce proti útoku zvanému "The Rebound attack"; tento útok je založen na „rotační kryptoanalýze“ a diferenciální kryptoanalýze . Při hledání zranitelností použili kryptoanalytici metodu zvanou „volný start“. To znamená, že při výpočtu hash kódu je zafixován určitý stav hash funkce a další výpočty mohou směřovat jak k výpočtu hash kódu, tak k výpočtu zprávy. Kryptanalytikům se podařilo dosáhnout srážky v 5 kolech a byla získána takzvaná „blízká srážka“ (to znamená, že byly nalezeny dvě zprávy, jejichž hash kódy se liší v malém počtu bitů) za použití 7,75 kol. Bylo také zjištěno, že schéma, podle kterého jsou klávesy vybírány pro každé kolo, dodává kompresní funkci stabilitu. Ukázalo se však, že srážka je možná za 7,75 ran a „skoro srážka“ za 8,75 a 9,75.

Článek "Integrální rozlišovací znaky pro Stribog s omezeným počtem kol" [8] pojednává o zabezpečení hašovací funkce (se sníženým počtem kol) proti integrální kryptoanalýze . Autorům se při studiu kompresní funkce podařilo najít diferenciál ve 4 kolech při výpočtu v dopředném směru a ve 3,5 kolech při výpočtu v opačném směru. Bylo také zjištěno, že diferenciální útok na hashovací funkci s koly 6 a 7 vyžaduje 264 a 2120 průměrných kol .

Pro studium kryptografické síly nové hashovací funkce oznámila společnost InfoTeKS v listopadu 2013 zahájení soutěže [9] ; skončila v květnu 2015 [10] . Vítězem se stal The Usage of Counter Revisited: Second-Preimage Attack on New Russian Standardized Hash Function, ve kterém autoři představili útok na nalezení druhého předobrazu pro hashovací funkci Stribog-512, který vyžaduje 2 266 volání kompresní funkce pro zprávy delší. než 2 259 bloků [11] .

Na konferenci Crypto-2015 představili Alex Biryukov , Leo Perrin a Alexey Udovenko zprávu, která uvádí, že hodnoty bloku S šifry Grasshopper a hashovací funkce Stribog nejsou (pseudo) náhodná čísla, ale jsou generovány na základě na skrytém algoritmu, který se reproduktorům podařilo obnovit pomocí metod reverzního inženýrství [12] [13] .

Dne 29. ledna 2019 byla publikována studie „Příčky v S-Boxu Streebog a Kuznyechik“ [14] , která vyvrací tvrzení autorů o náhodné volbě parametrů pro náhradní tabulky v algoritmech Stribog a Kuznyechik [15]. .

Výkon

Stránka věnovaná VI mezinárodní konferenci „Parallel Computing and Control Problems“ (PACO'2012) představuje článek P. A. Lebedeva „Porovnání starých a nových ruských standardů pro kryptografickou hashovací funkci na CPU a GPU NVIDIA“, ve kterém je srovnání o výkonu rodiny kryptografických hashovacích funkcí GOST R 34.11-94 a GOST R 34.11-2012 na procesorech architektury x86_64 a grafických kartách NVIDIA podporujících technologii CUDA [16] .

Pro porovnání výkonu na procesoru x86_64 byly použity 4 různé implementace hašovacích funkcí:

  1. implementace GOST R 34.11-1994 z kryptografického balíčku OpenSSL (verze 1.0.1c) s otevřeným zdrojovým kódem. V této implementaci nejsou žádné algoritmické nebo softwarové optimalizace;
  2. implementace GOST R 34.11-1994 v programu RHash (verze 1.2.9). Tato implementace má algoritmické a softwarové optimalizace, včetně optimalizací assembleru;
  3. implementace GOST R 34.11-2012, napsal A. Kazimirov [17] ;
  4. implementace GOST R 34.11-1994 a GOST R 34.11-2012 napsal P. A. Lebedev.

Byl použit procesor Intel Core i7-920 na základní frekvenci 2,67 GHz. Výsledky výkonu:

GOST R 34.11-1994 GOST R 34.11-2012
Provedení č. MB/s Hodiny/bajt MB/s Hodiny/bajt
jeden osmnáct 143 - -
2 49 52 - -
3 - - 38 67
čtyři 64 40 94 27

Porovnání rychlosti starého a nového standardu hashovacích funkcí na GPU bylo provedeno mezi implementacemi P. A. Lebedeva. Použita grafická karta NVIDIA GTX 580. Výsledky výkonu (8192 16 KB datových toků):

GOST R 34.11-1994 GOST R 34.11-2012
MB/s Hodiny/bajt MB/s Hodiny/bajt
1697 - 608 -

Na základě těchto výsledků se dochází k závěru, že hašovací funkce GOST R 34.11-2012 může být dvakrát rychlejší než hašovací funkce GOST R 34.11-94 na moderních procesorech, ale pomalejší na grafických kartách a systémech s omezenými zdroji.

Tyto výkonnostní výsledky lze vysvětlit tím, že výpočet nové hashovací funkce používá pouze modulo 2 sčítání a instrukce pro přenos dat. Stará hašovací funkce obsahuje mnoho instrukcí pro náhodné přehrávání, které se špatně mapují do instrukční sady CPU. Ale větší velikost stavů a ​​substitučních tabulek hašovací funkce GOST R 34.11-2012 ji zpomaluje na vysoce paralelních výpočetních zařízeních, jako jsou GPU.

Také studii výkonu nové hashovací funkce provedli její vývojáři na 64bitovém procesoru Intel Xeon E5335 2 GHz. Bylo použito jedno jádro. Výkon hašovací funkce GOST R 34.11-2012 byl 51 cyklů procesoru na 1 bajt hašovaných dat (přibližně 40 MB/s). Získaný výsledek je o 20 % lepší než stará hashovací funkce GOST R 34.11-94.

Zajímavosti

Na konci textu normy jsou uvedeny příklady výpočtu hash krok za krokem pro několik počátečních hodnot. Jednou z těchto hodnot je hexadecimální číslo M2 o délce 576 bitů (72 bajtů) z příkladu 2:

fbe2e5f0eee3c820fbeafaebef20fffbf0e1e0f0f520e0ed20e8ece0ebe5f0f2f120fff0
eeec20f120faf2fee5e2202ce8e8f6f3edee20e8e8e6edee20e8e

Na počítači x86 je pořadí bajtů od nejnižší k nejvyšší a podobné číslo v paměti bude reprezentováno v „převrácené“ podobě. Pokud toto pole bajtů převedete na text v kódování Windows-1251 , získáte mírně upravený řádek z Wordu o Igorově kampani :

Tyto větry, Stribozhovi vnoučata, vanou z moře šípy na Igorova statečná trhnutí

V reakci na kritický článek „Watch your Constants: Malicious Streebog“ [18] , výbor TK26 vydal poznámku „O algoritmu pro generování konstant pro hashovací funkci Stribog“ [19] [20] , která vysvětluje, že zaokrouhlené klíčové konstanty byly vytvořeny jako transformace vstupních řetězců pomocí hashovací funkce podobné Stribog. Pokud jsou tyto vstupní řetězce převedeny na text v kódování Windows-1251 , získají se jména autorů normy:

C i = H init (M) M (v hexadecimálním zápisu) M cp1251 (řetězec ve Windows-1251 )
C1 _ e2e5ede1e5f0c3 Grebněv
C2 _ f7e8e2eef0e8ece8e4e0ebc220e9e5e3f0e5d1 Sergej Vladimirovič
C3 _ f5f3ecc4 Fuj
C4 _ f7e8e2eef0e4ede0f1eae5ebc020e9e5f0e4edc0 Andrej Alexandrovič
C5 _ ede8e3fbc4 Dygin
C6 _ f7e8e2eeebe9e0f5e8cc20f1e8ede5c4 Denis Michajlovič
C7 _ ede8f5fef2e0cc Matyukhin
C 8 f7e8e2eef0eef2eae8c220e9e8f0f2e8ecc4 Dmitrij Viktorovič
C9 _ e9eeeaf1e4f3d0 Rudskoy
C 10 f7e8e2e5f0eee3c820f0e8ece8e4e0ebc2 Vladimír Igorevič
C 11 ede8eaf8e8d8 Shishkin
C 12 f7e8e2e5e5f1eae5ebc020e9e8ebe8f1e0c2 Vasilij Alekseevič

Poznámky

  1. ↑ 17. Vyhrazená hashovací funkce 11 (STREEBOG-512) Archivováno 22. ledna 2020 na Wayback Machine // ISO/IEC 10118-3:2018 Techniky zabezpečení IT – Hashovací funkce – Část 3: Vyhrazené hashovací funkce.
  2. ↑ Matyukhin D.V., Shishkin V.A., Rudsky V.I. Slibný hashovací algoritmus // Zpráva na konferenci RusCrypto'2010, 2010.
  3. ↑ Serge Vaudenay (2002). „Bezpečnostní chyby způsobené aplikacemi CBC výplně pro SSL, IPSEC, WTLS…“. Pokroky v kryptologii - EUROCRYPT 2002, Proc. Mezinárodní konference o teorii a aplikacích kryptografických technik. Springer Verlag (2332): 534-545.
  4. ↑ Kenneth G. Paterson; Gaven J. Watson (2008). „Imunizování režimu CBC proti útokům vycpávky Oracle: Formální bezpečnostní léčba“ . Bezpečnost a kryptografie pro sítě - SCN 2008, Poznámky k přednáškám z informatiky. Springer Verlag (5229): 340-357.
  5. ↑ Zdroj . Získáno 1. prosince 2013. Archivováno z originálu 3. prosince 2013.
  6. ↑ F. Mendel, N. Pramstaller, C. Rechberger, M. Kontak, J. Szmidt» CRYPTO 2008
  7. ↑ Riham AlTawy, Aleksandar Kircanski a Amr M. Youssef. Odrazové útoky na Stribog  (anglicky) (27. srpna 2013). Získáno 1. prosince 2013. Archivováno z originálu 3. prosince 2013.
  8. ↑ Riham AlTawy a Amr M. Youssef. Integral Distinguishers for Reduced-round Stribog  (anglicky) (8. října 2013). Získáno 3. listopadu 2015. Archivováno z originálu 4. března 2016.
  9. ↑ http://www.streebog.info/ Archivováno 3. prosince 2013 na soutěži Wayback Machine Open Feature Research Competition
  10. ↑ http://www.streebog.info/news/opredeleny-pobediteli-konkursa-po-issledovaniyu-khesh-funktsii-stribog/ Archivováno 10. září 2015 na Wayback Machine Vítězové soutěže ve výzkumu hashovacích funkcí Stribog byli určeni
  11. ↑ Jian Guo, Jérémy Jean, Gaëtan Leurent, Thomas Peyrin, Lei Wang. The Usage of Counter Revisited: Second-Preimage Attack on New Russian Standardized Hash Function  (anglicky) (29. srpna 2014). Získáno 3. listopadu 2015. Archivováno z originálu 4. března 2016.
  12. ↑ Alex Biryukov, Leo Perrin, Aleksei Udovenko. Tajná struktura S-Boxu Streebog, Kuznechik a Stribob  (anglicky) (14. srpna 2015). Získáno 3. listopadu 2015. Archivováno z originálu 8. září 2015.
  13. ↑ Alex Biryukov, Leo Perrin, Aleksei Udovenko. Reverse-Engineering the S-Box of Streebog, Kuznyechik a STRIBOBr1 (plná verze)  (anglicky) (26. ledna 2016). Získáno 22. února 2017. Archivováno z originálu 16. července 2017.
  14. ↑ Leo Perrin. Přepážky v S-Boxu Streebog a Kuznyechik (29. ledna 2019). Získáno 25. srpna 2020. Archivováno z originálu dne 14. listopadu 2020.
  15. ↑ Virgil Security Inc. Další zvláštnost v algoritmech GOST Grasshopper a Stribog . habr.com . Získáno 25. srpna 2020. Archivováno z originálu dne 7. listopadu 2020.
  16. ↑ P. A. Lebeděv. Porovnání starých a nových RF standardů pro kryptografickou hashovací funkci na CPU a GPU NVIDIA . Moskevský institut elektroniky a matematiky, Vysoká škola ekonomická na Národní výzkumné univerzitě (2012). Získáno 25. srpna 2020. Archivováno z originálu dne 18. dubna 2021.
  17. ↑ GitHub - okazymyrov/stribog . Získáno 3. prosince 2013. Archivováno z originálu 11. června 2018.
  18. ↑ Riham AlTawy a Amr M. Youssef. Sledujte své stálice: Malicious Streebog  (anglicky) (8. října 2013). Získáno 3. listopadu 2015. Archivováno z originálu 4. března 2016.
  19. ↑ V.I. Rudskoy. O algoritmu pro generování konstant hashovací funkce Stribog . Získáno 26. prosince 2019. Archivováno z originálu dne 26. prosince 2019.
  20. ↑ V. Rudskoy. Poznámka k původu konstant Streebog  . Získáno 26. prosince 2019. Archivováno z originálu dne 2. března 2021.

Odkazy

 Hashovací funkce
obecný účel
Kryptografický
Funkce generování klíčů
Kontrolní číslo ( srovnání )
Hashe