Stribog (hash-funktio)

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 15. heinäkuuta 2021 tarkistetusta versiosta . tarkastukset vaativat 6 muokkausta .
Stribog
Kehittäjät Venäjän FSB ,
OJSC "InfoTeKS"
julkaistu 2012
Standardit GOST 34.11-2018, GOST R 34.11-2012, ISO/IEC 10118-3:2018, RFC 6986
Hash-koko 256 tai 512 bittiä
Kierrosten lukumäärä 12
Tyyppi hash-toiminto

Stribog  ( STREEBOG  [ 1] ) on salausalgoritmi hash-funktion laskemiseen , kun syötetietolohkon koko on 512 bittiä ja hash-koodin koko on 256 tai 512 bittiä .

Kuvattu GOST 34.11-2018 "Tietotekniikka. Tietojen kryptografinen suojaus . Hajautusfunktio "- nykyinen osavaltioiden välinen salausstandardi .

Venäjän liittovaltion turvallisuuspalvelun tietoturva- ja erityisviestintäkeskuksen kehittämä JSC InfoTeKS : n osallistuminen Venäjän federaation kansalliseen standardiin GOST R 34.11-2012 ja voimaan 1.6.2019 Rosstandartin määräyksellä . 4. joulukuuta 2018 päivätty nro 1060-st .

GOST R 34.11-2012 -standardi kehitettiin ja otettiin käyttöön korvaamaan vanhentunut standardi GOST R 34.11-94 :

Kehittämistarve <...> johtuu tarpeesta luoda hajautustoiminto, joka täyttää nykyaikaiset kryptografisen vahvuuden vaatimukset ja GOST R 34.10-2012 sähköisen digitaalisen allekirjoituksen standardin vaatimukset .

— Standardin teksti. Johdanto.

Hajautusfunktion nimeä - " Stribog ", slaavilaisen jumaluuden nimen jälkeen - käytetään usein standardin virallisen nimen sijasta, vaikka sitä ei nimenomaisesti mainita sen tekstissä (katso alla ).

Käsitteet Stribog-hash-funktion rakentamiseen

RusCrypto-2010-konferenssissa esitettyjen vaatimusten mukaisesti uutta hash-funktiota koskevassa työssä [2] :

Samassa työssä esitetään "universaalit" vaatimukset, jotka koskevat hash-toimintoon kohdistuvien hyökkäysten monimutkaisuutta:

Tehtävä Monimutkaisuus
prototyypin rakentaminen 2n _
törmäyksen rakentaminen 2n/ 2
toisen prototyypin rakentaminen 2 n / (viestin pituus)
prototyypin pidentäminen 2n _

GOST R 34.11-2012 ja GOST R 34.11-94 vertailu

Pakkaustoiminto

Hash-funktiossa tärkeä elementti on pakkausfunktio. GOST R 34.11-2012:ssa pakkaustoiminto perustuu Miaguchi-Prenel-suunnitteluun . Kaavio Miaguchi-Prenel-suunnittelusta: h, m - vektorit syötetään pakkausfunktioon; g(h, m) on pakkausfunktion tulos; E on lohkosalaus, jonka lohkon ja avaimen pituus on 512 bittiä. XSPL-salaus otetaan lohkosalauksena GOST R 34.11-2012 hash-funktiossa. Tämä salaus koostuu seuraavista muunnoksista:

Uudessa hash-funktiossa käytetyt muunnokset tulee ymmärtää hyvin. Siksi lohkosalauksessa E käytetään muunnoksia X, S, P, L, jotka ovat hyvin tutkittuja.

Lohkosalauksen tärkeä parametri on se, kuinka avain valitaan käytettäväksi kullakin kierroksella. GOST R 34.11-2012:ssa käytetyssä lohkosalauksessa avaimet , , ... , jokaiselle 13 kierrokselle luodaan käyttämällä itse salaustoimintoa.

, , … ,  ovat iteratiivisia vakioita, jotka ovat 512-bittisiä vektoreita. Niiden merkitykset on määritelty standardin asiaa koskevassa osassa.

Kuvaus

Hash-funktio perustuu Merkle-Damgorin iteratiiviseen konstruktioon MD-vahvistuksella. MD-vahvistus ymmärretään epätäydellisen lohkon lisäämisenä laskettaessa hash-funktiota täydelliseen lisäämällä sen pituinen vektori (0 ... 01), että saadaan täydellinen lohko. Lisäelementtien joukossa on huomioitava seuraavat:

Yllä kuvattujen ratkaisujen avulla voit torjua monia tunnettuja hyökkäyksiä.

Lyhyt kuvaus hash-funktiosta GOST R 34.11-2012 voidaan esittää seuraavasti. Hajautusfunktion syöte on mielivaltaisen kokoinen viesti. Lisäksi viesti jaetaan 512-bittisiksi lohkoiksi, jos sanoman koko ei ole 512:n kerrannainen, sitä täydennetään tarvittavalla määrällä bittejä. Tällöin pakkausfunktiota käytetään iteratiivisesti, minkä seurauksena tiivistefunktion sisäinen tila päivitetään . Myös lohkon tarkistussumma ja käsiteltyjen bittien määrä lasketaan . Kun kaikki alkuperäisen viestin lohkot on käsitelty, suoritetaan vielä kaksi laskutoimitusta, jotka täydentävät hash-funktion laskennan:

Alexander Kazimirovin ja Valentina Kazimirovan [5] teoksessa on esitetty graafinen esitys hash-funktion laskemisesta.

Analyysi

Turvallisuus

Vanhan standardin krypta-analyysi paljasti joitakin sen heikkouksia teoreettisesta näkökulmasta. Siten yhdessä GOST R 34.11-94:n kryptausanalyysille omistetussa julkaisussa [6] havaittiin, että esikuvan rakennusalgoritmin monimutkaisuus on arvioitu 2192 pakkausfunktion laskelmaan, törmäys 2105 , joka on pienempi kuin "universaalit" arviot, jotka GOST R 34.11-94:lle on yhtä suuri kuin 2256 ja 2128 . Vaikka vuodesta 2013 lähtien uuden tiivistefunktion kryptografiseen vahvuuteen ei ole omistettu paljon töitä, voimme uuden hash-funktion suunnittelun perusteella tehdä joitain johtopäätöksiä sen kryptografisesta vahvuudesta ja olettaa että sen salausvastus on suurempi kuin GOST R 34.11-94:

Vuonna 2013 "Cryptology ePrint Archive: Listing for 2013" -sivusto julkaisi kaksi artikkelia uuden hash-funktion kryptausanalyysistä. Artikkeli "Rebound attack on Stribog" [7] tutkii hash-funktion kestävyyttä "The Rebound attack" -nimistä hyökkäystä vastaan; tämä hyökkäys perustuu "kiertosalausanalyysiin" ja differentiaaliseen kryptausanalyysiin . Kryptanalyytikot käyttivät "free-start"-nimistä menetelmää etsiessään haavoittuvuuksia. Tämä tarkoittaa, että hash-koodia laskettaessa tietty hash-funktion tila on kiinteä, ja jatkolaskutoimituksissa voidaan mennä sekä hash-koodin laskemiseen että viestin laskemiseen. Kryptanalyytikot onnistuivat saavuttamaan törmäyksen 5 kierroksella ja niin sanottu "lähestörmäys" saatiin aikaan (eli löydettiin kaksi viestiä, joiden hash-koodit eroavat pienessä määrässä bittejä) käyttämällä 7,75 kierrosta. Havaittiin myös, että menetelmä, jolla näppäimet valitaan jokaiselle kierrokselle, lisää vakautta pakkaustoimintoon. On kuitenkin osoitettu, että törmäys on mahdollinen 7,75 kierroksella ja "lähes törmäys" 8,75 ja 9,75.

Artikkeli "Integral Distinguishers for Reduced-round Stribog" [8] käsittelee hajautusfunktion turvallisuutta (pienennetyllä kierrosten määrällä) integraalista kryptausanalyysiä vastaan . Kirjoittajat onnistuivat puristusfunktiota tutkiessaan löytämään eron 4 kierroksella laskettaessa eteenpäin ja 3,5 kierroksella laskettaessa vastakkaiseen suuntaan. Havaittiin myös, että differentiaalinen hyökkäys hash-funktiota vastaan ​​kierroksilla 6 ja 7 vaatii 264 ja 2120 keskimääräistä kierrosta , vastaavasti.

