Stribog (hashfunktion)

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 15 juli 2021; kontroller kräver 6 redigeringar .
Stribog
Utvecklare Rysslands FSB ,
OJSC "InfoTeKS"
publiceras 2012
Standarder GOST 34.11-2018, GOST R 34.11-2012, ISO/IEC 10118-3:2018, RFC 6986
Hash storlek 256 eller 512 bitar
Antal omgångar 12
Sorts hash-funktion

Stribog  ( STREEBOG  [ 1] ) är en kryptografisk algoritm för att beräkna en hashfunktion med en indatablockstorlek på 512 bitar och en hashkodstorlek på 256 eller 512 bitar .

Beskrivs i GOST 34.11-2018 "Informationsteknik. Kryptografiskt skydd av information . Hashing-funktionen "- den nuvarande mellanstatliga kryptografiska standarden .

Utvecklat av centrum för informationssäkerhet och speciell kommunikation vid Rysslands federala säkerhetstjänst med deltagande av JSC InfoTeKS baserat på den nationella standarden för Ryska federationen GOST R 34.11-2012 och trädde i kraft den 1 juni 2019 på order av Rosstandart nr 1060-st daterad 4 december 2018 .

GOST R 34.11-2012-standarden utvecklades och introducerades som en ersättning för den föråldrade standarden GOST R 34.11-94 :

Behovet av att utveckla <...> orsakas av behovet av att skapa en hashfunktion som uppfyller moderna krav på kryptografisk styrka och kraven i GOST R 34.10-2012- standarden för elektronisk digital signatur .

— Standardens text. Introduktion.

Namnet på hashfunktionen - " Stribog ", efter namnet på den slaviska gudomen - används ofta istället för standardens officiella namn, även om det inte uttryckligen nämns i dess text (se nedan ).

Koncept för att konstruera Stribog-hashfunktionen

I enlighet med de krav som uttrycktes på RusCrypto-2010-konferensen, i arbetet med den nya hashfunktionen [2] :

I samma arbete införs "universella" krav på komplexiteten i attacker mot hashfunktionen:

En uppgift Komplexitet
bygga en prototyp 2n _
bygga en kollision 2n/ 2
konstruktion av den andra prototypen 2 n /(meddelandelängd)
prototypförlängning 2n _

Jämförelse av GOST R 34.11-2012 och GOST R 34.11-94

Kompressionsfunktion

I en hashfunktion är ett viktigt element komprimeringsfunktionen. I GOST R 34.11-2012 är komprimeringsfunktionen baserad på Miaguchi-Prenel-designen . Schema för Miaguchi-Prenel-designen: h, m - vektorer som matas in till komprimeringsfunktionen; g(h, m) är resultatet av komprimeringsfunktionen; E är ett blockchiffer med en block- och nyckellängd på 512 bitar. XSPL-chifferet tas som ett blockchiffer i GOST R 34.11-2012 hash-funktionen. Detta chiffer består av följande transformationer:

Transformationerna som används i den nya hashfunktionen bör förstås väl. Därför använder blockchifferet E transformationerna X, S, P, L, som är väl studerade.

En viktig parameter för ett blockchiffer är hur nyckeln väljs för att användas på varje runda. I blockchifferet som används i GOST R 34.11-2012 genereras nycklarna , , ... , för var och en av de 13 omgångarna med hjälp av själva krypteringsfunktionen.

, , … ,  är iterativa konstanter som är 512 bitars vektorer. Deras betydelser specificeras i relevant avsnitt av standarden.

Beskrivning

Hashfunktionen är baserad på Merkle-Damgor iterativa konstruktion med MD-förstärkning. MD-förstärkning förstås som tillägget av ett ofullständigt block vid beräkning av hashfunktionen till ett fullständigt genom att addera en vektor (0 ... 01) av sådan längd att ett fullständigt block erhålls. Bland de ytterligare elementen bör följande noteras:

Lösningarna som beskrivs ovan låter dig motverka många välkända attacker.

En kort beskrivning av hashfunktionen GOST R 34.11-2012 kan presenteras enligt följande. Inmatningen av hashfunktionen är ett meddelande av godtycklig storlek. Vidare är meddelandet uppdelat i block om 512 bitar, om meddelandestorleken inte är en multipel av 512, så kompletteras det med det erforderliga antalet bitar. Sedan används komprimeringsfunktionen iterativt, som ett resultat av vilket det interna tillståndet för hashfunktionen uppdateras . Blockkontrollsumman och antalet bearbetade bitar beräknas också . När alla block i det ursprungliga meddelandet har bearbetats utförs ytterligare två beräkningar som slutför beräkningen av hashfunktionen:

I verk av Alexander Kazimirov och Valentina Kazimirova [5] ges en grafisk illustration av beräkningen av hashfunktionen.

Analys

