Stribog (hash-funktion)

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 15. juli 2021; checks kræver 6 redigeringer .
Stribog
Udviklere FSB i Rusland ,
OJSC "InfoTeKS"
offentliggjort 2012
Standarder GOST 34.11-2018, GOST R 34.11-2012, ISO/IEC 10118-3:2018, RFC 6986
Hash størrelse 256 eller 512 bit
Antal runder 12
Type hash funktion

Stribog  ( STREEBOG  [ 1] ) er en kryptografisk algoritme til beregning af en hashfunktion med en inputdatablokstørrelse på 512 bit og en hashkodestørrelse på 256 eller 512 bit .

Beskrevet i GOST 34.11-2018 "Informationsteknologi. Kryptografisk beskyttelse af information . Hashing-funktionen "- den aktuelle mellemstatslige kryptografiske standard .

Udviklet af Center for Informationssikkerhed og Speciel Kommunikation af Federal Security Service of Russia med deltagelse af JSC InfoTeKS baseret på den nationale standard for Den Russiske Føderation GOST R 34.11-2012 og sat i kraft den 1. juni 2019 efter ordre fra Rosstandart nr. 1060-st dateret 4. december 2018 .

GOST R 34.11-2012-standarden blev udviklet og introduceret som en erstatning for den forældede standard GOST R 34.11-94 :

Behovet for at udvikle <...> er forårsaget af behovet for at skabe en hash-funktion, der opfylder moderne krav til kryptografisk styrke og kravene i GOST R 34.10-2012- standarden for elektronisk digital signatur .

— Standardens tekst. Introduktion.

Navnet på hashfunktionen - " Stribog ", efter navnet på den slaviske guddom - bruges ofte i stedet for standardens officielle navn, selvom det ikke er eksplicit nævnt i dens tekst (se nedenfor ).

Koncepter til konstruktion af Stribog-hash-funktionen

I overensstemmelse med kravene udtrykt på RusCrypto-2010-konferencen, i arbejdet med den nye hashfunktion [2] :

I samme arbejde introduceres "universelle" krav til kompleksiteten af ​​angreb på hashfunktionen:

En opgave Kompleksitet
bygge en prototype 2n _
bygge en kollision 2n/ 2
konstruktion af den anden prototype 2 n /(meddelelseslængde)
prototype forlængelse 2n _

Sammenligning af GOST R 34.11-2012 og GOST R 34.11-94

Kompressionsfunktion

I en hashfunktion er et vigtigt element komprimeringsfunktionen. I GOST R 34.11-2012 er kompressionsfunktionen baseret på Miaguchi-Prenel-designet . Skema for Miaguchi-Prenel-designet: h, m - vektorer input til komprimeringsfunktionen; g(h, m) er resultatet af kompressionsfunktionen; E er en blokcifre med en blok- og nøglelængde på 512 bit. XSPL-chifferet tages som en blokciffer i GOST R 34.11-2012 hash-funktionen. Denne chiffer består af følgende transformationer:

De transformationer, der bruges i den nye hash-funktion, skal forstås godt. Derfor bruger blokcifret E transformationerne X, S, P, L, som er godt undersøgt.

En vigtig parameter for en blokcifre er, hvordan nøglen vælges til at blive brugt på hver runde. I blokchifferet, der bruges i GOST R 34.11-2012, genereres nøglerne , , ... , for hver af de 13 runder ved hjælp af selve krypteringsfunktionen.

, , … ,  er iterative konstanter, der er 512 bit vektorer. Deres betydning er specificeret i det relevante afsnit af standarden.

Beskrivelse

Hash-funktionen er baseret på Merkle-Damgor iterative konstruktion ved hjælp af MD-forstærkning. MD-amplifikation forstås som tilføjelsen af ​​en ufuldstændig blok, når hashfunktionen beregnes til en komplet, ved at tilføje en vektor (0 ... 01) af en sådan længde, at en komplet blok opnås. Blandt de yderligere elementer skal følgende bemærkes:

Løsningerne beskrevet ovenfor giver dig mulighed for at imødegå mange velkendte angreb.

En kort beskrivelse af hash-funktionen GOST R 34.11-2012 kan præsenteres som følger. Indgangen til hash-funktionen er en besked af vilkårlig størrelse. Yderligere er meddelelsen opdelt i blokke på 512 bit, hvis meddelelsesstørrelsen ikke er et multiplum af 512, så suppleres den med det nødvendige antal bit. Derefter bruges komprimeringsfunktionen iterativt, hvilket resulterer i, at hashfunktionens interne tilstand opdateres . Blokkontrolsummen og antallet af behandlede bits beregnes også . Når alle blokke i den oprindelige meddelelse er blevet behandlet, udføres yderligere to beregninger, der fuldender beregningen af ​​hash-funktionen:

I Alexander Kazimirovs og Valentina Kazimirovas arbejde [5] er der givet en grafisk illustration af beregningen af ​​hashfunktionen.

Analyse

Sikkerhed

Krypteringsanalyse af den gamle standard afslørede nogle af dens svagheder fra et teoretisk synspunkt. I et af artiklerne [6] om kryptoanalyse af GOST R 34.11-94 blev det således fundet, at kompleksiteten af ​​præ-billedkonstruktionsalgoritmen er estimeret til 2192 beregninger af kompressionsfunktioner, kollision 2105 , hvilket er mindre end "universelle" estimater, som for GOST R 34.11- 94 er lig med 2256 og 2128 . Selvom der fra og med 2013 ikke er et stort antal værker afsat til den nye hashfunktions kryptografiske styrke, kan vi baseret på designet af den nye hashfunktion drage nogle konklusioner om dens kryptografiske styrke og antage , at dens kryptografiske modstand vil være højere end GOST R 34.11-94:

I 2013 udgav webstedet "Cryptology ePrint Archive: Listing for 2013" to artikler om kryptoanalysen af ​​en ny hashfunktion. Artiklen "Rebound-angreb på Stribog" [7] udforsker robustheden af ​​hash-funktionen mod et angreb kaldet "The Rebound attack"; dette angreb er baseret på "rotation cryptanalysis" og differential cryptanalyse . Kryptanalytikere brugte en metode kaldet "free-start", når de ledte efter sårbarheder. Det betyder, at ved beregning af hash-koden, er en bestemt tilstand af hash-funktionen fast, og yderligere beregninger kan gå både til at beregne hash-koden og til at beregne beskeden. Kryptanalytikerne var i stand til at opnå en kollision i 5 omgange, og der blev opnået en såkaldt "nær kollision" (hvilket betyder, at der blev fundet to beskeder, hvis hash-koder er forskellige i et lille antal bits) ved hjælp af 7,75 runder. Det blev også fundet, at skemaet, hvormed tasterne vælges for hver runde, tilføjer stabilitet til kompressionsfunktionen. Det har dog vist sig, at en kollision er mulig i 7,75 omgange, og "nær kollision" i henholdsvis 8,75 og 9,75.

Artiklen "Integral Distinguishers for Reduced-round Stribog" [8] diskuterer sikkerheden af ​​en hash-funktion (med et reduceret antal runder) mod integreret kryptoanalyse . Det lykkedes forfatterne, når de studerede kompressionsfunktionen, at finde differentialet i 4 omgange ved beregning i fremadgående retning og i 3,5 runder ved beregning i modsat retning. Det blev også fundet, at et differentielt angreb på en hashfunktion med runder på 6 og 7 kræver henholdsvis 264 og 2120 gennemsnitsrunder .

For at studere den kryptografiske styrke af en ny hash-funktion annoncerede InfoTeKS-virksomheden starten af ​​en konkurrence i november 2013 [9] ; den sluttede i maj 2015 [10] . Vinderen var The Usage of Counter Revisited: Second-Preimage Attack on New Russian Standardized Hash Function, hvor forfatterne præsenterede et angreb for at finde det andet preimage til Stribog-512 hash-funktionen, hvilket kræver 2.266 opkald til komprimeringsfunktionen for længere beskeder end 2 259 blokke [11] .

På Crypto-2015-konferencen præsenterede Alex Biryukov , Leo Perrin og Alexey Udovenko en rapport, der anførte, at værdierne for S-blokken af ​​Grasshopper -chifferet og Stribog-hash-funktionen ikke er (pseudo) tilfældige tal, men genereres baseret på på en skjult algoritme , som højttalerne formåede at gendanne ved hjælp af reverse engineering metoder [12] [13] .

Den 29. januar 2019 blev undersøgelsen "Partitioner i S-Box of Streebog and Kuznyechik" [14] offentliggjort , som tilbageviser forfatternes udsagn om det tilfældige valg af parametre for erstatningstabeller i Stribog og Kuznyechik algoritmerne [15] .

Ydeevne