Uuden hash-funktion kryptografisen vahvuuden tutkimiseksi InfoTeKS-yritys ilmoitti kilpailun alkamisesta marraskuussa 2013 [9] ; se päättyi toukokuussa 2015 [10] . Voittaja oli The Usage of Counter Revisited: Second-Preimage Attack on New Russian Standardized Hash Function, jossa kirjoittajat esittivät hyökkäyksen löytääkseen toisen esikuvan Stribog-512 hash-funktiolle, vaatien 2 266 kutsua pakkaustoiminnolle pidempiä viestejä varten. kuin 2 259 lohkoa [11] .

Crypto-2015 -konferenssissa Alex Biryukov , Leo Perrin ja Alexey Udovenko esittivät raportin, jossa todettiin, että Grasshopper -salauksen S-lohkon ja Stribog-hajautusfunktion arvot eivät ole (pseudo)satunnaislukuja, vaan ne on generoitu perustuen. piilotetulla algoritmilla, jonka kaiuttimet onnistuivat palauttamaan käänteissuunnittelumenetelmillä [12] [13] .

29. tammikuuta 2019 julkaistiin tutkimus "Partitions in the S-Box of Streebog and Kuznyechik" [14] , joka kumoaa tekijöiden väitteen satunnaisesta parametrien valinnasta korvaaviin taulukoihin Stribog- ja Kuznyechik-algoritmeissa [15] . .

Suorituskyky

