Stribog (funcție hash)

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 15 iulie 2021; verificările necesită 6 modificări .
Stribog
Dezvoltatori FSB al Rusiei ,
OJSC „InfoTeKS”
publicat 2012
Standarde GOST 34.11-2018, GOST R 34.11-2012, ISO/IEC 10118-3:2018, RFC 6986
Dimensiunea hash 256 sau 512 biți
Numărul de runde 12
Tip de funcția hash

Stribog  ( STREEBOG  [ 1] ) este un algoritm criptografic pentru calcularea unei funcții hash cu o dimensiune a blocului de date de intrare de 512 biți și o dimensiune a codului hash de 256 sau 512 biți .

Descris în GOST 34.11-2018 „Tehnologia informației. Protecția criptografică a informațiilor . Funcția de hashing „- standardul criptografic interstatal actual .

Dezvoltat de Centrul pentru Securitate Informațională și Comunicații Speciale al Serviciului Federal de Securitate al Rusiei , cu participarea JSC InfoTeKS , pe baza standardului național al Federației Ruse GOST R 34.11-2012 și a intrat în vigoare la 1 iunie 2019 prin ordinul lui Rosstandart. Nr. 1060-st din 4 decembrie 2018 .

Standardul GOST R 34.11-2012 a fost dezvoltat și introdus ca înlocuitor pentru standardul învechit GOST R 34.11-94 :

Necesitatea de a dezvolta <...> este cauzată de necesitatea de a crea o funcție hash care să îndeplinească cerințele moderne pentru puterea criptografică și cerințele standardului GOST R 34.10-2012 pentru semnătura digitală electronică .

— Textul standardului. Introducere.

Numele funcției hash - " Stribog ", după numele zeității slave - este adesea folosit în locul numelui oficial al standardului, deși nu este menționat în mod explicit în textul său (vezi mai jos ).

Concepte pentru construirea funcției hash Stribog

În conformitate cu cerințele exprimate la conferința RusCrypto-2010, în lucrarea la noua funcție hash [2] :

În aceeași lucrare, sunt introduse cerințe „universale” privind complexitatea atacurilor asupra funcției hash:

O sarcină Complexitate
construirea unui prototip 2n _
construind o coliziune 2n/ 2
construirea celui de-al doilea prototip 2 n /(lungimea mesajului)
alungirea prototipului 2n _

Comparație între GOST R 34.11-2012 și GOST R 34.11-94

Funcția de compresie

Într-o funcție hash, un element important este funcția de compresie. În GOST R 34.11-2012, funcția de compresie se bazează pe designul Miaguchi-Prenel . Schema designului Miaguchi-Prenel: h, m - vectori de intrare la funcția de compresie; g(h, m) este rezultatul funcției de compresie; E este un cifru bloc cu o lungime a blocului și a cheii de 512 biți. Cifrul XSPL este luat ca un cifru bloc în funcția hash GOST R 34.11-2012. Acest cifru constă din următoarele transformări:

Transformările utilizate în noua funcție hash ar trebui să fie bine înțelese. Prin urmare, cifrul bloc E folosește transformările X, S, P, L, care sunt bine studiate.

Un parametru important al cifrului bloc este modul în care este aleasă cheia pentru a fi utilizată în fiecare rundă. În cifrul bloc utilizat în GOST R 34.11-2012, cheile , , ... , pentru fiecare dintre cele 13 runde sunt generate folosind funcția de criptare în sine.

, , … ,  sunt constante iterative care sunt vectori de 512 biți. Semnificațiile lor sunt specificate în secțiunea relevantă a standardului.

Descriere

Funcția hash se bazează pe construcția iterativă Merkle-Damgor folosind amplificarea MD. Amplificarea MD este înțeleasă ca adăugarea unui bloc incomplet la calcularea funcției hash la una completă prin adăugarea unui vector (0 ... 01) de asemenea lungime încât să se obțină un bloc complet. Dintre elementele suplimentare, trebuie remarcate următoarele:

Soluțiile descrise mai sus vă permit să contracarați multe atacuri binecunoscute.

O scurtă descriere a funcției hash GOST R 34.11-2012 poate fi prezentată după cum urmează. Introducerea funcției hash este un mesaj de dimensiune arbitrară. În plus, mesajul este împărțit în blocuri de 512 biți, dacă dimensiunea mesajului nu este un multiplu de 512, atunci acesta este completat cu numărul necesar de biți. Apoi funcția de compresie este utilizată iterativ, în urma căreia starea internă a funcției hash este actualizată . De asemenea, sunt calculate suma de control bloc și numărul de biți procesați . Când toate blocurile mesajului original au fost procesate, sunt efectuate încă două calcule care completează calculul funcției hash:

În lucrarea lui Alexander Kazimirov și Valentina Kazimirova [5] , este dată o ilustrare grafică a calculului funcției hash.

Analiză

Securitate

Criptanaliza vechiului standard a scos la iveală unele dintre slăbiciunile sale din punct de vedere teoretic. Astfel, într-una dintre lucrările [6] dedicate criptoanalizei GOST R 34.11-94, s-a constatat că complexitatea algoritmului de construcție pre-imagine este estimată la 2192 calcule ale funcțiilor de compresie, coliziune 2105 , care este mai mică decât estimări „universale”, care pentru GOST R 34,11-94 este egală cu 2256 și 2128 . Deși din 2013 nu există un număr mare de lucrări dedicate puterii criptografice a noii funcție hash, bazate pe proiectarea noii funcții hash, putem trage câteva concluzii despre puterea sa criptografică și putem presupune că rezistența sa criptografică va fi mai mare decât cea a GOST R 34.11-94:

În 2013, site-ul „Cryptology ePrint Archive: Listing for 2013” ​​a publicat două articole despre criptoanaliza unei noi funcții hash. Articolul „Rebound attack on Stribog” [7] explorează robustețea funcției hash împotriva unui atac numit „The Rebound attack”; acest atac se bazează pe „criptanaliza de rotație” și criptoanaliza diferențială . Criptanalistii au folosit o metodă numită „pornire gratuită” atunci când au căutat vulnerabilități. Aceasta înseamnă că atunci când se calculează codul hash, o anumită stare a funcției hash este fixată, iar calculele ulterioare pot merge atât spre calcularea codului hash, cât și către calcularea mesajului. Criptanalistii au reusit sa realizeze o coliziune in 5 runde si s-a obtinut o asa-numita „aproape coliziune” (adica au fost gasite doua mesaje ale caror coduri hash sunt diferite intr-un numar mic de biti) folosind 7,75 runde. De asemenea, s-a constatat că schema prin care sunt alese tastele pentru fiecare rundă adaugă stabilitate funcției de compresie. Cu toate acestea, s-a demonstrat că o coliziune este posibilă în 7,75 reprize și „aproape coliziune” în 8,75 și, respectiv, 9,75.

Articolul „Integral Distinguishers for Reduced-round Stribog” [8] discută despre securitatea unei funcții hash (cu un număr redus de runde) împotriva criptoanalizei integrale . Autorii, la studierea funcției de compresie, au reușit să găsească diferența în 4 reprize la calculul în sens înainte și în 3,5 reprize la calculul în sens opus. Sa constatat, de asemenea, că un atac diferențial asupra unei funcții hash cu runde de 6 și 7 necesită 264 și , respectiv, 2120 de runde medii .

Pentru a studia puterea criptografică a unei noi funcții hash, compania InfoTeKS a anunțat începerea unei competiții în noiembrie 2013 [9] ; s-a încheiat în mai 2015 [10] . Câștigătorul a fost The Usage of Counter Revisited: Second-Preimage Attack on New Russian Standardized Hash Function, în care autorii au prezentat un atac pentru a găsi a doua preimagine pentru funcția hash Stribog-512, necesitând 2.266 de apeluri la funcția de compresie pentru mesaje mai lungi. de 2 259 blocuri [11] .

