NIST SP 800-90A - ("SP" on lyhenne sanoista S erityinen julkaisu " , "erikoisjulkaisu") on National Institute of Standards and Technologyn ( NIST ) julkaisu , jonka otsikko on "Suositus satunnaislukujen generoimiseksi determinististen generaattoreiden avulla satunnaiset bitit "( eng. "Suositus satunnaislukujen generointiin käyttämällä deterministisiä satunnaisbittigeneraattoreita" ). Julkaisu sisältää kuvaukset kolmesta oletettavasti kryptografisesti turvallisesta näennäissatunnaisten lukugeneraattorista , joita käytetään kryptografiassa : Hash_DRBG (perustuu hash-funktioihin ), HMAC_DRBG (perustuu sanoman todennushajautukseen ) ja CTR_DRBG (perustuu lohkosalauksiin laskuritilassa ) .
24.6.2015 alkaen julkaisun nykyinen versio on Versio 1 ( " Versio 1" ). Aiemmissa versioissa oli neljäs generaattori, Dual_EC_DRBG (perustuu elliptiseen kryptografiaan ). Myöhemmin kerrottiin, että Dual_EC_DRBG sisältää todennäköisesti kleptografisen takaoven , jonka National Security Agency on toteuttanut , kun taas useat kryptografit ovat hyväksyneet kolme muuta satunnaislukugeneraattoria yhtenäisiksi ja turvallisiksi [1] [2] .
NIST SP 800-90A on julkinen ja julkisessa käytössä, koska se on Yhdysvaltain liittovaltion hallituksen tekemä tutkimus .
HASH-DRBG perustuu tiivistefunktioon SH : {0, 1} ∗ → {0, 1} l kryptografisten hajautusfunktioiden SHA-perheestä [3] . Tila on muotoa S = (V, C, cnt) , jossa V ∈ {0, 1} len on laskuri, joka tiivistetään lehtilohkojen luomiseksi, joiden arvo päivittyy jokaisen generaattorikutsun aikana; С on vakio, joka riippuu pääelementistä ( eng. seed ), ja cnt on täyttölaskuri. cnt ilmaisee näennäissatunnaisten bittien pyyntöjen lukumäärän sen jälkeen, kun uusi arvo vastaanotettiin todelliselta satunnaisgeneraattorilta ilmentymisen tai uudelleenpopuloinnin aikana.
HASH-DRBG:n luontialgoritmi. Jos kutsussa käytetään lisätuloa generointiin, se hajautetaan ja lisätään laskuriin V modulo 2 len alustusprosessin aikana. Tuloslohkot rj muodostetaan sitten tiivistämällä laskuri V. Puhelun lopussa laskuri hajautetaan erillisellä etuliitteellä ja tuloksena oleva merkkijono sekä vakio C ja cnt lisätään V :hen, tällaisen toimenpiteen tulos annetaan päivitettynä laskurina.
Vakio C päivitetään vain uudelleenkansoituksen aikana (kun se on jälleen uuden muuttujan V johdannainen ) ja lisätään tilamuuttujaan V jokaisen tilapäivityksen yhteydessä. Vakio C varmistaa, että vaikka edellinen laskuri V toistuisi jossain vaiheessa eri täyttöjaksoilla (melkein varmasti eri), laskuri estää edellistä tilasarjaa toistumasta seuraavan arvon päivityksen yhteydessä. Standardi määrittelee V ja C kriittisiksi turvallisuustilan muuttujiksi [3] .
Syöttötiedot: S = (V, C, cnt), β, addin Tulos: S' = (V', C, cnt'), R jos 0 ← check(S, β, addin) sitten Palautus (virhe, ⊥) jos addin ≠ ε niin w ← SH(0x02||V||lisäys) V0 = (V + w) mod 2^len muuten V(0) ← V lämpötila ← e m ← [β/l] kun j = 1, . . . , teen r(j) ← SH(V(j-1)) V(j) ← (V(j−1) + 1) mod 2^len lämpötila ← lämpötila||r(j) R ← vasen (lämpö, β) H ← SH(0x03||V(0)) V' ← (V(0) + H + C + cnt) mod 2^len cnt' ← cnt + 1 paluu (V', C, cnt')HMAC on hash-pohjainen viestin todennuskoodi, jonka Mihir Bellare ja kollegat esittelivät [ 4] ja standardisoitiin myöhemmin [5] . HMAC-DRBG käyttää HMAC:ta: {0, 1} l ×{0, 1} * → {0, 1} l pseudosatunnaisten lähtölohkojen luomiseen. Tila on muotoa S = (K, V, cnt) , jossa standardi määrittelee K ja V turvallisuuskriittisiksi salaisen tilamuuttujiksi. Oletetaan, että alustuksen jälkeen alkutila on S 0 = (K 0 , V 0 , cnt 0 ) , missä cnt 0 = 1 ja K 0 , V 0 ← {0, 1} len . Tässä HMAC-avaimena käytetään K ∈ {0, 1} l , V ∈ {0, 1} l on laskuri ja cnt tarkoittaa täyttölaskuria [3] .
Generointialgoritmi käyttää päivitystoimintoa, jolla lisätään tilamuuttujiin K ja V mahdolliset lisäsyötteet ja päivitetään molemmat yksisuuntaisesti. Jos puheluun sisältyy lisäsyöttö, suoritetaan ylimääräinen päivityspari. Itse HMAC-DRBG:n generointialgoritmi toimii seuraavasti: alustusprosessi lisää tilamuuttujiin mahdolliset lisäsyötteet päivitystoiminnon kautta; jos puheluun ei sisälly lisätuloja, tila pysyy ennallaan. K 0 : lle , V 0 : lle merkitään tätä prosessia vastaavat tilamuuttujat, minkä jälkeen tuloksena olevat lohkot generoidaan automaattisesti soveltamalla iteratiivisesti HMAC(K 0 ,·) -algoritmia virtalaskimelle V j-1 , lähtölohko r j ja laskurin Vj seuraava arvo on yhtä suuri kuin tuloksena oleva merkkijono. Avain K 0 pysyy muuttumattomana jokaisen iteraation ajan. Kun puhelu on valmis, viimeinen prosessi päivittää K :n ja V :n päivitystoiminnolla [3] . päivitystoiminto
Syöttötiedot: addin, K, V Lähtötiedot: K, V K ← HMAC(K, V||0x00||lisäys) V ← HMAC(K, V) jos addin ≠ ε niin K ← HMAC(K, V||0x01||lisäys) V ← HMAC(K, V) paluu (K, V)luoda toimintoa
Syöttötiedot: S = (K, V, cnt), β, addin Tulos: S' = (K', V', cnt'), R jos 0 ← check(S, β, addin) sitten palautus (virhe, ⊥) jos addin ≠ ε niin (K0, V0) ← päivitys(addin, K, V) muuten (K0, V(0)) ← (K, V) lämpötila ← e ; m ← [β/l] kun j = 1, . . . , teen V(j) ← HMAC(K0, V(j−1)) r(j) ← V(j) lämpötila ← lämpötila||r(j) R ← vasen (lämpö, β) (K', V') ← päivitys(addin, K0, V(m)) cnt' ← cnt + 1 paluu (R, (K', V', cnt'))CTR_DRBG perustuu lohkosalausalgoritmiin, jonka salaustoimintoa E : {0, 1} k × {0, 1} l → {0, 1} l käytetään CTR-tilassa (laskuritilassa). Tilalla on muotoa S = (K, V, cnt) , jossa K ∈ {0, 1} k käytetään lohkosalauksen avaimena, V ∈ {0, 1} l on laskuri ja cnt tarkoittaa täyttölaskuri. Standardin mukaan K ja V ovat kriittisiä turvallisuustilan muuttujia. Alustus palauttaa alkutilan S 0 = (К 0 , V 0 , cnt 0 ) , missä cnt 0 = 1 ja K 0 ← {0, 1} k , V 0 ← {0, 1} l [3] .
Kuten HMAC_DRBG:ssä, algoritmi käyttää päivitystoimintoa tilamuuttujien K ja V päivittämiseen yksisuuntaisesti sekä mahdollisten lisätietosyötteiden sisällyttämiseen (jotka välitetään päivitysfunktiolle annettu_data-parametrin kautta). Funktio suorittaa lohkosalauksen CTR-tilassa käyttämällä nykyistä avainta ja laskuria, ketjuttaen tuloksena olevat lähtölohkot r j . Sitten vasemmanpuoleiset κ+l - bitit katkaistaan ja annetut_data-arvot rivitetään XOR-operaatiolla. Jokainen muu prosessi kutsuu päivitysfunktiota siten, että se varmistaa, että annettu_data on täsmälleen κ+l bittiä pitkä [3] .
CTR_DRBG:lle on kaksi vaihtoehtoa riippuen siitä, käytetäänkö generointitoimintoa. CTR_DRBG df -generointifunktio yhdistää CBC-MAC-pohjaisen funktion kykyyn poimia lähes tasainen tulos riittävän korkean entropian tuloista. Jos generoivaa funktiota df ei käytetä, lisäsyötemerkkijonojen addin pituus on enintään (κ + l) — bittiä. Alustusprosessi yhdistää jokaisen lisäsyötteen päivitysfunktioon: jos käytetään generointifunktiota, lisäsyötemerkkijono on (κ + l) -bittien merkkijono, jossa on CTR_DRBG df ennen tämän prosessin aloittamista. Jos lisäsyöttöä ei käytetä, tila pysyy ennallaan ja addinin arvo on 0 (κ+l) (jotta muodostuu päivitysfunktion syöte viimeisen proseduurin aikana, kun puhelu päättyy). Tuloslohkot rj luodaan sitten iteratiivisesti lohkosalauksen kanssa CTR-tilassa. Avain K pysyy samana kaikissa näissä iteraatioissa. Kun puhelu on valmis, viimeinen prosessi päivittää sekä K:n että V:n päivityskutsulla [3] . päivitystoiminto
Syöttötiedot: toimitetut tiedot, K, V Lähtötiedot: K, V lämpötila ← e m ← [(κ + l)/l] kun j = 1, . . . , teen V ← (V + 1) mod 2^l C(i) ← E(K, V) lämpötila ← temp||Ci lämpötila ← vasen (lämpö, (κ + l)) K||V ← temp ⊕ toimitetut tiedot paluu (K, V)luoda toimintoa
Syöttötiedot: S = (K, V, cnt), β, addin Tulos: S' = (K', V', cnt'), R jos 0 ← check(S, β, addin) sitten palautus (virhe, ⊥) jos addin ≠ ε niin jos johdannaisfunktiota käytetään silloin addin ← df(addin, (κ + l)) else if len(addin) < (κ + l) sitten addin ← addin||0^(κ+l−len(addin)) (K0, V0) ← päivitys(addin, K, V ) muu addin ← 0^κ+l; (K0, V(0)) ← (K, V) lämpötila ← e ; m ← [β/l] kun j = 1, . . . , teen V(j) ← (V(j−1) + 1) mod 2^l r(j) ← E(K0, V(j)) lämpötila ← lämpötila||r(j) R ← vasen (lämpö, β) (K', V') ← päivitys(addin, K0, V(m)) cnt' ← cnt + 1 paluu (R, (K', V', cnt'))Dual_EC_DRBG poistettiin julkaisusta, kun asiakirjan ensimmäinen versio julkaistiin. Syynä tähän oli takaoven mahdollinen olemassaolo . Takaovi on tahallisesti sisäänrakennettu virhe algoritmiin, joka sallii luvattoman pääsyn tietoihin tai tietokoneen kauko-ohjauksen [6] .
Osana Bullrun- ohjelmaa NSA lisää takaovia salausjärjestelmiin. Dual_EC_DRBG oli oletettavasti yksi tavoitteista vuonna 2013 [7] . Standardointityössä NSA saavutti sen, mistä lopulta tuli standardin ainoa toimittaja [8] . Käytettäessä NIST SP 800-90A:ssa hyväksyttyä Dual_EC_DRBG:tä NSA mainitsi, että tunnettu tietoturvayritys RSA Security käytti Dual_EC_DRBG:tä tuotteissaan. Kuitenkin NSA maksoi RSA Securitylle 10 miljoonaa dollaria Dual_EC_DRBG:n oletuksena käyttämisestä tuotteissaan. Reuters kuvailee sopimusta "yritysjohtajien, ei puhtaiden tekniikkojen, laatimana". Koska Reuters kuvaili 10 miljoonan dollarin sopimusta RSA Securityn pakottamiseksi käyttämään Dual_EC_DRBG:tä salaiseksi, Dual_EC_DRBG:n NIST SP 800-90A:n käyttöönottoprosessiin osallistuneet ihmiset eivät väittäneet tienneet tästä ilmeisestä eturistiriidasta [9] . Tämä voi auttaa selittämään, kuinka satunnaislukugeneraattori, joka myöhemmin osoittautui huonommaksi kuin vaihtoehtoja (todennäköisen takaoven lisäksi), otettiin käyttöön standardina NIST SP 800-90A:ssa.
Vaikka Dan Shumov ja Nils Ferguson dokumentoivat Dual_EC_DRBG:n takaoven potentiaalin jo vuonna 2007 [10] , RSA Securityn kaltaiset yritykset käyttivät sitä edelleen tuotteissa vuoteen 2013 asti [1] . Kun otetaan huomioon Dual_EC_DRBG:n tunnetut puutteet, myöhemmin nousi esiin väitteitä, että RSA Security lisäsi tarkoituksella NSA-takaoven tuotteisiinsa. RSA kiistää tietoisesti lisääneensä takaoven tuotteisiinsa [11] .
Takaoven löytymisen jälkeen NIST aloitti uudelleen NIST SP 800-90A [7] [12] hallituksen tarkistusprosessin . NIST SP 800-90A:n tarkistettu versio, josta Dual_EC_DRBG poistettiin, julkaistiin kesäkuussa 2015 [13] .
Hash_DRBG:llä ja HMAC_DRBG:llä on turvatodisteet näennäissatunnaisten sekvenssien luomiseksi [14] . Hash_DRBG:n ja HMAC_DRBG:n turvallisuustodisteasiakirjassa mainitaan Dual_EC_DRBG:n tietoturvayritykset, joissa todetaan, että CTR_DRBG:tä ei pitäisi käyttää, koska se on ainoa generaattori NIST SP 800-90A:ssa, jolle ei ole turvatodistusta [14] .
HMAC_DRBG:llä on myös koneella varmennettu suojaustodistus [15] . Opinnäytetyö, joka sisältää laskennallisesti varmennetun suojaustodistuksen, osoittaa myös, että oikein toteutetun HMAC_DRBG-instanssin murtaminen ei vaaranna ennen murtumista luotujen numeroiden turvallisuutta [15] .
CTR_DRBG:llä on osoitettu olevan tietoturvaongelmia, kun sitä käytetään tiettyjen parametrien kanssa, koska kryptografit eivät huomioineet salauslohkon kokoa tätä näennäissatunnaislukugeneraattoria suunnitellessaan [16] . CTR_DRBG näyttää olevan turvallinen ja mahdoton erottaa todellisesta satunnaislähteestä, kun AES :ää käytetään taustalla olevan lohkosalauksena ja 112 bittiä otetaan tästä näennäissatunnaislukugeneraattorista [16] . Kun AES:ää käytetään taustalla olevana lohkosalauksena ja kustakin esiintymästä otetaan 128 bittiä, tarvittava suojaustaso asetetaan sillä ehdolla, että laskuritilassa olevan 128-bittisen salauksen tulos voidaan erottaa todellisesta satunnaislukugeneraattorista [16 ] . Kun AES:tä käytetään taustalla olevan lohkosalauksena ja yli 128 bittiä otetaan tästä näennäissatunnaislukugeneraattorista, tuloksena olevaa suojaustasoa rajoittaa lohkon koko, ei avaimen koko, joten todellinen suojaustaso on paljon pienempi. kuin avaimen koon edellyttämä suojaustaso [16] . On myös osoitettu, että CTR_DRBG ei voi tarjota odotettua suojaustasoa käytettäessä Triple DES :ää, koska sen 64-bittinen lohkokoko on paljon pienempi kuin Triple DES:ssä käytetty 112-bittinen avainkoko [16] .
Dual_EC_DRBG:n Security Proof Attempt väittää, että Dual_EC_DRBG edellyttää kolmea ongelmaa ollakseen NP suojattu : Diffie-Hellman- tehtävä , diskreetti logaritmiongelma ja katkaistun pisteen ongelma [17] . Diffie-Hellmanin päätösongelma on laajalti tunnustettu matemaattisesti vaikeaksi [17] . Diskreetti logaritmiongelma ei ole laajalti hyväksytty NP-luokassa, jotkut todisteet osoittavat, että tämä ongelma on vaikea, mutta eivät todista sitä [17] . Turvatodiste on siksi kyseenalainen, ja se voidaan mitätöidä, jos diskreetin logaritmin ongelman osoitetaan olevan pikemminkin ratkaistava kuin matemaattisesti vaikea. Katkaistun pisteen ongelma edellyttää, että Dual_EC_DRBG:n valitsemasta pisteestä katkaistaan tarpeeksi bittejä, jotta sitä ei voida erottaa todella satunnaisluvusta [17] . on kuitenkin osoitettu, että Dual_EC_DRBG-standardin oletusarvoinen 16-bittinen katkaisu ei riitä tekemään tulosta erottumattomaksi todellisesta satunnaislukugeneraattorista [18] ja tekee siksi Dual_EC_DRBG-suojaustodistuksen mitättömäksi käytettäessä oletusarvoista katkaisuarvoa.
Yllä olevat algoritmit ovat standardeja, ja suuret yritykset käyttävät niitä luodakseen omia tuotteitaan niiden pohjalta. Joten Microsoft luomassa CryptoApi -päivitystä nimeltä "Cryptography API: Next Generation (CNG)" asetti pseudosatunnaislukugeneraattorin oletusarvoksi CTR_DRBG [19] .
Intel käyttää myös CTR_DRBG:tä [20] satunnaisluvun luomiseen käyttämällä sisäänrakennettua satunnaislukugeneraattoria RdRand - käskyssä .