Stribog (hash függvény)

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. július 15-én felülvizsgált verziótól ; az ellenőrzések 6 szerkesztést igényelnek .
Stribog
Fejlesztők Orosz FSB ,
OJSC "InfoTeKS"
közzétett 2012
Szabványok GOST 34.11-2018, GOST R 34.11-2012, ISO/IEC 10118-3:2018, RFC 6986
Hash méret 256 vagy 512 bites
A körök száma 12
Típusú hash függvény

A Stribog  ( STREEBOG  [ 1] ) egy kriptográfiai algoritmus egy 512 bites bemeneti adatblokk méretével és 256 vagy 512 bites hash kóddal rendelkező hash függvény kiszámítására .

A GOST 34.11-2018 „Információs technológia. Az információk kriptográfiai védelme . A kivonatoló függvény "- a jelenlegi államközi titkosítási szabvány .

Az Oroszországi Szövetségi Biztonsági Szolgálat Információbiztonsági és Speciális Kommunikációs Központja fejlesztette ki a JSC InfoTeKS részvételével az Orosz Föderáció GOST R 34.11-2012 nemzeti szabványa alapján, és 2019. június 1-jén léptették hatályba a Rosstandart rendelete alapján. 2018. december 4 -én kelt 1060. sz .

A GOST R 34.11-2012 szabványt az elavult GOST R 34.11-94 szabvány helyettesítéseként fejlesztették ki és vezették be :

A <...> fejlesztésének szükségességét egy olyan hash függvény létrehozásának szükségessége okozza, amely megfelel a kriptográfiai erősség modern követelményeinek és a GOST R 34.10-2012 szabvány elektronikus digitális aláírásra vonatkozó követelményeinek .

— A szabvány szövege. Bevezetés.

A hash függvény neve - " Stribog ", a szláv istenség neve után - gyakran használatos a szabvány hivatalos neve helyett, bár a szövegében kifejezetten nem szerepel (lásd alább ).

A Stribog hash függvény felépítésének fogalmai

A RusCrypto-2010 konferencián megfogalmazott követelményeknek megfelelően az új hash függvény munkája során [2] :

Ugyanebben a munkában „univerzális” követelményeket vezetnek be a hash függvény elleni támadások összetettségére vonatkozóan:

Egy feladat Bonyolultság
prototípus építése 2n _
ütközés építése 2n/ 2
a második prototípus megépítése 2 n / (üzenet hossza)
prototípus hosszabbítás 2n _

A GOST R 34.11-2012 és a GOST R 34.11-94 összehasonlítása

Tömörítési funkció

A hash függvényben fontos elem a tömörítési függvény. A GOST R 34.11-2012-ben a tömörítési funkció a Miaguchi-Prenel tervezésen alapul . A Miaguchi-Prenel tervezés sémája: h, m - vektorok bemenete a tömörítési függvénybe; g(h, m) a tömörítési függvény eredménye; Az E egy blokk-rejtjel, amelynek blokkja és kulcsa 512 bit. A GOST R 34.11-2012 hash függvényében az XSPL-rejtjel blokkrejtjelnek minősül. Ez a titkosítás a következő átalakításokból áll:

Az új hash függvényben használt transzformációkat jól meg kell érteni. Ezért az E blokk titkosítás az X, S, P, L transzformációkat használja, amelyek jól tanulmányozottak.

A blokk titkosítás fontos paramétere az, hogy a kulcsot hogyan választják ki az egyes körökben való használatra. A GOST R 34.11-2012-ben használt blokk-rejtjelben a , , ... , kulcsok mind a 13 körhöz a titkosítási funkció segítségével generálódnak.

, , … ,  iteratív állandók, amelyek 512 bites vektorok. Jelentésüket a szabvány megfelelő szakasza határozza meg.

Leírás

A hash függvény a Merkle-Damgor iteratív konstrukción alapul , MD erősítéssel. Az MD-erősítés alatt egy hiányos blokk hozzáadását értjük, amikor a hash függvényt egy teljes blokkhoz adjuk egy olyan hosszúságú vektor (0 ... 01) hozzáadásával, hogy teljes blokkot kapjunk. A további elemek közül a következőket kell megjegyezni:

A fent leírt megoldások lehetővé teszik számos jól ismert támadás elleni védekezést.

A GOST R 34.11-2012 hash függvény rövid leírása a következőképpen mutatható be. A hash függvény bemenete tetszőleges méretű üzenet. Továbbá az üzenet 512 bites blokkokra van felosztva, ha az üzenet mérete nem 512 többszöröse, akkor kiegészítik a szükséges bitszámmal. Ezután a tömörítési függvény iteratív módon kerül felhasználásra, aminek eredményeként a hash függvény belső állapota frissül . A blokk ellenőrző összege és a feldolgozott bitek száma is kiszámításra kerül. Az eredeti üzenet összes blokkjának feldolgozása után két további számítás történik, amelyek befejezik a hash függvény számítását:

Alekszandr Kazimirov és Valentina Kazimirova [5] munkájában a hash-függvény számításának grafikus illusztrációja látható.

Elemzés

Biztonság

A régi szabvány kriptoanalízise feltárta annak néhány gyenge pontját elméleti szempontból. Így az egyik, a GOST R 34.11-94 kriptoanalízisével foglalkozó cikkben [6] azt találták, hogy a kép előtti konstrukciós algoritmus bonyolultságát 2192 tömörítési függvény számításra becsülik, 2105 ütközést , ami kisebb, mint a "univerzális" becslések, amelyek a GOST R 34.11-94 esetén egyenlő 2256 és 2128 . Bár 2013-tól nem sok munka foglalkozik az új hash függvény kriptográfiai erősségével, az új hash függvény tervezése alapján levonhatunk néhány következtetést a kriptográfiai erősségéről, és feltételezhetjük, hogy , hogy a kriptográfiai ellenállása nagyobb lesz, mint a GOST R 34.11-94:

2013-ban a "Cryptology ePrint Archive: Listing for 2013" webhely két cikket tett közzé egy új hash függvény kriptográfiai elemzéséről. A "Rebound attack on Stribog" [7] című cikk a hash funkció robusztusságát tárja fel a "The Rebound attack" nevű támadással szemben; ez a támadás a "rotációs kriptoanalízisen" és a differenciális kriptográfiai elemzésen alapul . A kriptaelemzők a „szabadindítás” nevű módszert alkalmazták a sebezhetőségek keresésekor. Ez azt jelenti, hogy a hash kód kiszámításakor a hash függvény egy bizonyos állapota rögzítésre kerül, és a további számítások mind a hash-kód kiszámítására, mind az üzenet kiszámítására irányulhatnak. A kriptoanalitikusok 5 kör alatt tudtak ütközést elérni, és 7,75 kör felhasználásával sikerült elérni az úgynevezett "közelütközést" (ami azt jelenti, hogy két olyan üzenetet találtak, amelyek hash kódjai kis számú bitben különböznek egymástól). Azt is megállapították, hogy az a séma, amely alapján a billentyűket minden körhöz kiválasztják, stabilitást ad a tömörítési funkciónak. Kimutatták azonban, hogy ütközés 7,75 fordulóban lehetséges, "közel ütközés" pedig 8,75 és 9,75 fordulóban.

Az "Integral Distinguishers for Reduced-round Stribog" [8] című cikk a hash függvény (csökkentett számú körrel) biztonságát tárgyalja az integrált kriptoanalízissel szemben . A szerzőknek a tömörítési függvény tanulmányozása során sikerült megtalálni a különbséget előrefelé történő számításnál 4 körben, ellenkező irányú számításnál 3,5 körben. Azt is megállapították, hogy egy 6-os és 7-es körös hash-függvény elleni differenciális támadáshoz 264 , illetve 2120 átlagos körre van szükség .

Egy új hash-függvény kriptográfiai erősségének tanulmányozására az InfoTeKS cég 2013 novemberében versenyt hirdetett [9] ; 2015 májusában ért véget [10] . A győztes a The Usage of Counter Revisited: Second-Preimage Attack on New Russian Standardized Hash Function lett, amelyben a szerzők egy támadást mutattak be, hogy megtalálják a Stribog-512 hash függvény második előképét, amely 2266 tömörítési funkciót igényel a hosszabb üzenetekhez. mint 2 259 blokk [11] .