Siden dedikeret til VI International Conference "Parallel Computing and Control Problems" (PACO'2012) præsenterer en artikel af P. A. Lebedev "Sammenligning af de gamle og nye russiske standarder for den kryptografiske hash-funktion på NVIDIA CPU'er og GPU'er", hvori sammenligning af ydeevnen af ​​familien af ​​kryptografiske hash-funktioner GOST R 34.11-94 og GOST R 34.11-2012 på x86_64-arkitekturprocessorer og NVIDIA-videokort, der understøtter CUDA-teknologi [16] .

For at sammenligne ydeevne på en x86_64-processor blev der taget 4 forskellige implementeringer af hash-funktioner:

  1. implementering af GOST R 34.11-1994 fra OpenSSL kryptografisk pakke (version 1.0.1c) med åben kildekode. Der er ingen algoritmiske eller softwareoptimeringer i denne implementering;
  2. implementering af GOST R 34.11-1994 i RHash-programmet (version 1.2.9). Denne implementering har algoritmiske og softwareoptimeringer, herunder assembler-optimeringer;
  3. implementering af GOST R 34.11-2012, skrevet af A. Kazimirov [17] ;
  4. implementering af GOST R 34.11-1994 og GOST R 34.11-2012 skrevet af P. A. Lebedev.

Der blev brugt en Intel Core i7-920 CPU med en basisfrekvens på 2,67 GHz. Præstationsresultater:

GOST R 34.11-1994 GOST R 34.11-2012
Implementering nr. MB/s Ure/byte MB/s Ure/byte
en atten 143 - -
2 49 52 - -
3 - - 38 67
fire 64 40 94 27

Sammenligning af hastigheden af ​​de gamle og nye standarder for hash-funktioner på GPU'en blev udført mellem implementeringerne af P. A. Lebedev. NVIDIA GTX 580-grafikkort brugt. Ydeevneresultater (8192 16 KB datastrømme):

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

Baseret på disse resultater konkluderes det, at GOST R 34.11-2012 hash-funktionen kan være dobbelt så hurtig som GOST R 34.11-94 hash-funktionen på moderne processorer, men langsommere på grafikkort og systemer med begrænsede ressourcer.

Disse præstationsresultater kan forklares ved, at beregningen af ​​den nye hash-funktion kun bruger modulo 2-tilføjelser og dataoverførselsinstruktioner. Den gamle hash-funktion indeholder mange shuffle-instruktioner, der ikke passer godt til CPU-instruktionssættet. Men den øgede størrelse af tilstande og substitutionstabeller for GOST R 34.11-2012 hash-funktionen gør den langsommere på meget parallelle computerfaciliteter såsom GPU'er.

Også en undersøgelse af ydeevnen af ​​den nye hash-funktion blev udført af dens udviklere på en 64-bit Intel Xeon E5335 2 GHz-processor. Der blev brugt en kerne. Ydeevnen af ​​GOST R 34.11-2012 hash-funktionen var 51 processorcyklusser pr. 1 byte hash-data (ca. 40 MB/s). Det opnåede resultat er 20% bedre end den gamle hash-funktion GOST R 34.11-94.

Interessante fakta

I slutningen af ​​standardteksten er der givet eksempler på trin-for-trin hash-beregning for flere begyndelsesværdier. En af disse værdier er det hexadecimale tal M 2 med længden 576 bit (72 bytes) fra eksempel 2:

fbe2e5f0eee3c820fbeafaebef20fffbf0e1e0f0f520e0ed20e8ece0ebe5f0f2f120fff0
eeec20f120faf2fee5e2202ce8f6f3ede220e18eed20e20e5f5f202020e5f2020202020202020

På en x86 -computer er byterækkefølgen fra lav til høj , og et lignende tal i hukommelsen vil være repræsenteret i en "inverteret" form. Hvis du konverterer denne række af bytes til tekst i Windows-1251- kodning , får du en let ændret linje fra Word om Igors kampagne :

Disse vinde, Stribozhs børnebørn, blæser fra havet med pile på Igors modige plukker

Som svar på den kritiske artikel "Watch your Constants: Malicious Streebog" [18] udsendte TK26-udvalget en note "Om algoritmen til at generere konstanter for Stribog-hash-funktionen" [19] [20] , som forklarer, at runde nøglekonstanter blev bygget som en transformation af inputstrenge ved hjælp af den Stribog-lignende hash-funktion. Hvis disse inputstrenge konverteres til tekst i Windows-1251- kodning , vil navnene på standardens forfattere fås:

C i = H init (M) M (i hexadecimal notation) M cp1251 (streng 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 Dmitry Viktorovich
C9 _ e9eeeaf1e4f3d0 Rudskoy
C 10 f7e8e2e5f0eee3c820f0e8ece8e4e0ebc2 Vladimir Igorevich
C 11 ede8eaf8e8d8 Shishkin
C 12 f7e8e2e5e5f1eae5ebc020e9e8ebe8f1e0c2 Vasily Alekseevich

Noter

  1. ↑ 17. Dedikeret Hash-Function 11 (STREEBOG-512) Arkiveret 22. januar 2020 på Wayback Machine // ISO/IEC 10118-3:2018 IT-sikkerhedsteknikker - Hash-funktioner - Del 3: Dedikerede hash-funktioner.
  2. ↑ Matyukhin D.V., Shishkin V.A., Rudsky V.I. En lovende hashing-algoritme // Rapport ved RusCrypto'2010-konferencen, 2010.
  3. ↑ Serge Vaudenay (2002). "Sikkerhedsfejl induceret af CBC Padding Applications til SSL, IPSEC, WTLS ...". Fremskridt inden for kryptologi - EUROCRYPT 2002, Proc. International konference om teori og anvendelser af kryptografiske teknikker. Springer Verlag (2332): 534-545.
  4. ↑ Kenneth G. Paterson; Gaven J. Watson (2008). "Immunisering af CBC-tilstand mod polstring af Oracle-angreb: En formel sikkerhedsbehandling". Sikkerhed og kryptografi til netværk - SCN 2008, Lecture Notes in Computer Science. Springer Verlag (5229): 340-357.
  5. ↑ Kilde . Hentet 1. december 2013. Arkiveret fra originalen 3. december 2013.
  6. ↑ F. Mendel, N. Pramstaller, C. Rechberger, M. Kontak, J. Szmidt» CRYPTO 2008
  7. ↑ Riham AlTawy, Aleksandar Kircanski og Amr M. Youssef. Rebound-angreb på Stribog  (engelsk) (27. august 2013). Hentet 1. december 2013. Arkiveret fra originalen 3. december 2013.
  8. ↑ Riham AlTawy og Amr M. Youssef. Integral Distinguishers for Reduced-round Stribog  (engelsk) (8. oktober 2013). Hentet 3. november 2015. Arkiveret fra originalen 4. marts 2016.
  9. ↑ http://www.streebog.info/ Arkiveret 3. december 2013 ved Wayback Machine Open Feature Research Competition
  10. ↑ http://www.streebog.info/news/opredeleny-pobediteli-konkursa-po-issledovaniyu-khesh-funktsii-stribog/ Arkiveret 10. september 2015 på Wayback Machine Vinderne af Stribog hashfunktions forskningskonkurrencen er blevet kåret
  11. ↑ Jian Guo, Jérémy Jean, Gaëtan Leurent, Thomas Peyrin, Lei Wang. Brugen af ​​Counter Revisited: Second-Preimage Attack on New Russian Standardized Hash Function  (engelsk) (29. august 2014). Hentet 3. november 2015. Arkiveret fra originalen 4. marts 2016.
  12. ↑ Alex Biryukov, Leo Perrin, Aleksei Udovenko. The Secret Structure of the S-Box of Streebog, Kuznechik and Stribob  (engelsk) (14. august 2015). Hentet 3. november 2015. Arkiveret fra originalen 8. september 2015.
  13. ↑ Alex Biryukov, Leo Perrin, Aleksei Udovenko. Reverse-engineering af S-Box af Streebog, Kuznyechik og STRIBOBr1 (fuld version)  (engelsk) (26. januar 2016). Hentet 22. februar 2017. Arkiveret fra originalen 16. juli 2017.
  14. ↑ Leo Perrin. Skillevægge i S-Box i Streebog og Kuznyechik (29. januar 2019). Hentet 25. august 2020. Arkiveret fra originalen 14. november 2020.
  15. ↑ Virgil Security Inc. En anden mærkværdighed i GOST-algoritmerne Grasshopper og Stribog . habr.com . Hentet 25. august 2020. Arkiveret fra originalen 7. november 2020.
  16. ↑ P. A. Lebedev. Sammenligning af gamle og nye RF-standarder for kryptografisk hash-funktion på NVIDIA CPU'er og GPU'er . Moscow Institute of Electronics and Mathematics, National Research University Higher School of Economics (2012). Hentet 25. august 2020. Arkiveret fra originalen 18. april 2021.
  17. ↑ GitHub - okazymyrov/stribog . Hentet 3. december 2013. Arkiveret fra originalen 11. juni 2018.
  18. ↑ Riham AlTawy og Amr M. Youssef. Hold øje med dine konstanter: Malicious Streebog  (engelsk) (8. oktober 2013). Hentet 3. november 2015. Arkiveret fra originalen 4. marts 2016.
  19. ↑ V.I. Rudskoy. På algoritmen til generering af konstanterne for Stribog-hash-funktionen . Hentet 26. december 2019. Arkiveret fra originalen 26. december 2019.
  20. ↑ V. Rudskoy. Bemærkning om Streebog konstanter  oprindelse . Hentet 26. december 2019. Arkiveret fra originalen 2. marts 2021.

Links

 Hash funktioner
generelle formål
Kryptografisk
Nøglegenereringsfunktioner
Tjek nummer ( sammenligning )
Hashes