NIST SP 800-90A - ("SP" er en forkortelse for Special Publication " , "special publication") er en publikation fra National Institute of Standards and Technology ( NIST ) med titlen "Anbefaling til generering af tilfældige tal ved hjælp af deterministiske generatorer random bits "( eng. "Anbefaling for generering af tilfældige tal ved brug af deterministiske tilfældige bitgeneratorer" ). Publikationen indeholder beskrivelser af tre angiveligt kryptografisk sikre pseudo-tilfældige talgeneratorer til brug i kryptografi : Hash_DRBG (baseret på hash-funktioner ), HMAC_DRBG (baseret på meddelelsesgodkendelses-hash ) og CTR_DRBG (baseret på blokcifre i tællertilstand ).
Fra den 24. juni 2015 er den aktuelle version af publikationen Revision 1 ( " Revision 1" ). Tidligere versioner inkluderede en fjerde generator, Dual_EC_DRBG (baseret på elliptisk kryptografi ). Det blev senere rapporteret, at Dual_EC_DRBG sandsynligvis indeholder en kleptografisk bagdør , implementeret af National Security Agency , mens de andre tre tilfældige talgeneratorer accepteres som konsistente og sikre af flere kryptografer [1] [2] .
NIST SP 800-90A er i det offentlige domæne og er i det offentlige domæne, da det er en undersøgelse foretaget af den amerikanske føderale regering .
HASH-DRBG er baseret på hash-funktionen SH : {0, 1} ∗ → {0, 1} l fra SHA-familien af kryptografiske hash-funktioner [3] . Tilstanden har formen S = (V, C, cnt) , hvor V ∈ {0, 1} len er en tæller, der hashes for at skabe bladblokke, hvis værdi opdateres under hvert generatorkald; С er en konstant afhængig af det overordnede element ( eng. frø ), og cnt er genopfyldningstælleren. cnt angiver antallet af anmodninger om pseudotilfældige bit siden den nye værdi modtaget fra den sande tilfældige generator under instansiering eller genpopulation.
Generationsalgoritme for HASH-DRBG. Hvis et ekstra input bruges i opkaldet til at generere, hashes det og tilføjes til tælleren V modulo 2 len under initialiseringsprocessen. Udgangsblokkene rj dannes derefter ved at hashe tælleren V . Ved afslutningen af opkaldet hashes tælleren med et separat præfiks, og den resulterende streng, sammen med konstanten C og cnt , tilføjes til V , resultatet af en sådan operation er givet som den opdaterede tæller.
Konstanten C opdateres kun under genpopulation (når den igen er en afledt af den nye variabel V ) og tilføjes til tilstandsvariablen V under hver tilstandsopdatering. Konstanten C sørger for, at selvom den forrige tæller V duplikeres på et tidspunkt i forskellige genopfyldningsperioder (næsten helt sikkert forskellige), vil tælleren forhindre den forrige sekvens af tilstande i at gentage sig, næste gang værdien opdateres. Standarden definerer V og C som kritiske sikkerhedstilstandsvariable [3] .
Indgangsdata: S = (V, C, cnt), β, addin Output: S' = (V', C, cnt'), R hvis 0 ← check(S, β, addin) så Retur (fejl, ⊥) hvis addin ≠ ε så w ← SH(0x02||V||tilføjelse) V0 = (V + w) mod 2^len andet V(0) ← V temp ← e m ← [β/l] for j = 1, . . . , jeg gør r(j) ← SH(V(j−1)) V(j) ← (V(j−1) + 1) mod 2^len temp ← temp||r(j) R ← venstre(temp, β) H ← SH(0x03||V(0)) V' ← (V(0) + H + C + cnt) mod 2^len cnt' ← cnt + 1 returnere (V', C, cnt')HMAC er en hash-baseret meddelelsesgodkendelseskode, der blev introduceret af Mihir Bellare og kolleger [ 4] og efterfølgende standardiseret [5] . HMAC-DRBG bruger HMAC: {0, 1} l ×{0, 1} * → {0, 1} l til at generere pseudo-tilfældige outputblokke. Staten har formen S = (K, V, cnt) , hvor standarden definerer K og V som sikkerhedskritiske hemmelige tilstandsvariable. Det antages, at starttilstanden efter initialisering er S 0 = (K 0 , V 0 , cnt 0 ) , hvor cnt 0 = 1 og K 0 , V 0 ← {0, 1} len . Her bruges K ∈ {0, 1} l som HMAC-nøgle, V ∈ {0, 1} l er tælleren, og cnt angiver genopfyldningstælleren [3] .
Genereringsalgoritmen bruger opdateringsfunktionen, som bruges til at tilføje yderligere input til tilstandsvariablerne K og V , og opdaterer begge envejs. Hvis yderligere input er inkluderet i opkaldet, udføres et ekstra par opdateringer. Selve genereringsalgoritmen for HMAC-DRBG fungerer som følger: initialiseringsprocessen tilføjer yderligere input til tilstandsvariablerne via opdateringsfunktionen; hvis yderligere input ikke er inkluderet i opkaldet, forbliver tilstanden uændret. For K 0 , V 0 betegner vi tilstandsvariablerne svarende til denne proces, hvorefter de resulterende blokke automatisk genereres ved iterativt at anvende HMAC(K 0 ,·) -algoritmen for strømtælleren Vj -1 , outputblokken rj og den næste værdi af tælleren Vj er lig med den resulterende streng. Nøglen K 0 forbliver uændret gennem hver iteration. Når opkaldet er afsluttet, opdaterer den sidste proces K og V med opdateringsfunktionen [3] . opdateringsfunktion
Inputdata: addin, K, V Outputdata: K, V K ← HMAC(K, V||0x00||tilføjelse) V ← HMAC(K, V) hvis addin ≠ ε så K ← HMAC(K, V||0x01||tilføjelse) V ← HMAC(K, V) retur (K, V)generere funktion
Indgangsdata: S = (K, V, cnt), β, addin Output: S' = (K', V', cnt'), R hvis 0 ← check(S, β, addin) så returnere (fejl, ⊥) hvis addin ≠ ε så (K0, V0) ← opdatering(tilføjelse, K, V) andet (K0, V(0)) ← (K, V) temp ← e ; m ← [β/l] for j = 1, . . . , jeg gør V(j) ← HMAC(K0, V(j−1)) r(j) ← V(j) temp ← temp||r(j) R ← venstre(temp, β) (K', V') ← opdatering(addin, K0, V(m)) cnt' ← cnt + 1 returnere (R, (K', V', cnt'))CTR_DRBG er baseret på en blokchifferalgoritme, hvis chifferfunktion E: {0, 1} k × {0, 1} l → {0, 1} l bruges i CTR-tilstand (tællertilstand). Tilstanden har formen S = (K, V, cnt) , hvor K ∈ {0, 1} k bruges som nøglen til blokchifferet, V ∈ {0, 1} l er tælleren, og cnt angiver genopfyldningstæller. Standarden angiver, at K og V er kritiske sikkerhedstilstandsvariable. Initialisering returnerer starttilstanden S 0 = (К 0 , V 0 , cnt 0 ) , hvor cnt 0 = 1 og K 0 ← {0, 1} k , V 0 ← {0, 1} l [3] .
Som i HMAC_DRBG bruger algoritmen opdateringsfunktionen til at opdatere tilstandsvariablerne K og V envejs samt til at inkludere eventuelle yderligere datainput (som videregives til opdateringsfunktionen via parameteren provided_data). Funktionen kører blokchifferet i CTR-tilstand ved hjælp af den aktuelle nøgle og tæller, og sammenkæder de resulterende outputblokke r j . Derefter afkortes de κ+l bits længst til venstre, og de angivne_data-værdier er inlinet ved hjælp af XOR-operationen. Opdateringsfunktionen kaldes af hver af de andre processer på en sådan måde, at den sikrer, at forsynede_data er nøjagtigt κ+l bit lange [3] .
Der er to muligheder for CTR_DRBG afhængigt af om genereringsfunktionen bliver brugt. Den CTR_DRBG df -genererende funktion kombinerer en CBC-MAC baseret funktion med evnen til at udtrække et næsten ensartet output fra tilstrækkeligt høje entropi input. Hvis genereringsfunktionen df ikke bruges, er de ekstra inputstrenge addin begrænset til ikke mere end (κ + l) — bit i længden. Initialiseringsprocessen forbinder hvert ekstra input til opdateringsfunktionen: hvis der bruges en genereringsfunktion, så er den ekstra inputstreng en streng af (κ + l) -bits med CTR_DRBG df , før denne proces startes. Hvis der ikke bruges yderligere input, forbliver tilstanden uændret, og addin har værdien 0 (κ+l) (for at danne input til opdateringsfunktionen under den endelige procedure, når opkaldet afsluttes). Udgangsblokkene rj oprettes derefter iterativt med blokchifferet i CTR-tilstand. Nøglen K forbliver den samme gennem alle disse iterationer. Når opkaldet er afsluttet, opdaterer den sidste proces både K og V via et opkald til opdatering [3] . opdateringsfunktion
Inputdata: leverede data, K, V Outputdata: K, V temp ← e m ← [(κ + l)/l] for j = 1, . . . , jeg gør V ← (V + 1) mod 2^l C(i) ← E(K, V) temp ← temp||Ci temp ← venstre(temp, (κ + l)) K||V ← temp ⊕ leverede data retur (K, V)generere funktion
Indgangsdata: S = (K, V, cnt), β, addin Output: S' = (K', V', cnt'), R hvis 0 ← check(S, β, addin) så returnere (fejl, ⊥) hvis addin ≠ ε så hvis der bruges afledningsfunktion da addin ← df(addin, (κ + l)) ellers hvis len(addin) < (κ + l) så addin ← addin||0^(κ+l−len(addin)) (K0, V0) ← opdatering(addin, K, V ) andet addin ← 0^κ+l; (K0, V(0)) ← (K, V) temp ← e ; m ← [β/l] for j = 1, . . . , jeg gør V(j) ← (V(j−1) + 1) mod 2^l r(j) ← E(K0, V(j)) temp ← temp||r(j) R ← venstre(temp, β) (K', V') ← opdatering(addin, K0, V(m)) cnt' ← cnt + 1 returnere (R, (K', V', cnt'))Dual_EC_DRBG blev trukket tilbage fra offentliggørelse med udgivelsen af den første revision af dokumentet. Årsagen til dette var den potentielle eksistens af en bagdør . En bagdør er en bevidst indbygget defekt i en algoritme, der tillader uautoriseret adgang til data eller fjernstyring af en computer [6] .
Som en del af Bullrun- programmet indsætter NSA bagdøre i kryptografiske systemer. Dual_EC_DRBG var angiveligt et af målene i 2013 [7] . I processen med standardiseringsarbejde opnåede NSA det, der til sidst blev den eneste redaktør af standarden [8] . Ved adgang til Dual_EC_DRBG, der blev vedtaget i NIST SP 800-90A, citerede NSA brugen af Dual_EC_DRBG af det anerkendte sikkerhedsfirma RSA Security i deres produkter. RSA Security blev dog betalt $10 millioner af NSA for at bruge Dual_EC_DRBG som standard i deres produkter. Reuters beskriver aftalen som "udformet af virksomhedsledere, ikke rene teknologer." Fordi kontrakten på $10 millioner til at tvinge RSA Security til at bruge Dual_EC_DRBG blev beskrevet som hemmelig af Reuters, var de involverede i NIST SP 800-90A adoptionsprocessen for Dual_EC_DRBG angiveligt uvidende om denne tilsyneladende interessekonflikt [9] . Dette kan hjælpe med at forklare, hvordan en tilfældig talgenerator, som senere viste sig at være ringere end alternativer (ud over en sandsynlig bagdør), blev vedtaget som en standard i NIST SP 800-90A.
Selvom potentialet for en bagdør i Dual_EC_DRBG allerede var dokumenteret af Dan Shumov og Nils Ferguson i 2007, [10] fortsatte den med at blive brugt i produkter af virksomheder som RSA Security indtil 2013 [1] . I betragtning af de kendte mangler i Dual_EC_DRBG dukkede der efterfølgende påstande op om, at RSA Security bevidst indsatte NSA-bagdøren i sine produkter. RSA afviser bevidst at indsætte en bagdør i sine produkter [11] .
Efter at bagdøren blev opdaget, genoptog NIST NIST SP 800-90A [7] [12] regeringsgennemgangsprocessen . En revideret version af NIST SP 800-90A, hvor Dual_EC_DRBG blev fjernet, blev offentliggjort i juni 2015 [13] .
Hash_DRBG og HMAC_DRBG har sikkerhedsbeviser til at generere pseudo-tilfældige sekvenser [14] . Sikkerhedsbevisdokumentet for Hash_DRBG og HMAC_DRBG citerer sikkerhedsbevisforsøg for Dual_EC_DRBG, der angiver, at CTR_DRBG ikke bør bruges, fordi det er den eneste generator i NIST SP 800-90A, som der ikke er sikkerhedsbevis for [14] .
HMAC_DRBG har også et maskinverificeret sikkerhedsbevis [15] . Afhandlingen, som indeholder et beregningsmæssigt verificeret sikkerhedsbevis, beviser også, at cracking af en korrekt implementeret instans af HMAC_DRBG ikke kompromitterer sikkerheden af numre, der er oprettet før cracket [15] .
CTR_DRBG har vist sig at have sikkerhedsproblemer, når det bruges med visse parametre, da kryptografer ikke tog størrelsen på chifferblokken i betragtning, da de designede denne pseudo-tilfældige talgenerator [16] . CTR_DRBG ser ud til at være sikker og umulig at skelne fra en ægte tilfældig kilde, når AES bruges som den underliggende blokchiffer, og 112 bit er taget fra denne pseudo-tilfældige talgenerator [16] . Når AES bruges som den underliggende blokchiffer, og der tages 128 bit fra hver instans, indstilles det nødvendige sikkerhedsniveau med det forbehold, at outputtet fra en 128-bit cipher i tællertilstand kan skelnes fra en ægte tilfældig talgenerator [16 ] . Når AES bruges som den underliggende blokchiffer, og der tages mere end 128 bit fra denne pseudo-tilfældige talgenerator, så er det resulterende sikkerhedsniveau begrænset af blokstørrelsen, ikke nøglestørrelsen, og så det faktiske sikkerhedsniveau er meget mindre end det sikkerhedsniveau, nøglestørrelsen antyder [16] . Det er også blevet vist, at CTR_DRBG ikke kan levere det forventede sikkerhedsniveau ved brug af Triple DES , fordi dens 64-bit blokstørrelse er meget mindre end den 112-bit nøglestørrelse, der bruges til Triple DES [16] .
Security Proof Attempt for Dual_EC_DRBG hævder, at Dual_EC_DRBG kræver tre problemer for at være NP for at være sikre : Diffie-Hellman- problemet , det diskrete logaritmeproblem og det trunkerede punktproblem [17] . Diffie-Hellman-beslutningsproblemet er almindeligt anerkendt som matematisk vanskeligt [17] . Det diskrete logaritmeproblem er ikke almindeligt accepteret i NP-klassen, nogle beviser viser, at dette problem er svært, men beviser det ikke [17] . Sikkerhedsbeviset er derfor åbent for spørgsmål og kan blive ugyldigt, hvis det diskrete logaritmeproblem viser sig at være løseligt snarere end matematisk vanskeligt. Problemet med trunkerede punkter kræver, at nok bits afkortes fra det punkt, der er valgt af Dual_EC_DRBG for at gøre det umuligt at skelne fra et virkelig tilfældigt tal [17] . det er imidlertid blevet vist, at 16-bit trunkeringen, der er standard af Dual_EC_DRBG standarden, er utilstrækkelig til at gøre outputtet umuligt at skelne fra en sand tilfældig talgenerator [18] og derfor ugyldiggør Dual_EC_DRBG sikkerhedsbeviset, når standardafkortningsværdien bruges.
Ovenstående algoritmer er standarder og bruges af store virksomheder til at skabe deres egne produkter baseret på dem. Så Microsoft , i færd med at oprette en opdatering til sit CryptoApi kaldet "Cryptography API: Next Generation (CNG)", indstillede standard pseudo-tilfældige talgenerator til CTR_DRBG [19] .
Intel bruger også CTR_DRBG [20] til at generere et tilfældigt tal ved hjælp af den indbyggede tilfældige talgenerator i RdRand- instruktionen .