A Crypto-2015 konferencián Alex Biryukov , Leo Perrin és Alexey Udovenko bemutatott egy jelentést, amely szerint a Grasshopper titkosítás S-blokkjának és a Stribog hash függvénynek az értékei nem (pszeudo) véletlen számok, hanem generáláson alapulnak. rejtett algoritmuson , amit a hangszóróknak sikerült visszaállítani reverse engineering módszerekkel [12] [13] .

2019. január 29-én megjelent a „Partitions in the S-Box of Streebog and Kuznyechik” [14] című tanulmány , amely cáfolja a szerzők állítását a Stribog és Kuznyechik algoritmusok helyettesítő tábláinak véletlenszerű megválasztásáról [15]. .

Teljesítmény

A „Párhuzamos számítástechnikai és vezérlési problémák” (PACO'2012) VI nemzetközi konferenciának szentelt webhely P. A. Lebedev cikkét mutatja be „A régi és új orosz szabványok összehasonlítása az NVIDIA CPU-k és GPU-k kriptográfiai hash funkciójára vonatkozóan”, amelyben összehasonlítás történik. a GOST R 34.11-94 és GOST R 34.11-2012 kriptográfiai hash funkciók családjának teljesítményéről x86_64 architektúrájú processzorokon és CUDA technológiát támogató NVIDIA videokártyákon [16] .

Az x86_64 processzor teljesítményének összehasonlításához a hash függvények 4 különböző megvalósítását vettük figyelembe:

  1. a GOST R 34.11-1994 megvalósítása az OpenSSL kriptográfiai csomagból (1.0.1c verzió) nyílt forráskóddal. Ebben a megvalósításban nincsenek algoritmusok vagy szoftveroptimalizálások;
  2. a GOST R 34.11-1994 végrehajtása az RHash programban (1.2.9-es verzió). Ez a megvalósítás algoritmikus és szoftveroptimalizálást tartalmaz, beleértve az összeszerelő optimalizálásokat is;
  3. a GOST R 34.11-2012 végrehajtása, írta: A. Kazimirov [17] ;
  4. a GOST R 34.11-1994 és a GOST R 34.11-2012 végrehajtása, írta P. A. Lebedev.

Intel Core i7-920 CPU-t használtak 2,67 GHz-es alapfrekvenciával. Teljesítmény eredményei:

GOST R 34.11-1994 GOST R 34.11-2012
Megvalósítási sz. MB/s Óraszám/byte MB/s Óraszám/byte
egy tizennyolc 143 - -
2 49 52 - -
3 - - 38 67
négy 64 40 94 27

A GPU-n lévő hash-függvények régi és új szabványainak sebességének összehasonlítását P. A. Lebedev implementációi között végezték el. NVIDIA GTX 580 grafikus kártya használt. Teljesítmény eredmények (8192 16 KB adatfolyam):

GOST R 34.11-1994 GOST R 34.11-2012
MB/s Óraszám/byte MB/s Óraszám/byte
1697 - 608 -

Ezen eredmények alapján arra a következtetésre jutottunk, hogy a GOST R 34.11-2012 hash funkciója kétszer olyan gyors lehet, mint a GOST R 34.11-94 hash funkció a modern processzorokon, de lassabb a grafikus kártyákon és a korlátozott erőforrásokkal rendelkező rendszereken.

Ezek a teljesítményeredmények azzal magyarázhatók, hogy az új hash függvény számítása csak modulo 2 összeadásokat és adatátviteli utasításokat használ. A régi hash függvény sok keverési utasítást tartalmaz, amelyek nem illeszkednek jól a CPU utasításkészletéhez. A GOST R 34.11-2012 hash-függvény állapotainak és helyettesítési tábláinak megnövekedett mérete azonban lelassítja a rendkívül párhuzamos számítástechnikai eszközökön, például a GPU-kon.

Ezenkívül a fejlesztők tanulmányozták az új hash funkció teljesítményét egy 64 bites Intel Xeon E5335 2 GHz-es processzoron. Egy magot használtak. A GOST R 34.11-2012 hash funkció teljesítménye 51 processzorciklus volt a kivonatolt adatok 1 bájtjaként (körülbelül 40 MB/s). A kapott eredmény 20%-kal jobb, mint a régi GOST R 34.11-94 hash függvény.

Érdekes tények

A szabvány szövegének végén példák találhatók a lépésről lépésre történő hash kiszámítására több kezdeti értékhez. Ezen értékek egyike a 2. példából származó 576 bites (72 bájt) hexadecimális M 2 szám:

fbe2e5f0eee3c820fbeafaebef20fffbf0e1e0f0f520e0ed20e8ece0ebe5f0f2f120fff0
eeec20f120faf2fee5e2202ce8f6f3ede220e12025f3ede220e120f6f

Egy x86 - os számítógépen a bájtok sorrendje alacsonytól magasig terjed , és a memóriában lévő hasonló szám „fordított” formában jelenik meg. Ha ezt a bájttömböt szöveggé konvertálja Windows-1251 kódolással , akkor egy kissé módosított sort kap az Igor kampányáról szóló Word- ből :

Ezek a szelek, Stribozs unokái, a tenger felől fújnak nyilakkal Igor bátor pengetőire.

A „Watch your Constants: Mallicious Streebog” [18] című kritikai cikkre reagálva a TK26 bizottság megjegyzést adott ki „A Stribog hash függvény konstansainak generálására szolgáló algoritmusról” [19] [20] , amely elmagyarázza, hogy a kerek kulcskonstansok. bemeneti karakterláncok transzformációjaként épültek fel a Stribog-szerű hash függvény segítségével. Ha ezeket a bemeneti karakterláncokat Windows-1251 kódolású szöveggé konvertálja , akkor a szabvány szerzőinek neveit kapjuk meg:

C i = H init (M) M (hexadecimális jelöléssel) M cp1251 (karakterlánc a Windows-1251 rendszerben )
C1_ _ e2e5ede1e5f0c3 Grebnev
C2_ _ f7e8e2eef0e8ece8e4e0ebc220e9e5e3f0e5d1 Szergej Vlagyimirovics
C3_ _ f5f3ecc4 Dmuh
C4_ _ f7e8e2eef0e4ede0f1eae5ebc020e9e5f0e4edc0 Andrej Alekszandrovics
C5_ _ ede8e3fbc4 Dygin
C6_ _ f7e8e2eeebe9e0f5e8cc20f1e8ede5c4 Denis Mihajlovics
C7_ _ ede8f5fef2e0cc Matyukhin
C 8 f7e8e2eef0eef2eae8c220e9e8f0f2e8ecc4 Dmitrij Viktorovics
C9_ _ e9eeeaf1e4f3d0 Rudskoy
C 10 f7e8e2e5f0eee3c820f0e8ece8e4e0ebc2 Vlagyimir Igorevics
C 11 ede8eaf8e8d8 Shishkin
C 12 f7e8e2e5e5f1eae5ebc020e9e8ebe8f1e0c2 Vaszilij Alekszejevics

Jegyzetek

  1. ↑ 17. 11. dedikált hash-függvény (STREEBOG-512) Archiválva : 2020. január 22. a Wayback Machine -nél // ISO/IEC 10118-3:2018 IT-biztonsági technikák – Hash-funkciók – 3. rész: Dedikált hash-funkciók.
  2. ↑ Matyukhin D.V., Shishkin V.A., Rudsky V.I. Egy ígéretes kivonatoló algoritmus // Jelentés a RusCrypto'2010 konferencián, 2010.
  3. ↑ Serge Vaudenay (2002). „Biztonsági hibák, amelyeket az SSL-hez, IPSEC-hez, WTLS-hez… CBC-kitöltő alkalmazások okoztak”. Advances in Cryptology – EUROCRYPT 2002, Proc. Nemzetközi Konferencia a kriptográfiai technikák elméletéről és alkalmazásairól. Springer Verlag (2332): 534-545.
  4. ↑ Kenneth G. Paterson; Gaven J. Watson (2008). "A CBC mód immunizálása az Oracle támadások ellen: formális biztonsági kezelés". Biztonság és kriptográfia hálózatokhoz - SCN 2008, Előadásjegyzetek számítástechnikából. Springer Verlag (5229): 340-357.
  5. ↑ Forrás . Letöltve: 2013. december 1. Az eredetiből archiválva : 2013. december 3.
  6. ↑ F. Mendel, N. Pramstaller, C. Rechberger, M. Kontak, J. Szmidt» CRYPTO 2008
  7. ↑ Riham AlTawy, Aleksandar Kircanski és Amr M. Youssef. Visszapattanó támadások Stribog ellen  (angol) (2013. augusztus 27.). Letöltve: 2013. december 1. Az eredetiből archiválva : 2013. december 3.
  8. ↑ Riham AlTawy és Amr M. Youssef. Integral Distinguishers for Reduced-round Stribog  (angol) (2013. október 8.). Letöltve: 2015. november 3. Az eredetiből archiválva : 2016. március 4..
  9. ↑ http://www.streebog.info/ Archivált 2013. december 3-án a Wayback Machine Open Feature Research Competition versenyen
  10. ↑ http://www.streebog.info/news/opredeleny-pobediteli-konkursa-po-issledovaniyu-khesh-funktsii-stribog/ Archiválva : 2015. szeptember 10. a Wayback Machine -nél Kiderültek a Stribog hash függvény kutatási verseny győztesei
  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  (angol) (2014. augusztus 29.). Letöltve: 2015. november 3. Az eredetiből archiválva : 2016. március 4..
  12. ↑ Alex Biryukov, Leo Perrin, Aleksei Udovenko. The Secret Structure of the S-Box of Streebog, Kuznechik és Stribob  (angolul) (2015. augusztus 14.). Letöltve: 2015. november 3. Az eredetiből archiválva : 2015. szeptember 8..
  13. ↑ Alex Biryukov, Leo Perrin, Aleksei Udovenko. A Streebog, a Kuznyechik és a STRIBOBr1 S-Box (teljes verzió) visszafordítása  (angolul) (2016. január 26.). Letöltve: 2017. február 22. Az eredetiből archiválva : 2017. július 16.
  14. ↑ Leo Perrin. Partíciók a Streebog és a Kuznyechik S-Box-ban (2019. január 29.). Letöltve: 2020. augusztus 25. Az eredetiből archiválva : 2020. november 14.
  15. ↑ Virgil Security Inc. Egy másik furcsaság a GOST Grasshopper és Stribog algoritmusaiban . habr.com . Letöltve: 2020. augusztus 25. Az eredetiből archiválva : 2020. november 7..
  16. ↑ P. A. Lebegyev. Az NVIDIA CPU-k és GPU-k kriptográfiai hash funkciójának régi és új RF szabványainak összehasonlítása . Moszkvai Elektronikai és Matematikai Intézet, Nemzeti Kutatóegyetem Közgazdasági Felsőiskola (2012). Letöltve: 2020. augusztus 25. Az eredetiből archiválva : 2021. április 18.
  17. ↑ GitHub - okazymyrov/stribog . Letöltve: 2013. december 3. Az eredetiből archiválva : 2018. június 11.
  18. ↑ Riham AlTawy és Amr M. Youssef. Nézze meg az állandókat: Malicious Streebog  (angol) (2013. október 8.). Letöltve: 2015. november 3. Az eredetiből archiválva : 2016. március 4..
  19. ↑ V.I. Rudskoy. A Stribog hashing függvény állandóit generáló algoritmusról . Letöltve: 2019. december 26. Az eredetiből archiválva : 2019. december 26.
  20. ↑ V. Rudszkoj. Megjegyzés a Streebog állandók  eredetéhez . Letöltve: 2019. december 26. Az eredetiből archiválva : 2021. március 2.

Linkek

 Hash függvények
Általános rendeltetésű
Kriptográfia
Kulcsgenerálási funkciók
Csekkszám ( összehasonlítás )
Hashes