VI kansainväliselle konferenssille "Parallel Computing and Control Problems" (PACO'2012) omistettu sivusto esittelee P. A. Lebedevin artikkelin "Vanhojen ja uusien venäläisten standardien vertailu NVIDIA-suorittimien ja grafiikkasuorittimien kryptografiselle hajautustoiminnolle ", jossa vertailu salaustiivistetoimintojen GOST R 34.11-94 ja GOST R 34.11-2012 suorituskyvystä x86_64-arkkitehtuuriprosessoreissa ja CUDA-tekniikkaa tukevissa NVIDIA- näytönkorteissa [16] .

Suorituskyvyn vertaamiseksi x86_64-prosessorilla otettiin 4 erilaista hash-toimintojen toteutusta:

  1. GOST R 34.11-1994:n toteutus OpenSSL-salauspaketista (versio 1.0.1c) avoimella lähdekoodilla. Tässä toteutuksessa ei ole algoritmisia tai ohjelmistooptimointeja;
  2. GOST R 34.11-1994:n käyttöönotto RHash-ohjelmassa (versio 1.2.9). Tässä toteutuksessa on algoritmi- ja ohjelmistooptimointeja, mukaan lukien kokoonpanooptimoinnit;
  3. GOST R 34.11-2012 täytäntöönpano, kirjoittanut A. Kazimirov [17] ;
  4. GOST R 34.11-1994 ja GOST R 34.11-2012 täytäntöönpano, kirjoittanut P. A. Lebedev.

Käytettiin Intel Core i7-920 -suoritinta 2,67 GHz:n perustaajuudella. Suoritustulokset:

GOST R 34.11-1994 GOST R 34.11-2012
Toteutus nro MB/s Kellot/tavu MB/s Kellot/tavu
yksi kahdeksantoista 143 - -
2 49 52 - -
3 - - 38 67
neljä 64 40 94 27

GPU:n hash-toimintojen vanhojen ja uusien standardien nopeuden vertailu suoritettiin P. A. Lebedevin toteutusten välillä. Käytetty NVIDIA GTX 580 -näytönohjain. Suorituskykytulokset (8192 16 kt datavirtaa):

GOST R 34.11-1994 GOST R 34.11-2012
MB/s Kellot/tavu MB/s Kellot/tavu
1697 - 608 -

Näiden tulosten perusteella päätellään, että GOST R 34.11-2012 hash-toiminto voi olla kaksi kertaa nopeampi kuin GOST R 34.11-94 hash-toiminto nykyaikaisissa prosessoreissa, mutta hitaampi näytönohjainkorteissa ja järjestelmissä, joissa on rajalliset resurssit.

Nämä suorituskykytulokset selittyvät sillä, että uuden hash-funktion laskennassa käytetään vain modulo 2 -lisäyksiä ja tiedonsiirtokäskyjä. Vanha hash-funktio sisältää monia sekoituskäskyjä, jotka eivät sovi hyvin suorittimen käskyjoukkoon. Mutta GOST R 34.11-2012 hash-funktion tilojen ja korvaustaulukoiden lisääntynyt koko hidastaa sitä erittäin rinnakkaisissa laskentajärjestelmissä, kuten GPU:issa.

Lisäksi sen kehittäjät suorittivat tutkimuksen uuden hash-toiminnon suorituskyvystä 64-bittisellä Intel Xeon E5335 2 GHz -prosessorilla. Yksi ydin käytettiin. GOST R 34.11-2012 hash-funktion suorituskyky oli 51 prosessorisykliä 1 tavua kohden hajautettua dataa (noin 40 MB/s). Saatu tulos on 20% parempi kuin vanha hash-funktio GOST R 34.11-94.

Mielenkiintoisia faktoja

Standardin tekstin lopussa on esimerkkejä vaiheittaisesta hash-laskennasta useille alkuarvoille. Yksi näistä arvoista on esimerkin 2 heksadesimaaliluku M 2, jonka pituus on 576 bittiä (72 tavua):

fbe2e5f0eee3c820fbeafaebef20fffbf0e1e0f0f520e0ed20e8ece0ebe5f0f2f120fff0
eeec20f120faf2fee5e2202ce8f6f3ede2202ce8f6f3ede220e120f25f8

x86- tietokoneessa tavujärjestys on matalasta korkeaan , ja vastaava luku muistissa esitetään "käänteisessä" muodossa. Jos muunnat tämän tavujoukon tekstiksi Windows-1251- koodauksella , saat hieman muokatun rivin Wordista Igorin kampanjasta :

Nämä tuulet, Stribozhin lapsenlapset, puhaltavat merestä nuolilla Igorin rohkeisiin kynsiin

Vastauksena kriittiseen artikkeliin "Watch your Constants: Mallicious Streebog" [18] TK26-komitea julkaisi huomautuksen "Algoritmista vakioiden luomiseksi Stribog-hajautusfunktiolle" [19] [20] , jossa selitetään, että pyöreät avainvakiot rakennettiin syötemerkkijonojen muunnokseksi Stribogin kaltaisella hash-funktiolla. Jos nämä syöttöjonot muunnetaan tekstiksi Windows-1251- koodauksella , saadaan standardin tekijöiden nimet:

C i = H init (M) M (heksadesimaalimuodossa) M cp1251 (merkkijono Windows-1251 :ssä )
C1_ _ e2e5ede1e5f0c3 Grebnev
C2_ _ f7e8e2eef0e8ece8e4e0ebc220e9e5e3f0e5d1 Sergei Vladimirovitš
C3_ _ f5f3ecc4 Dmuh
C4_ _ f7e8e2eef0e4ede0f1eae5ebc020e9e5f0e4edc0 Andrei Aleksandrovitš
C5 _ ede8e3fbc4 Dygin
C6 _ f7e8e2eeebe9e0f5e8cc20f1e8ede5c4 Denis Mihailovitš
C7_ _ ede8f5fef2e0cc Matyukhin
C 8 f7e8e2eef0eef2eae8c220e9e8f0f2e8ecc4 Dmitri Viktorovich
C9_ _ e9eeeaf1e4f3d0 Rudskoy
C 10 f7e8e2e5f0eee3c820f0e8ece8e4e0ebc2 Vladimir Igorevitš
C 11 ede8eaf8e8d8 Shishkin
C 12 f7e8e2e5e5f1eae5ebc020e9e8ebe8f1e0c2 Vasili Aleksejevitš

Muistiinpanot

  1. ↑ 17. Dedicated Hash-Function 11 (STREEBOG-512) Arkistoitu 22. tammikuuta 2020 Wayback Machinessa // ISO/IEC 10118-3:2018 IT-suojaustekniikat - Hash-funktiot - Osa 3: Dedicated hash-funktiot.
  2. ↑ Matyukhin D.V., Shishkin V.A., Rudsky V.I. Lupaava hajautusalgoritmi // Raportti RusCrypto'2010 -konferenssissa, 2010.
  3. ↑ Serge Vaudenay (2002). "SSL-, IPSEC-, WTLS- ja CBC-täytesovellusten aiheuttamat tietoturvavirheet". Advances in Cryptology - EUROCRYPT 2002, Proc. Kansainvälinen konferenssi kryptografisten tekniikoiden teoriasta ja sovelluksista. Springer Verlag (2332): 534-545.
  4. ↑ Kenneth G. Paterson; Gaven J. Watson (2008). "Immunising CBC Mode Against Padding Oracle Attacks: Formal Security Treatment". Tietoturva ja kryptografia verkkoihin - SCN 2008, Tietojenkäsittelytieteen luentomuistiinpanot. Springer Verlag (5229): 340-357.
  5. ↑ Lähde . Haettu 1. joulukuuta 2013. Arkistoitu alkuperäisestä 3. joulukuuta 2013.
  6. ↑ F. Mendel, N. Pramstaller, C. Rechberger, M. Kontak, J. Szmidt» CRYPTO 2008
  7. ↑ Riham AlTawy, Aleksandar Kircanski ja Amr M. Youssef. Rebound-hyökkäykset Stribogiin  (englanniksi) (27. elokuuta 2013). Haettu 1. joulukuuta 2013. Arkistoitu alkuperäisestä 3. joulukuuta 2013.
  8. ↑ Riham AlTawy ja Amr M. Youssef. Integral Distinguishers for Reduced-round Stribog  (englanniksi) (8. lokakuuta 2013). Haettu 3. marraskuuta 2015. Arkistoitu alkuperäisestä 4. maaliskuuta 2016.
  9. ↑ http://www.streebog.info/ Arkistoitu 3. joulukuuta 2013 Wayback Machine Open Feature Research Competition -kilpailussa
  10. ↑ http://www.streebog.info/news/opredeleny-pobediteli-konkursa-po-issledovaniyu-khesh-funktsii-stribog/ Arkistoitu 10. syyskuuta 2015 Wayback Machinessa Stribog-hajautusfunktion tutkimuskilpailun voittajat on selvitetty
  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  (englanniksi) (29. elokuuta 2014). Haettu 3. marraskuuta 2015. Arkistoitu alkuperäisestä 4. maaliskuuta 2016.
  12. ↑ Alex Biryukov, Leo Perrin, Aleksei Udovenko. Streebogin, Kuznechikin ja Stribobin S-Boxin salainen rakenne  (englanniksi) (14. elokuuta 2015). Haettu 3. marraskuuta 2015. Arkistoitu alkuperäisestä 8. syyskuuta 2015.
  13. ↑ Alex Biryukov, Leo Perrin, Aleksei Udovenko. Streebogin, Kuznyechikin ja STRIBOBr1:n (täysi versio)  (englanninkielinen) S-Boxin käänteinen suunnittelu ( 26. tammikuuta 2016). Haettu 22. helmikuuta 2017. Arkistoitu alkuperäisestä 16. heinäkuuta 2017.
  14. ↑ Leo Perrin. Väliseinät Streebogin ja Kuznyechikin S-Boxissa (29.1.2019). Haettu 25. elokuuta 2020. Arkistoitu alkuperäisestä 14. marraskuuta 2020.
  15. ↑ Virgil Security Inc. Toinen omituisuus GOST-algoritmeissa Grasshopper ja Stribog . habr.com . Haettu 25. elokuuta 2020. Arkistoitu alkuperäisestä 7. marraskuuta 2020.
  16. ↑ P. A. Lebedev. Vanhojen ja uusien RF-standardien vertailu NVIDIA-suorittimien ja grafiikkasuorittimien kryptografiselle hajautustoiminnolle . Moskovan elektroniikan ja matematiikan instituutti, Kansallisen tutkimusyliopiston kauppakorkeakoulu (2012). Haettu 25. elokuuta 2020. Arkistoitu alkuperäisestä 18. huhtikuuta 2021.
  17. ↑ GitHub - okazymyrov/stribog . Haettu 3. joulukuuta 2013. Arkistoitu alkuperäisestä 11. kesäkuuta 2018.
  18. ↑ Riham AlTawy ja Amr M. Youssef. Katso Constants: Malicious Streebog  (englanniksi) (8. lokakuuta 2013). Haettu 3. marraskuuta 2015. Arkistoitu alkuperäisestä 4. maaliskuuta 2016.
  19. ↑ V.I. Rudskoy. Algoritmista Stribog-hajautusfunktion vakioiden generoimiseksi . Haettu 26. joulukuuta 2019. Arkistoitu alkuperäisestä 26. joulukuuta 2019.
  20. ↑ V. Rudskoy. Huomautus Streebog-vakioiden  alkuperästä . Haettu 26. joulukuuta 2019. Arkistoitu alkuperäisestä 2. maaliskuuta 2021.

Linkit

 Hash-funktiot
yleinen tarkoitus
Kryptografinen
Avainten luontitoiminnot
Tarkista numero ( vertailu )
Hashes