Säkerhet

Kryptering av den gamla standarden avslöjade några av dess svagheter ur en teoretisk synvinkel. Sålunda, i en av artiklarna [6] som ägnas åt kryptoanalys av GOST R 34.11-94, fann man att komplexiteten hos algoritmen för konstruktion av före bilder uppskattas till 2192 beräkningar av komprimeringsfunktioner, kollision 2105 , vilket är mindre än "universella" uppskattningar, som för GOST R 34.11- 94 är lika med 2256 och 2128 . Även om det från och med 2013 inte finns ett stort antal arbeten som ägnas åt den nya hashfunktionens kryptografiska styrka, baserat på designen av den nya hashfunktionen, kan vi dra några slutsatser om dess kryptografiska styrka och anta att dess kryptografiska motstånd kommer att vara högre än för GOST R 34.11-94:

2013 publicerade sajten "Cryptology ePrint Archive: Listing for 2013" två artiklar om kryptoanalysen av en ny hashfunktion. Artikeln "Rebound attack on Stribog" [7] utforskar robustheten i hashfunktionen mot en attack som kallas "The Rebound attack"; denna attack är baserad på "rotation cryptanalysis" och differential cryptanalysis . Kryptanalytiker använde en metod som kallas "free-start" när de letade efter sårbarheter. Detta innebär att vid beräkning av hashkoden är ett visst tillstånd för hashfunktionen fixerat, och ytterligare beräkningar kan gå både mot att beräkna hashkoden och mot att beräkna meddelandet. Kryptanalytikerna kunde åstadkomma en kollision i 5 omgångar och en så kallad "nära kollision" erhölls (vilket innebär att två meddelanden hittades vars hashkoder är olika i ett litet antal bitar) med hjälp av 7,75 omgångar. Det visade sig också att schemat med vilket nycklarna väljs för varje runda ger stabilitet till komprimeringsfunktionen. Det har dock visat sig att en kollision är möjlig i 7,75 omgångar, och "nära kollision" i 8,75 respektive 9,75.

Artikeln "Integral Distinguishers for Reduced-round Stribog" [8] diskuterar säkerheten för en hashfunktion (med ett reducerat antal omgångar) mot integral kryptoanalys . Författarna, när de studerade kompressionsfunktionen, lyckades hitta differentialen i 4 omgångar vid beräkning i framåtriktning och i 3,5 omgångar vid beräkning i motsatt riktning. Det visade sig också att en differentiell attack på en hashfunktion med omgångar om 6 och 7 kräver 264 respektive 2120 genomsnittsrundor .

För att studera den kryptografiska styrkan hos en ny hashfunktion tillkännagav InfoTeKS-företaget starten av en tävling i november 2013 [9] ; den avslutades i maj 2015 [10] . Vinnaren var The Usage of Counter Revisited: Second-Preimage Attack on New Russian Standardized Hash Function, där författarna presenterade en attack för att hitta den andra förbilden för Stribog-512 hash-funktionen, som kräver 2 266 anrop till komprimeringsfunktionen för längre meddelanden än 2 259 block [11] .

På Crypto-2015-konferensen presenterade Alex Biryukov , Leo Perrin och Alexey Udovenko en rapport som anger att värdena för S-blocket för Grasshopper -chifferet och Stribog-hashfunktionen inte är (pseudo) slumptal, utan genereras baserat på på en dold algoritm , som högtalarna lyckades återställa med hjälp av reverse engineering-metoder [12] [13] .

Den 29 januari 2019 publicerades studien "Partitioner i S-Box of Streebog and Kuznyechik" [14] , som motbevisar författarnas uttalande om det slumpmässiga valet av parametrar för ersättningstabeller i Stribog och Kuznyechik-algoritmerna [15] .

Prestanda

