NIST SP 800-90A - ("SP" är en förkortning för Special Publication " , "special publication") är en publikation från National Institute of Standards and Technology ( NIST ) med titeln "Rekommendation för generering av slumptal med deterministiska generatorer slumpmässiga bitar "( sv. "Rekommendation för generering av slumptal med hjälp av deterministiska slumpmässiga bitgeneratorer" ). Publikationen innehåller beskrivningar av tre förment kryptografiskt säkra pseudoslumptalsgeneratorer för användning i kryptografi : Hash_DRBG (baserat på hashfunktioner ), HMAC_DRBG (baserat på meddelandeautentiseringshash ) och CTR_DRBG (baserat på blockchiffer i räknarläge ).
Från och med den 24 juni 2015 är den aktuella versionen av publikationen Revision 1 ( " Revision 1" ). Tidigare versioner inkluderade en fjärde generator, Dual_EC_DRBG (baserad på elliptisk kryptografi ). Det rapporterades senare att Dual_EC_DRBG sannolikt innehåller en kleptografisk bakdörr , implementerad av National Security Agency , medan de andra tre slumptalsgeneratorerna accepteras som konsekventa och säkra av flera kryptografer [1] [2] .
NIST SP 800-90A är allmän egendom och är allmän egendom, eftersom det är en studie av den amerikanska federala regeringen .
HASH-DRBG är baserad på hashfunktionen SH : {0, 1} ∗ → {0, 1} l från SHA-familjen av kryptografiska hashfunktioner [3] . Tillståndet har formen S = (V, C, cnt) , där V ∈ {0, 1} len är en räknare som hashas för att skapa lövblock, vars värde uppdateras under varje generatoranrop; С är en konstant beroende på föräldraelementet ( eng. seed ), och cnt är påfyllningsräknaren. cnt indikerar antalet förfrågningar om pseudoslumpmässiga bitar sedan det nya värdet mottagits från den sanna slumpgeneratorn under instansiering eller ompopulation.
Generationsalgoritm för HASH-DRBG. Om en ytterligare ingång används i anropet för att generera, hashas den och läggs till räknaren V modulo 2 len under initieringsprocessen. Utgångsblocken rj bildas sedan genom att hasha räknaren V . I slutet av samtalet hashas räknaren med ett separat prefix, och den resulterande strängen, tillsammans med konstanten C och cnt , läggs till V , resultatet av en sådan operation ges som den uppdaterade räknaren.
Konstanten C uppdateras endast under återpopulation (när den återigen är en derivata av den nya variabeln V ) och läggs till tillståndsvariabeln V under varje tillståndsuppdatering. Konstanten C ser till att även om den föregående räknaren V dupliceras någon gång under olika påfyllningsperioder (nästan säkert olika), kommer räknaren att förhindra att den föregående sekvensen av tillstånd upprepas nästa gång värdet uppdateras. Standarden definierar V och C som kritiska säkerhetstillståndsvariabler [3] .
Indata: S = (V, C, cnt), β, addin Utgång: S' = (V', C, cnt'), R om 0 ← check(S, β, addin) då Returnera (fel, ⊥) om addin ≠ ε då w ← SH(0x02||V||tillägg) V0 = (V + w) mod 2^len annat V(0) ← V temp ← e m ← [β/l] för j = 1, . . . , jag gör r(j) ← SH(V(j−1)) V(j) ← (V(j−1) + 1) mod 2^len temp ← temp||r(j) R ← vänster(temp, β) H ← SH(0x03||V(0)) V' ← (V(0) + H + C + cnt) mod 2^len cnt' ← cnt + 1 returnera (V', C, cnt')HMAC är en hash-baserad meddelandeautentiseringskod som introducerades av Mihir Bellare och kollegor [ 4] och sedan standardiserades [5] . HMAC-DRBG använder HMAC: {0, 1} l ×{0, 1} * → {0, 1} l för att generera pseudoslumpmässiga utdatablock. Tillståndet har formen S = (K, V, cnt) , där standarden definierar K och V som säkerhetskritiska hemliga tillståndsvariabler. Det antas att efter initiering är initialtillståndet S 0 = (K 0 , V 0 , cnt 0 ) , där cnt 0 = 1 och K 0 , V 0 ← {0, 1} len . Här används K ∈ {0, 1} l som HMAC-nyckel, V ∈ {0, 1} l är räknaren och cnt betecknar påfyllningsräknaren [3] .
Genereringsalgoritmen använder uppdateringsfunktionen, som används för att lägga till eventuell ytterligare indata till tillståndsvariablerna K och V , och uppdaterar båda envägs. Om ytterligare input ingår i samtalet, utförs ytterligare ett par uppdateringar. Själva genereringsalgoritmen för HMAC-DRBG fungerar enligt följande: initieringsprocessen lägger till ytterligare indata till tillståndsvariablerna via uppdateringsfunktionen; om ytterligare ingångar inte ingår i samtalet förblir tillståndet oförändrat. För K 0 , V 0 betecknar vi tillståndsvariablerna som motsvarar denna process, varefter de resulterande blocken genereras automatiskt genom att iterativt tillämpa HMAC(K 0 ,·) -algoritmen för strömräknaren Vj -1 , utgångsblocket rj och nästa värde på räknaren Vj är lika med den resulterande strängen. Nyckeln Ko förblir oförändrad under varje iteration. När samtalet är klart uppdaterar den slutliga processen K och V med uppdateringsfunktionen [3] . uppdateringsfunktion
Indata: addin, K, V Utdata: K, V K ← HMAC(K, V||0x00||tillägg) V ← HMAC(K, V) om addin ≠ ε då K ← HMAC(K, V||0x01||tillägg) V ← HMAC(K, V) retur (K, V)generera funktion
Indata: S = (K, V, cnt), β, addin Utgång: S' = (K', V', cnt'), R om 0 ← check(S, β, addin) då returnera (fel, ⊥) om addin ≠ ε då (K0, V0) ← uppdatering(add, K, V) annat (K0, V(0)) ← (K, V) temp ← e ; m ← [β/l] för j = 1, . . . , jag gör V(j) ← HMAC(K0, V(j−1)) r(j) ← V(j) temp ← temp||r(j) R ← vänster(temp, β) (K', V') ← update(addin, K0, V(m)) cnt' ← cnt + 1 returnera (R, (K', V', cnt'))CTR_DRBG är baserad på en blockchifferalgoritm vars chifferfunktion E: {0, 1} k × {0, 1} l → {0, 1} l används i CTR-läge (räknarläge). Tillståndet har formen S = (K, V, cnt) , där K ∈ {0, 1} k används som nyckel för blockchifferet, V ∈ {0, 1} l är räknaren och cnt anger påfyllningsdisk. Standarden anger att K och V är kritiska säkerhetstillståndsvariabler. Initiering returnerar initialtillståndet S 0 = (К 0 , V 0 , cnt 0 ) , där cnt 0 = 1 och K 0 ← {0, 1} k , V 0 ← {0, 1} l [3] .
Liksom i HMAC_DRBG använder algoritmen uppdateringsfunktionen för att uppdatera tillståndsvariablerna K och V enväg , såväl som för att inkludera eventuella ytterligare dataingångar (som skickas till uppdateringsfunktionen via parametern provided_data). Funktionen kör blockchifferet i CTR-läge med hjälp av den aktuella nyckeln och räknaren, sammanlänkar de resulterande utgångsblocken r j . Sedan trunkeras de κ+l bitarna längst till vänster och de tillhandahållna_datavärdena infogas med hjälp av XOR-operationen. Uppdateringsfunktionen anropas av var och en av de andra processerna på ett sådant sätt att den säkerställer att tillhandahållen_data är exakt κ+l bitar långa [3] .
Det finns två alternativ för CTR_DRBG beroende på om genereringsfunktionen används. Den CTR_DRBG df- genererande funktionen kombinerar en CBC-MAC-baserad funktion med förmågan att extrahera en nästan enhetlig utsignal från tillräckligt höga entropiingångar. Om genereringsfunktionen df inte används begränsas de ytterligare inmatningssträngarna addin till högst (κ + l) — bitar i längd. Initieringsprocessen kopplar varje ytterligare ingång till uppdateringsfunktionen: om en genererande funktion används, är den extra ingångssträngen en sträng av (K + l) -bitar med CTR_DRBG df innan denna process påbörjas. Om ingen ytterligare ingång används förblir tillståndet oförändrat och addin har värdet 0 (κ+l) (för att bilda ingången till uppdateringsfunktionen under den slutliga proceduren när anropet slutförs). Utmatningsblocken rj skapas sedan iterativt med blockchifferet i CTR-mod. Nyckeln K förblir densamma under alla dessa iterationer. När samtalet är klart uppdaterar den slutliga processen både K och V via ett anrop till uppdatering [3] . uppdateringsfunktion
Indata: tillhandahållna data, K, V Utdata: K, V temp ← e m ← [(κ + l)/l] för j = 1, . . . , jag gör V ← (V + 1) mod 2^l C(i) ← E(K, V) temp ← temp||Ci temp ← vänster(temp, (κ + l)) K||V ← temp ⊕ tillhandahållna data retur (K, V)generera funktion
Indata: S = (K, V, cnt), β, addin Utgång: S' = (K', V', cnt'), R om 0 ← check(S, β, addin) då returnera (fel, ⊥) om addin ≠ ε då om härledningsfunktion används då addin ← df(addin, (κ + l)) annars om len(addin) < (κ + l) då addin ← addin||0^(κ+l−len(addin)) (K0, V0) ← uppdatering(add, K, V ) annan addin ← 0^κ+l; (K0, V(0)) ← (K, V) temp ← e ; m ← [β/l] för j = 1, . . . , jag gör V(j) ← (V(j−1) + 1) mod 2^l r(j) ← E(K0, V(j)) temp ← temp||r(j) R ← vänster(temp, β) (K', V') ← update(addin, K0, V(m)) cnt' ← cnt + 1 returnera (R, (K', V', cnt'))Dual_EC_DRBG drogs tillbaka från publicering när den första revideringen av dokumentet släpptes. Anledningen till detta var den potentiella existensen av en bakdörr . En bakdörr är en medvetet inbyggd defekt i en algoritm som tillåter obehörig åtkomst till data eller fjärrkontroll av en dator [6] .
Som en del av Bullrun- programmet sätter NSA in bakdörrar i kryptografiska system. Dual_EC_DRBG var förmodligen ett av målen 2013 [7] . I processen med standardiseringsarbete uppnådde NSA vad som så småningom blev den enda redaktören för standarden [8] . Vid åtkomst till Dual_EC_DRBG antagen i NIST SP 800-90A hänvisade NSA till användningen av Dual_EC_DRBG av det kända säkerhetsföretaget RSA Security i sina produkter. RSA Security betalades dock 10 miljoner USD av NSA för att använda Dual_EC_DRBG som standard i sina produkter. Reuters beskriver affären som "gjord av företagsledare, inte rena teknologer." Eftersom kontraktet på 10 miljoner dollar för att tvinga RSA Security att använda Dual_EC_DRBG beskrevs som hemligt av Reuters, påstods personerna som var inblandade i NIST SP 800-90A adoptionsprocessen för Dual_EC_DRBG vara omedvetna om denna uppenbara intressekonflikt [9] . Detta kan hjälpa till att förklara hur en slumptalsgenerator, som senare visade sig vara sämre än alternativ (utöver en trolig bakdörr), antogs som en standard i NIST SP 800-90A.
Även om potentialen för en bakdörr i Dual_EC_DRBG redan dokumenterades av Dan Shumov och Nils Ferguson 2007, [10] fortsatte den att användas i produkter av företag som RSA Security fram till 2013 [1] . Med tanke på de kända bristerna i Dual_EC_DRBG dök det senare upp anklagelser om att RSA Security medvetet satte in NSA-bakdörren i sina produkter. RSA förnekar att medvetet infoga en bakdörr i sina produkter [11] .
Efter att bakdörren upptäcktes, återupptog NIST regeringens granskning av NIST SP 800-90A [7] [12] . En reviderad version av NIST SP 800-90A, där Dual_EC_DRBG togs bort, publicerades i juni 2015 [13] .
Hash_DRBG och HMAC_DRBG har säkerhetsbevis för att generera pseudo-slumpmässiga sekvenser [14] . Säkerhetsbeviset för Hash_DRBG och HMAC_DRBG citerar säkerhetsbevisförsök för Dual_EC_DRBG som säger att CTR_DRBG inte ska användas eftersom det är den enda generatorn i NIST SP 800-90A som det inte finns något säkerhetsbevis för [14] .
HMAC_DRBG har också ett maskinverifierat säkerhetsbevis [15] . Avhandlingen, som innehåller ett beräkningsverifierat säkerhetsbevis, bevisar också att knäckning av en korrekt implementerad instans av HMAC_DRBG inte äventyrar säkerheten för siffror som skapats före sprickan [15] .
CTR_DRBG har visat sig ha säkerhetsproblem när den används med vissa parametrar, eftersom kryptografer inte tog hänsyn till chifferblockstorleken när de designade denna pseudoslumptalsgenerator [16] . CTR_DRBG verkar vara säker och omöjlig att skilja från en sann slumpmässig källa när AES används som det underliggande blockchifferet och 112 bitar tas från denna pseudoslumptalsgenerator [16] . När AES används som det underliggande blockchifferet och 128 bitar tas från varje instans, ställs den nödvändiga säkerhetsnivån in med förbehållet att utsignalen från ett 128-bitars chiffer i räknarläge kan särskiljas från en sann slumptalsgenerator [16 ] . När AES används som det underliggande blockchifferet och mer än 128 bitar tas från denna pseudo-slumptalsgenerator, så begränsas den resulterande säkerhetsnivån av blockstorleken, inte nyckelstorleken, och så den faktiska säkerhetsnivån är mycket lägre än säkerhetsnivån som antyds av nyckelstorleken [16] . Det har också visat sig att CTR_DRBG inte kan tillhandahålla den förväntade säkerhetsnivån vid användning av Triple DES eftersom dess 64-bitars blockstorlek är mycket mindre än 112-bitars nyckelstorleken som används för Triple DES [16] .
Säkerhetsbevisförsöket för Dual_EC_DRBG hävdar att Dual_EC_DRBG kräver tre problem för att vara NP för att vara säkra : Diffie-Hellman- problemet , det diskreta logaritmproblemet och problemet med trunkerad punkt [17] . Diffie-Hellmans beslutsproblem är allmänt erkänt som matematiskt svårt [17] . Det diskreta logaritmproblemet är inte allmänt accepterat för NP-klassen, vissa bevis visar att detta problem är svårt, men bevisar det inte [17] . Säkerhetsbeviset kan därför ifrågasättas och kan ogiltigförklaras om det diskreta logaritmproblemet visar sig vara lösbart snarare än matematiskt svårt. Problemet med trunkerad punkt kräver att tillräckligt många bitar trunkeras från punkten som valts av Dual_EC_DRBG för att göra den omöjlig att skilja från ett verkligt slumpmässigt tal [17] . emellertid har det visat sig att 16-bitars trunkeringen som är standard av Dual_EC_DRBG-standarden är otillräcklig för att göra utgången omöjlig att skilja från en sann slumptalsgenerator [18] och ogiltigförklarar därför Dual_EC_DRBG-säkerhetsbeviset när det förinställda trunkeringsvärdet används.
Ovanstående algoritmer är standarder och används av stora företag för att skapa sina egna produkter utifrån dem. Så Microsoft , i färd med att skapa en uppdatering för sitt CryptoApi som heter "Cryptography API: Next Generation (CNG)", ställer in standardgeneratorn för pseudoslumptal till CTR_DRBG [19] .
Intel använder också CTR_DRBG [20] för att generera ett slumptal med den inbyggda slumptalsgeneratorn i RdRand- instruktionen .