NIST SP 800-90A - („SP“ je zkratka pro Special Publication “ , „speciální publikace“) je publikace Národního institutu pro standardy a technologie ( NIST ) s názvem „Doporučení pro generování náhodných čísel pomocí deterministických generátorů náhodné bity "( eng. "Doporučení pro generování náhodných čísel pomocí deterministických generátorů náhodných bitů" ). Publikace obsahuje popisy tří údajně kryptograficky bezpečných generátorů pseudonáhodných čísel pro použití v kryptografii : Hash_DRBG (založený na hashovacích funkcích ), HMAC_DRBG (založený na hash ověřování zpráv ) a CTR_DRBG (založený na blokových šifrách v režimu čítače ).
K 24. červnu 2015 je aktuální verze publikace Revize 1 ( " Revize 1" ). Dřívější verze obsahovaly čtvrtý generátor, Dual_EC_DRBG (založený na eliptické kryptografii ). Později bylo oznámeno, že Dual_EC_DRBG pravděpodobně obsahuje kleptografická zadní vrátka implementovaná Národní bezpečnostní agenturou , zatímco ostatní tři generátory náhodných čísel jsou přijímány jako konzistentní a bezpečné několika kryptografy [1] [2] .
NIST SP 800-90A je ve veřejné doméně a je ve veřejné doméně, protože se jedná o studii federální vlády USA .
HASH-DRBG je založeno na hašovací funkci SH : {0, 1} ∗ → {0, 1} l z rodiny kryptografických hašovacích funkcí SHA [3] . Stav má tvar S = (V, C, cnt) , kde V ∈ {0, 1} len je čítač, který je hašován za účelem vytvoření listových bloků, jejichž hodnota se aktualizuje při každém volání generátoru; С je konstanta v závislosti na mateřském prvku ( angl. seed ) a cnt je počítadlo náplně. cnt udává počet požadavků na pseudonáhodné bity od obdržení nové hodnoty od skutečného generátoru náhodných dat během vytváření instance nebo opětovného naplnění.
Generační algoritmus pro HASH-DRBG. Pokud je ve volání ke generování použit další vstup, je hashován a přidán do čítače V modulo 2 len během procesu inicializace. Výstupní bloky rj jsou pak tvořeny hašováním čítače V. Na konci volání je počítadlo hašováno se samostatnou předponou a výsledný řetězec je spolu s konstantou C a cnt přidán k V , výsledek takové operace je uveden jako aktualizované počítadlo.
Konstanta C se aktualizuje pouze při repopulaci (kdy je opět derivací nové proměnné V ) a při každé aktualizaci stavu se přidává ke stavové proměnné V. Konstanta C zajišťuje, že i když je předchozí čítač V duplikován v určitém okamžiku v různých periodách doplňování (téměř jistě různých), čítač zabrání opakování předchozí sekvence stavů při příští aktualizaci hodnoty. Norma definuje V a C jako proměnné kritického bezpečnostního stavu [3] .
Vstupní data: S = (V, C, cnt), β, addin Výstup: S' = (V', C, cnt'), R if 0 ← check(S, β, addin) then Návrat (chyba, ⊥) jestliže addin ≠ ε pak w ← SH(0x02||V||addin) V0 = (V + w) mod 2^len jinak V(0) ← V teplota ← e m ← [β/l] pro j = 1,. . . , dělám r(j) ← SH(V(j−1)) V(j) ← (V(j−1) + 1) mod 2^len teplota ← teplota||r(j) R ← vlevo (teplota, β) H ← SH(0x03||V(0)) V'← (V(0) + H + C + cnt) mod 2^len cnt' ← cnt + 1 návrat (V', C, cnt')HMAC je autentizační kód zprávy založený na hash, který byl představen Mihirem Bellare a kolegy [ 4] a následně standardizován [5] . HMAC-DRBG používá HMAC: {0, 1} l ×{0, 1} * → {0, 1} l ke generování pseudonáhodných výstupních bloků. Stav má tvar S = (K, V, cnt) , kde standard definuje K a V jako kriticky důležité tajné stavové proměnné. Předpokládá se, že po inicializaci je počáteční stav S 0 = (K 0 , V 0 , cnt 0 ) , kde cnt 0 = 1 a K 0 , V 0 ← {0, 1} len . Zde se jako klíč HMAC používá K ∈ {0, 1} l , V ∈ {0, 1} l je počítadlo a cnt označuje počítadlo doplňování [3] .
Algoritmus generování využívá funkci aktualizace, která se používá k přidání jakéhokoli dalšího vstupu do stavových proměnných K a V a aktualizuje obě jednosměrně. Pokud je ve volání zahrnut další vstup, provede se další pár aktualizací. Samotný generovací algoritmus pro HMAC-DRBG funguje následovně: inicializační proces přidává další vstup do stavových proměnných pomocí funkce aktualizace; pokud nejsou do hovoru zahrnuty další vstupy, stav zůstává nezměněn. Pro K 0 , V 0 označíme stavové proměnné odpovídající tomuto procesu, načež jsou výsledné bloky automaticky generovány iterativní aplikací algoritmu HMAC(K 0 ,·) pro aktuální čítač V j-1 , výstupní blok r j a další hodnota čítače V j je rovna výslednému řetězci. Klíč K 0 zůstává během každé iterace nezměněn. Po dokončení volání poslední proces aktualizuje K a V pomocí funkce aktualizace [3] . funkce aktualizace
Vstupní data: addin, K, V Výstupní údaje: K, V K ← HMAC(K, V||0x00||addin) V ← HMAC(K; V) jestliže addin ≠ ε pak K ← HMAC(K, V||0x01||addin) V ← HMAC(K; V) návrat (K, V)generovat funkci
Vstupní data: S = (K, V, cnt), β, addin Výstup: S' = (K', V', cnt'), R if 0 ← check(S, β, addin) then vrátit (chyba, ⊥) jestliže addin ≠ ε pak (K0, V0) ← aktualizace(addin, K, V) else (K0, V(0)) ← (K, V) teplota ← e ; m ← [β/l] pro j = 1,. . . , dělám V(j) ← HMAC(K0, V(j−1)) r(j) ← V(j) teplota ← teplota||r(j) R ← vlevo (teplota, β) (K', V') ← update(addin, K0, V(m)) cnt' ← cnt + 1 návrat (R, (K', V', cnt'))CTR_DRBG je založeno na algoritmu blokové šifry, jehož šifrovací funkce E : {0, 1} k × {0, 1} l → {0, 1} l se používá v režimu CTR (režim čítače). Stav má tvar S = (K, V, cnt) , kde K ∈ {0, 1} k je použito jako klíč pro blokovou šifru, V ∈ {0, 1} l je čítač a cnt označuje počítadlo doplňování. Norma uvádí, že K a V jsou kritické proměnné bezpečnostního stavu. Inicializace vrátí počáteční stav S 0 = (К 0 , V 0 , cnt 0 ) , kde cnt 0 = 1 a K 0 ← {0, 1} k , V 0 ← {0, 1} l [3] .
Stejně jako v HMAC_DRBG používá algoritmus funkci update k jednosměrné aktualizaci stavových proměnných K a V a také k zahrnutí jakýchkoliv dalších datových vstupů (které jsou předány aktualizační funkci prostřednictvím parametru provide_data). Funkce spustí blokovou šifru v režimu CTR pomocí aktuálního klíče a čítače a zřetězí výsledné výstupní bloky r j . Poté se zkrátí bity κ+l nejvíce vlevo a hodnoty poskytnutých_dat se vloží pomocí operace XOR. Funkce aktualizace je volána každým z ostatních procesů tak, aby zajistila, že poskytovaná_data jsou dlouhá přesně κ+l bitů [3] .
Existují dvě možnosti pro CTR_DRBG v závislosti na tom, zda se používá funkce generování. Funkce generování CTR_DRBG df kombinuje funkci založenou na CBC-MAC se schopností extrahovat téměř rovnoměrný výstup ze vstupů s dostatečně vysokou entropií. Pokud není použita generovací funkce df , jsou dodatečné vstupní řetězce omezeny na maximálně (κ + l) — bitů na délku. Inicializační proces připojí každý další vstup k aktualizační funkci: pokud je použita generovací funkce, je dalším vstupním řetězcem řetězec (κ + l) -bitů s CTR_DRBG df před zahájením tohoto procesu. Pokud není použit žádný další vstup, stav zůstane nezměněn a addin má hodnotu 0 (κ+l) (pro vytvoření vstupu do funkce aktualizace během závěrečné procedury po dokončení volání). Výstupní bloky r j jsou pak vytvářeny iterativně blokovou šifrou v režimu CTR. Klíč K zůstává ve všech těchto iteracích stejný. Po dokončení volání poslední proces aktualizuje K i V prostřednictvím volání aktualizace [3] . funkce aktualizace
Vstupní data: poskytnutá data, K, V Výstupní údaje: K, V teplota ← e m ← [(κ + l)/l] pro j = 1,. . . , dělám V ← (V + 1) mod 2^l C(i) ← E(K, V) teplota ← teplota||Ci teplota ← vlevo(teplota, (κ + l)) K||V ← teplota ⊕ poskytnutá data návrat (K, V)generovat funkci
Vstupní data: S = (K, V, cnt), β, addin Výstup: S' = (K', V', cnt'), R if 0 ← check(S, β, addin) then vrátit (chyba, ⊥) jestliže addin ≠ ε pak pokud se pak použije derivační funkce addin ← df(addin, (κ + l)) else if len(addin) < (κ + l) then addin ← addin||0^(κ+l−len(addin)) (K0, V0) ← update(addin, K, V ) jiný addin ← 0^κ+l; (K0, V(0)) ← (K, V) teplota ← e ; m ← [β/l] pro j = 1,. . . , dělám V(j) ← (V(j−1) + 1) mod 2^l r(j) ← E(K0, V(j)) teplota ← teplota||r(j) R ← vlevo (teplota, β) (K', V') ← update(addin, K0, V(m)) cnt' ← cnt + 1 návrat (R, (K', V', cnt'))Dual_EC_DRBG byl stažen z publikace s vydáním první revize dokumentu. Důvodem byla potenciální existence zadních vrátek . Backdoor je záměrně zabudovaná vada v algoritmu, která umožňuje neoprávněný přístup k datům nebo vzdálené ovládání počítače [6] .
V rámci programu Bullrun vkládá NSA do kryptografických systémů zadní vrátka. Dual_EC_DRBG byl údajně jedním z cílů v roce 2013 [7] . V procesu normalizační práce dosáhl NSA toho, co se nakonec stalo jediným editorem normy [8] . Při přístupu k Dual_EC_DRBG přijatému v NIST SP 800-90A NSA citovala použití Dual_EC_DRBG renomovanou bezpečnostní firmou RSA Security ve svých produktech. Společnosti RSA Security však NSA zaplatila 10 milionů dolarů za to, aby ve svých produktech standardně používala Dual_EC_DRBG. Reuters popisuje dohodu jako „vytvořenou obchodními lídry, nikoli čistými technology“. Protože kontrakt ve výši 10 milionů dolarů, který měl přinutit RSA Security používat Dual_EC_DRBG, byl agenturou Reuters popsán jako tajný, lidé zapojení do procesu přijetí NIST SP 800-90A pro Dual_EC_DRBG si údajně nebyli vědomi tohoto zjevného střetu zájmů [9] . To může pomoci vysvětlit, jak byl v NIST SP 800-90A přijat jako standard generátor náhodných čísel, o kterém se později ukázalo, že je horší než alternativy (kromě pravděpodobného zadního vrátka).
Přestože potenciál pro zadní vrátka v Dual_EC_DRBG zdokumentovali již Dan Shumov a Nils Ferguson v roce 2007 [10] , až do roku 2013 byl nadále používán v produktech společností jako RSA Security [1] . Vzhledem ke známým nedostatkům v Dual_EC_DRBG se následně objevila obvinění, že RSA Security záměrně vložila zadní vrátka NSA do svých produktů. RSA popírá, že by do svých produktů vědomě vkládala zadní vrátka [11] .
Poté, co byla objevena zadní vrátka, NIST obnovil vládní proces přezkoumání NIST SP 800-90A [7] [12] . Revidovaná verze NIST SP 800-90A, ve které byl Dual_EC_DRBG odstraněn, byla zveřejněna v červnu 2015 [13] .
Hash_DRBG a HMAC_DRBG mají bezpečnostní důkazy pro generování pseudonáhodných sekvencí [14] . Dokument bezpečnostního důkazu pro Hash_DRBG a HMAC_DRBG cituje pokusy o bezpečnostní důkaz pro Dual_EC_DRBG s tím, že CTR_DRBG by neměl být používán, protože je to jediný generátor v NIST SP 800-90A, pro který neexistuje žádný bezpečnostní důkaz [14] .
HMAC_DRBG má také strojově ověřený doklad o zabezpečení [15] . Práce, která obsahuje výpočetně ověřený bezpečnostní důkaz, také dokazuje, že cracknutí správně implementované instance HMAC_DRBG neohrozí bezpečnost čísel vytvořených před crackem [15] .
Ukázalo se, že CTR_DRBG má bezpečnostní problémy při použití s určitými parametry, protože kryptografové při navrhování tohoto generátoru pseudonáhodných čísel nebrali v úvahu velikost bloku šifry [16] . CTR_DRBG se zdá být bezpečný a nerozeznatelný od skutečného náhodného zdroje, když je jako základní bloková šifra použita AES a 112 bitů je převzato z tohoto generátoru pseudonáhodných čísel [16] . Když se jako základní bloková šifra použije AES a z každé instance se vezme 128 bitů, nastaví se nezbytná úroveň zabezpečení s podmínkou, že výstup 128bitové šifry v režimu čítače lze odlišit od skutečného generátoru náhodných čísel [16 ] . Když se jako základní bloková šifra použije AES a z tohoto generátoru pseudonáhodných čísel je odebráno více než 128 bitů, pak je výsledná úroveň zabezpečení omezena velikostí bloku, nikoli velikostí klíče, takže skutečná úroveň zabezpečení je mnohem nižší. než je úroveň zabezpečení implikovaná velikostí klíče [16] . Také se ukázalo, že CTR_DRBG nemůže poskytnout očekávanou úroveň zabezpečení při použití Triple DES , protože jeho 64bitová velikost bloku je mnohem menší než 112bitová velikost klíče používaná pro Triple DES [16] .
Security Proof Attempt for Dual_EC_DRBG tvrdí, že Dual_EC_DRBG vyžaduje tři problémy, aby byl NP , aby byl bezpečný : problém Diffie-Hellman , problém diskrétního logaritmu a problém zkráceného bodu [17] . Diffie-Hellmanův rozhodovací problém je široce uznáván jako matematicky obtížný [17] . Problém diskrétního logaritmu není široce přijímán do třídy NP, některé důkazy ukazují, že tento problém je obtížný, ale nedokazují to [17] . Důkaz zabezpečení je proto otevřená otázka a může být zneplatněn, pokud se ukáže, že problém diskrétního logaritmu je spíše řešitelný než matematicky obtížný. Problém zkráceného bodu vyžaduje, aby bylo z bodu zvoleného Dual_EC_DRBG oříznuto dostatečné množství bitů, aby bylo nerozeznatelné od skutečně náhodného čísla [17] . ukázalo se však, že 16bitové zkrácení předvolené standardem Dual_EC_DRBG je nedostatečné k tomu, aby byl výstup nerozeznatelný od skutečného generátoru náhodných čísel [18] , a proto při použití výchozí hodnoty zkrácení znehodnocuje bezpečnostní důkaz Dual_EC_DRBG.
Výše uvedené algoritmy jsou standardy a používají je velké společnosti k vytváření vlastních produktů na jejich základě. Microsoft tedy v procesu vytváření aktualizace pro své CryptoApi s názvem „Cryptography API: Next Generation (CNG)“ nastavil výchozí generátor pseudonáhodných čísel na CTR_DRBG [19] .
Intel také používá CTR_DRBG [20] ke generování náhodného čísla pomocí vestavěného generátoru náhodných čísel v instrukci RdRand .