Webbplatsen tillägnad VI International Conference "Parallel Computing and Control Problems" (PACO'2012) presenterar en artikel av P. A. Lebedev "Comparison of the old and new Russian standards for the cryptographic hash function on NVIDIA CPUs and GPUs", i vilken jämförelse av prestandan för familjen av kryptografiska hashfunktioner GOST R 34.11-94 och GOST R 34.11-2012 på x86_64-arkitekturprocessorer och NVIDIA-grafikkort som stöder CUDA-teknik [16] .

För att jämföra prestanda på en x86_64-processor togs fyra olika implementeringar av hash-funktioner:

  1. implementering av GOST R 34.11-1994 från OpenSSL-krypteringspaketet (version 1.0.1c) med öppen källkod. Det finns inga algoritmiska eller mjukvaruoptimeringar i denna implementering;
  2. implementering av GOST R 34.11-1994 i RHash-programmet (version 1.2.9). Denna implementering har algoritm- och mjukvaruoptimeringar, inklusive assembleroptimeringar;
  3. implementering av GOST R 34.11-2012, skriven av A. Kazimirov [17] ;
  4. implementering av GOST R 34.11-1994 och GOST R 34.11-2012 skriven av P. A. Lebedev.

En Intel Core i7-920 CPU med en basfrekvens på 2,67 GHz användes. Resultatresultat:

GOST R 34.11-1994 GOST R 34.11-2012
Genomförande nr. MB/s Klockor/byte MB/s Klockor/byte
ett arton 143 - -
2 49 52 - -
3 - - 38 67
fyra 64 40 94 27

Jämförelse av hastigheten för de gamla och nya standarderna för hashfunktioner på GPU:n utfördes mellan implementeringarna av P. A. Lebedev. NVIDIA GTX 580 grafikkort används. Prestandaresultat (8192 16 KB dataströmmar):

GOST R 34.11-1994 GOST R 34.11-2012
MB/s Klockor/byte MB/s Klockor/byte
1697 - 608 -

Baserat på dessa resultat dras slutsatsen att hashfunktionen GOST R 34.11-2012 kan vara dubbelt så snabb som hashfunktionen GOST R 34.11-94 på moderna processorer, men långsammare på grafikkort och system med begränsade resurser.

Dessa prestandaresultat kan förklaras av det faktum att beräkningen av den nya hashfunktionen endast använder modulo 2-tillägg och dataöverföringsinstruktioner. Den gamla hashfunktionen innehåller många shuffle-instruktioner som inte passar bra till CPU-instruktionsuppsättningen. Men den ökade storleken på tillstånd och substitutionstabeller för GOST R 34.11-2012 hash-funktionen gör den långsammare på mycket parallella datorfaciliteter som GPU:er.

En studie av prestandan för den nya hashfunktionen utfördes också av dess utvecklare på en 64-bitars Intel Xeon E5335 2 GHz-processor. En kärna användes. Prestanda för hashfunktionen GOST R 34.11-2012 var 51 processorcykler per 1 byte hashad data (ungefär 40 MB/s). Det erhållna resultatet är 20% bättre än den gamla hashfunktionen GOST R 34.11-94.

Intressanta fakta

I slutet av standardtexten ges exempel på steg-för-steg-hashberäkning för flera initiala värden. Ett av dessa värden är det hexadecimala talet M 2 med längden 576 bitar (72 byte) från exempel 2:

fbe2e5f0eee3c820fbeafaebef20fffbf0e1e0f0f520e0ed20e8ece0ebe5f0f2f120fff0
eeec20f120faf2fee5e2202ce8f6f3ede220e18eed2010f5f0f2010f5f5f20200f5f0f20

På en x86 -dator är byteordningen från låg till hög , och ett liknande antal i minnet kommer att representeras i en "inverterad" form. Om du konverterar denna uppsättning byte till text i Windows-1251- kodning får du en något modifierad rad från Word om Igors kampanj :

Dessa vindar, Stribozhs barnbarn, blåser från havet med pilar på Igors modiga plockar

Som svar på den kritiska artikeln "Watch your Constants: Malicious Streebog" [18] , utfärdade TK26-kommittén en not "Om algoritmen för att generera konstanter för Stribog-hashfunktionen" [19] [20] , som förklarar att runda nyckelkonstanter byggdes som en transformation av inmatningssträngar med den Stribog-liknande hashfunktionen. Om dessa inmatningssträngar konverteras till text i Windows-1251- kodning kommer namnen på författarna till standarden att erhållas:

Ci = H init (M) M (i hexadecimal notation) M cp1251 (sträng i Windows-1251 )
C1 _ e2e5ede1e5f0c3 Grebnev
C2 _ f7e8e2eef0e8ece8e4e0ebc220e9e5e3f0e5d1 Sergey Vladimirovich
C3 _ f5f3ecc4 Dmuh
C4 _ f7e8e2eef0e4ede0f1eae5ebc020e9e5f0e4edc0 Andrey Alexandrovich
C5 _ ede8e3fbc4 Dygin
C6 _ f7e8e2eeebe9e0f5e8cc20f1e8ede5c4 Denis Mikhailovich
C7 _ ede8f5fef2e0cc Matyukhin
C 8 f7e8e2eef0eef2eae8c220e9e8f0f2e8ecc4 Dmitrij Viktorovich
C9 _ e9eeeaf1e4f3d0 Rudskoy
C 10 f7e8e2e5f0eee3c820f0e8ece8e4e0ebc2 Vladimir Igorevich
C 11 ede8eaf8e8d8 Shishkin
C 12 f7e8e2e5e5f1eae5ebc020e9e8ebe8f1e0c2 Vasily Alekseevich

Anteckningar

  1. ↑ 17. Dedikerad Hash-Function 11 (STREEBOG-512) Arkiverad 22 januari 2020 på Wayback Machine // ISO/IEC 10118-3:2018 IT-säkerhetstekniker - Hash-funktioner - Del 3: Dedikerade hash-funktioner.
  2. ↑ Matyukhin D.V., Shishkin V.A., Rudsky V.I. En lovande hashalgoritm // Rapport vid RusCrypto'2010-konferensen, 2010.
  3. ↑ Serge Vaudenay (2002). "Säkerhetsbrister inducerade av CBC Padding Applications till SSL, IPSEC, WTLS ...". Framsteg inom kryptologi - EUROCRYPT 2002, Proc. Internationell konferens om teori och tillämpningar av kryptografiska tekniker. Springer Verlag (2332): 534-545.
  4. ↑ Kenneth G. Paterson; Gaven J. Watson (2008). "Immunisera CBC-läge mot utfyllnad av Oracle-attacker: en formell säkerhetsbehandling". Säkerhet och kryptografi för nätverk - SCN 2008, föreläsningsanteckningar i datavetenskap. Springer Verlag (5229): 340-357.
  5. ↑ Källa . Hämtad 1 december 2013. Arkiverad från originalet 3 december 2013.
  6. ↑ F. Mendel, N. Pramstaller, C. Rechberger, M. Kontak, J. Szmidt» CRYPTO 2008
  7. ↑ Riham AlTawy, Aleksandar Kircanski och Amr M. Youssef. Reboundattacker mot Stribog  (engelska) (27 augusti 2013). Hämtad 1 december 2013. Arkiverad från originalet 3 december 2013.
  8. ↑ Riham AlTawy och Amr M. Youssef. Integral Distinguishers for Reduced-round Stribog  (engelska) (8 oktober 2013). Hämtad 3 november 2015. Arkiverad från originalet 4 mars 2016.
  9. ↑ http://www.streebog.info/ Arkiverad 3 december 2013 vid Wayback Machine Open Feature Research Competition
  10. ↑ http://www.streebog.info/news/opredeleny-pobediteli-konkursa-po-issledovaniyu-khesh-funktsii-stribog/ Arkiverad 10 september 2015 på Wayback Machine Vinnarna av Stribog hashfunktionsforskningstävlingen har fastställts
  11. ↑ Jian Guo, Jérémy Jean, Gaëtan Leurent, Thomas Peyrin, Lei Wang. Användningen av Counter Revisited: Second-Preimage Attack on New Russian Standardized Hash Function  (engelska) (29 augusti 2014). Hämtad 3 november 2015. Arkiverad från originalet 4 mars 2016.
  12. ↑ Alex Biryukov, Leo Perrin, Aleksei Udovenko. The Secret Structure of the S-Box of Streebog, Kuznechik and Stribob  (engelska) (14 augusti 2015). Hämtad 3 november 2015. Arkiverad från originalet 8 september 2015.
  13. ↑ Alex Biryukov, Leo Perrin, Aleksei Udovenko. Reverse-engineering the S-Box of Streebog, Kuznyechik and STRIBOBr1 (fullversion)  (engelska) (26 januari 2016). Hämtad 22 februari 2017. Arkiverad från originalet 16 juli 2017.
  14. ↑ Leo Perrin. Skiljeväggar i S-boxen i Streebog och Kuznyechik (29 januari 2019). Hämtad 25 augusti 2020. Arkiverad från originalet 14 november 2020.
  15. ↑ Virgil Security Inc. En annan konstighet i GOST-algoritmerna Grasshopper och Stribog . habr.com . Hämtad 25 augusti 2020. Arkiverad från originalet 7 november 2020.
  16. ↑ P. A. Lebedev. Jämförelse av gamla och nya RF-standarder för kryptografisk hashfunktion på NVIDIA-processorer och GPU:er . Moscow Institute of Electronics and Mathematics, National Research University Higher School of Economics (2012). Hämtad 25 augusti 2020. Arkiverad från originalet 18 april 2021.
  17. ↑ GitHub - okazymyrov/stribog . Hämtad 3 december 2013. Arkiverad från originalet 11 juni 2018.
  18. ↑ Riham AlTawy och Amr M. Youssef. Se dina konstanter: Malicious Streebog  (engelska) (8 oktober 2013). Hämtad 3 november 2015. Arkiverad från originalet 4 mars 2016.
  19. ↑ V.I. Rudskoy. På algoritmen för att generera konstanterna för Stribog-hashfunktionen . Hämtad 26 december 2019. Arkiverad från originalet 26 december 2019.
  20. ↑ V. Rudskoy. Anmärkning om Streebogs konstanters  ursprung . Hämtad 26 december 2019. Arkiverad från originalet 2 mars 2021.

Länkar

 Hash-funktioner
generell mening
Kryptografisk
Nyckelgenereringsfunktioner
Kontrollnummer ( jämförelse )
Hashes