La conferința Crypto-2015, Alex Biryukov , Leo Perrin și Alexey Udovenko au prezentat un raport care afirmă că valorile blocului S al cifrului Grasshopper și ale funcției hash Stribog nu sunt numere (pseudo) aleatoare, ci sunt generate pe baza pe un algoritm ascuns , pe care difuzoarele au reușit să-l restabilească folosind metode de inginerie inversă [12] [13] .

La 29 ianuarie 2019, a fost publicat studiul „Partiții în S-Box of Streebog and Kuznyechik” [14] , care respinge declarația autorilor despre alegerea aleatorie a parametrilor pentru tabelele de înlocuire în algoritmii Stribog și Kuznyechik [15] .

Performanță

Site-ul dedicat celei de-a VI-a Conferințe Internaționale „Parallel Computing and Control Problems” (PACO'2012) prezintă un articol al lui P. A. Lebedev „Compararea vechilor și noilor standarde rusești pentru funcția hash criptografică pe procesoarele și GPU-urile NVIDIA”, în care comparație a performanței familiei de funcții hash criptografice GOST R 34.11-94 și GOST R 34.11-2012 pe procesoare cu arhitectură x86_64 și plăci video NVIDIA care acceptă tehnologia CUDA [16] .

Pentru a compara performanța pe un procesor x86_64, au fost luate 4 implementări diferite ale funcțiilor hash:

  1. implementarea GOST R 34.11-1994 din pachetul criptografic OpenSSL (versiunea 1.0.1c) cu cod sursă deschis. Nu există optimizări algoritmice sau software în această implementare;
  2. implementarea GOST R 34.11-1994 în programul RHash (versiunea 1.2.9). Această implementare are optimizări algoritmice și software, inclusiv optimizări pentru asamblare;
  3. implementarea GOST R 34.11-2012, scrisă de A. Kazimirov [17] ;
  4. implementarea GOST R 34.11-1994 și GOST R 34.11-2012 scris de P. A. Lebedev.

A fost folosit un procesor Intel Core i7-920 la o frecvență de bază de 2,67 GHz. Rezultate de performanță:

GOST R 34.11-1994 GOST R 34.11-2012
Implementare nr. MB/s Ceasuri/octet MB/s Ceasuri/octet
unu optsprezece 143 - -
2 49 52 - -
3 - - 38 67
patru 64 40 94 27

Comparația vitezei standardelor vechi și noi ale funcțiilor hash pe GPU a fost efectuată între implementările lui P. A. Lebedev. Folosită placă grafică NVIDIA GTX 580. Rezultate de performanță (8192 fluxuri de date de 16 KB):

GOST R 34.11-1994 GOST R 34.11-2012
MB/s Ceasuri/octet MB/s Ceasuri/octet
1697 - 608 -

Pe baza acestor rezultate, se ajunge la concluzia că funcția hash GOST R 34.11-2012 poate fi de două ori mai rapidă decât funcția hash GOST R 34.11-94 pe procesoarele moderne, dar mai lentă pe plăcile grafice și sistemele cu resurse limitate.

Aceste rezultate de performanță pot fi explicate prin faptul că calculul noii funcție hash utilizează numai adunări modulo 2 și instrucțiuni de transfer de date. Vechea funcție hash conține multe instrucțiuni de amestecare care nu se potrivesc bine cu setul de instrucțiuni CPU. Dar dimensiunea crescută a stărilor și a tabelelor de înlocuire ale funcției hash GOST R 34.11-2012 o face mai lent pe facilități de calcul extrem de paralele, cum ar fi GPU-urile.

De asemenea, un studiu al performanței noii funcție hash a fost realizat de dezvoltatorii săi pe un procesor Intel Xeon E5335 pe 64 de biți 2 GHz. A fost folosit un nucleu. Performanța funcției hash GOST R 34.11-2012 a fost de 51 de cicluri de procesor pe 1 octet de date hash (aproximativ 40 MB/s). Rezultatul obținut este cu 20% mai bun decât vechea funcție hash GOST R 34.11-94.

Fapte interesante

La sfârșitul textului standardului, sunt date exemple de calcul hash pas cu pas pentru mai multe valori inițiale. Una dintre aceste valori este numărul hexazecimal M 2 cu lungimea de 576 de biți (72 de octeți) din exemplul 2:

fbe2e5f0eee3c820fbeafaebef20fffbf0e1e0f0f520e0ed20e8ece0ebe5f0f2f120fff0
eeec20f120faf2fee5e2202ce8f6f3ede220f6f3ede220e2020202020202020202020202020020020020000000000000

Pe un computer x86 , ordinea octeților este de la mic la mare și un număr similar din memorie va fi reprezentat într-o formă „inversată”. Dacă convertiți această matrice de octeți în text în codificarea Windows-1251 , veți obține o linie ușor modificată din Cuvântul despre campania lui Igor :

Aceste vânturi, nepoții lui Stribozh, bat din mare cu săgeți pe curățile curajoase ale lui Igor

Ca răspuns la articolul critic „Watch your Constants: Malicious Streebog” [18] , comitetul TK26 a emis o notă „Despre algoritmul de generare a constantelor pentru funcția hash Stribog” [19] [20] , care explică faptul că constantele cheie rotunde au fost construite ca o transformare a șirurilor de intrare folosind funcția hash asemănătoare Stribog. Dacă aceste șiruri de intrare sunt convertite în text în codificarea Windows-1251 , atunci se vor obține numele autorilor standardului:

C i = H init (M) M (în notație hexazecimală) M cp1251 (șir în Windows-1251 )
C1 _ e2e5ede1e5f0c3 Grebnev
C2 _ f7e8e2eef0e8ece8e4e0ebc220e9e5e3f0e5d1 Serghei Vladimirovici
C3 _ f5f3ecc4 Dmuh
C4 _ f7e8e2eef0e4ede0f1eae5ebc020e9e5f0e4edc0 Andrei Alexandrovici
C5 _ ede8e3fbc4 Dygin
C6 _ f7e8e2eeebe9e0f5e8cc20f1e8ede5c4 Denis Mihailovici
C7 _ ede8f5fef2e0cc Matyukhin
C 8 f7e8e2eef0eef2eae8c220e9e8f0f2e8ecc4 Dmitri Viktorovici
C9 _ e9eeeaf1e4f3d0 Rudskoy
C 10 f7e8e2e5f0eee3c820f0e8ece8e4e0ebc2 Vladimir Igorevici
C 11 ede8eaf8e8d8 Shishkin
C 12 f7e8e2e5e5f1eae5ebc020e9e8ebe8f1e0c2 Vasili Alekseevici

Note

  1. ↑ 17. Dedicated Hash-Function 11 (STREEBOG-512) Arhivat 22 ianuarie 2020 la Wayback Machine // ISO/IEC 10118-3:2018 IT Security Techniques - Hash-functions - Part 3: Dedicated hash-functions.
  2. ↑ Matyukhin D.V., Shishkin V.A., Rudsky V.I. A promising hashing algorithm // Raport la conferința RusCrypto'2010, 2010.
  3. ↑ Serge Vaudenay (2002). „Defecte de securitate induse de aplicațiile de umplutură CBC la SSL, IPSEC, WTLS…”. Progrese în Criptologie - EUROCRYPT 2002, Proc. Conferință internațională privind teoria și aplicațiile tehnicilor criptografice. Springer Verlag (2332): 534-545.
  4. ↑ Kenneth G. Paterson; Gaven J. Watson (2008). „Modul CBC de imunizare împotriva atacurilor Oracle de umplutură: un tratament formal de securitate”. Securitate și criptare pentru rețele - SCN 2008, Note de curs în Informatică. Springer Verlag (5229): 340-357.
  5. ↑ Sursa . Consultat la 1 decembrie 2013. Arhivat din original pe 3 decembrie 2013.
  6. ↑ F. Mendel, N. Pramstaller, C. Rechberger, M. Kontak, J. Szmidt» CRYPTO 2008
  7. ↑ Riham AlTawy, Aleksandar Kircanski și Amr M. Youssef. Atacurile de rebound asupra Stribog  (engleză) (27 august 2013). Consultat la 1 decembrie 2013. Arhivat din original pe 3 decembrie 2013.
  8. ↑ Riham AlTawy și Amr M. Youssef. Integral Distinguisters for Reduced-round Stribog  (engleză) (8 octombrie 2013). Consultat la 3 noiembrie 2015. Arhivat din original pe 4 martie 2016.
  9. ↑ http://www.streebog.info/ Arhivat 3 decembrie 2013 la Wayback Machine Open Feature Research Competition
  10. ↑ http://www.streebog.info/news/opredeleny-pobediteli-konkursa-po-issledovaniyu-khesh-funktsii-stribog/ Arhivat 10 septembrie 2015 la Wayback Machine Au fost stabiliți câștigătorii concursului de cercetare a funcției hash Stribog
  11. ↑ Jian Guo, Jérémy Jean, Gaëtan Leurent, Thomas Peyrin, Lei Wang. Utilizarea Counter Revisited: al doilea atac preimagine asupra noii funcții Hash standardizate rusești  (engleză) (29 august 2014). Consultat la 3 noiembrie 2015. Arhivat din original pe 4 martie 2016.
  12. ↑ Alex Biryukov, Leo Perrin, Aleksei Udovenko. The Secret Structure of the S-Box of Streebog, Kuznechik and Stribob  (în engleză) (14 august 2015). Consultat la 3 noiembrie 2015. Arhivat din original pe 8 septembrie 2015.
  13. ↑ Alex Biryukov, Leo Perrin, Aleksei Udovenko. Reverse-Engineering the S-Box of Streebog, Kuznyechik and STRIBOBr1 (Versiunea completă)  (engleză) (26 ianuarie 2016). Preluat la 22 februarie 2017. Arhivat din original la 16 iulie 2017.
  14. ↑ Leo Perrin. Partiții în S-Box din Streebog și Kuznyechik (29 ianuarie 2019). Preluat la 25 august 2020. Arhivat din original la 14 noiembrie 2020.
  15. ↑ Virgil Security Inc. O altă ciudățenie în algoritmii GOST Grasshopper și Stribog . habr.com . Preluat la 25 august 2020. Arhivat din original la 7 noiembrie 2020.
  16. ↑ P. A. Lebedev. Comparație dintre standardele RF vechi și noi pentru funcția hash criptografică pe procesoarele și GPU-urile NVIDIA . Institutul de Electronică și Matematică din Moscova, Școala Superioară de Economie a Universității Naționale de Cercetare (2012). Preluat la 25 august 2020. Arhivat din original la 18 aprilie 2021.
  17. ↑ GitHub - okazymyrov/stribog . Preluat la 3 decembrie 2013. Arhivat din original la 11 iunie 2018.
  18. ↑ Riham AlTawy și Amr M. Youssef. Watch your Constants: Malicious Streebog  (engleză) (8 octombrie 2013). Consultat la 3 noiembrie 2015. Arhivat din original pe 4 martie 2016.
  19. ↑ V.I. Rudskoy. Pe algoritmul de generare a constantelor funcției de hashing Stribog . Preluat la 26 decembrie 2019. Arhivat din original la 26 decembrie 2019.
  20. ↑ V. Rudskoy. Notă despre originea constantelor Streebog  . Preluat la 26 decembrie 2019. Arhivat din original la 2 martie 2021.

Link -uri

 Funcții hash
scop general
Criptografic
Funcții de generare a cheilor
Numărul de verificare ( comparație )
Hashes