A NIST SP 800-90A - (az „SP” a „ Special P ublication ” rövidítése , „speciális kiadvány”) a National Institute of Standards and Technology ( NIST ) kiadványa „Ajánlás véletlen számok determinisztikus generátorokkal történő előállításához” címmel . random bits "( eng. "Recommendation for Random Number Generation using Deterministic Random Bit Generators" ). A kiadvány három kriptográfiailag erős pszeudo-véletlenszám- generátor leírását tartalmazza, amelyeket a titkosításban használnak : Hash_DRBG ( hash függvények alapján ), HMAC_DRBG ( az üzenet-hitelesítési hash alapján ) és CTR_DRBG ( számláló módban lévő blokkrejtjelek alapján ).
2015. június 24-én a kiadvány aktuális verziója az 1. változat ( " Revision 1" ). A korábbi verziók tartalmaztak egy negyedik generátort, a Dual_EC_DRBG -t ( elliptikus kriptográfia alapján ). Később jelentették, hogy a Dual_EC_DRBG valószínűleg tartalmaz egy kleptográfiai hátsó ajtót , amelyet a Nemzetbiztonsági Ügynökség valósított meg , míg a másik három véletlenszám-generátort számos kriptográfus konzisztensnek és biztonságosnak fogadta el [1] [2] .
A NIST SP 800-90A közkincs és közkincs, mivel az Egyesült Államok szövetségi kormányának tanulmánya .
A HASH-DRBG az SH hash függvényen alapul: {0, 1} ∗ → {0, 1} l a kriptográfiai hash függvények SHA családjából [3] . Az állapot alakja S = (V, C, cnt) , ahol V ∈ {0, 1} len egy számláló, amely kivonatolva levélblokkokat hoz létre, amelyek értéke minden generátorhívás során frissül; A С a szülőelemtől függő konstans ( eng. seed ), a cnt pedig az utántöltési számláló. A cnt a pszeudo-véletlen bitekre vonatkozó kérések számát jelzi, mióta a valódi véletlenszerű generátortól kapott új érték a példányosítás vagy újratelepítés során.
A HASH-DRBG generálási algoritmusa. Ha a hívásban további bemenetet használnak a generáláshoz, akkor azt kivonatolja, és hozzáadja a V modulo 2 len számlálóhoz az inicializálási folyamat során. Az r j kimeneti blokkokat ezután a V számláló kivonatolásával alakítjuk ki . A hívás végén a számlálót egy külön előtaggal kivonatolja, és a kapott karakterláncot a C és cnt konstanssal együtt hozzáadjuk V -hez, egy ilyen művelet eredménye a frissített számláló.
A C konstans csak az újratelepítés során frissül (amikor ismét az új V változó deriváltja), és minden állapotfrissítés során hozzáadódik a V állapotváltozóhoz. A C konstans gondoskodik arról, hogy még ha az előző V számláló egy bizonyos ponton megduplázódik is különböző újratöltési periódusokban (majdnem biztosan eltérő), a számláló megakadályozza, hogy az előző állapotsor megismétlődjön az érték következő frissítésekor. A szabvány V és C kritikus biztonsági állapotváltozóként határozza meg [3] .
Bemenő adatok: S = (V, C, cnt), β, addin Kimenet: S' = (V', C, cnt'), R ha 0 ← check(S, β, addin) akkor Visszaküldés (hiba, ⊥) ha addin ≠ ε akkor w ← SH(0x02||V||addin) V0 = (V + w) mod 2^len különben V(0) ← V hőmérséklet ← e m ← [β/l] ha j = 1, . . . , m do r(j) ← SH(V(j-1)) V(j) ← (V(j−1) + 1) mod 2^len hőmérséklet ← temp||r(j) R ← bal (hőmérséklet, β) H ← SH(0x03||V(0)) V' ← (V(0) + H + C + cnt) mod 2^len cnt' ← cnt + 1 vissza (V', C, cnt')A HMAC egy hash-alapú üzenet-hitelesítési kód, amelyet Mihir Bellare és munkatársai vezettek be [ 4] , majd ezt követően szabványosították [5] . A HMAC-DRBG a HMAC-t használja: {0, 1} l ×{0, 1} * → {0, 1} l pszeudo-véletlen kimeneti blokkok generálásához. Az állapot alakja S = (K, V, cnt) , ahol a szabvány K -t és V -t biztonságkritikus titkos állapotváltozóként határozza meg. Feltételezzük, hogy inicializálás után a kezdeti állapot S 0 = (K 0 , V 0 , cnt 0 ) , ahol cnt 0 = 1 és K 0 , V 0 ← {0, 1} len . Itt K ∈ {0, 1} l a HMAC kulcs, V ∈ {0, 1} l a számláló, cnt pedig az utántöltési számláló [3] .
A generálási algoritmus a frissítési függvényt használja, amely bármilyen további bemenet hozzáadására szolgál a K és V állapotváltozókhoz , és mindkettőt egyirányú frissíti. Ha a hívás további bemenetet tartalmaz, a rendszer további pár frissítést hajt végre. Maga a HMAC-DRBG generálási algoritmus a következőképpen működik: az inicializálási folyamat minden további bemenetet hozzáad az állapotváltozókhoz a frissítési függvényen keresztül; ha további bemenetek nem szerepelnek a hívásban, az állapot változatlan marad. K 0 , V 0 esetén az ennek a folyamatnak megfelelő állapotváltozókat jelöljük, majd a kapott blokkokat automatikusan generáljuk a HMAC(K 0 ,·) algoritmus iteratív alkalmazásával a V j-1 áramszámlálóra , az r j kimeneti blokkra . és a V j számláló következő értéke egyenlő a kapott karakterlánccal. A K 0 kulcs minden iteráció során változatlan marad. Amikor a hívás befejeződik, a végső folyamat frissíti a K és V -t a [3] frissítési funkcióval . frissítési funkció
Bemeneti adatok: addin, K, V Kimeneti adatok: K, V K ← HMAC(K, V||0x00||addin) V ← HMAC(K, V) ha addin ≠ ε akkor K ← HMAC(K, V||0x01||addin) V ← HMAC(K, V) vissza (K, V)függvényt generál
Bemenő adatok: S = (K, V, cnt), β, addin Kimenet: S' = (K', V', cnt'), R ha 0 ← check(S, β, addin) akkor visszaküldés (hiba, ⊥) ha addin ≠ ε akkor (K0, V0) ← frissítés (addin, K, V) más (K0, V(0)) ← (K, V) temp ← e ; m ← [β/l] ha j = 1, . . . , m do V(j) ← HMAC(K0, V(j-1)) r(j) ← V(j) hőmérséklet ← temp||r(j) R ← bal (hőmérséklet, β) (K', V') ← frissítés(addin, K0, V(m)) cnt' ← cnt + 1 vissza (R, (K', V', cnt'))A CTR_DRBG egy blokk rejtjelező algoritmuson alapul, amelynek E : {0, 1} k × {0, 1} l → {0, 1} l titkosítási függvénye CTR módban (számláló módban) használatos. Az állapot alakja S = (K, V, cnt) , ahol K ∈ {0, 1} k a blokk titkosítás kulcsa, V ∈ {0, 1} l a számláló, cnt pedig a utántöltő számláló. A szabvány kimondja, hogy K és V kritikus biztonsági állapotváltozók. Az inicializálás az S 0 = (К 0 , V 0 , cnt 0 ) kezdeti állapotot adja vissza , ahol cnt 0 = 1 és K 0 ← {0, 1} k , V 0 ← {0, 1} l [3] .
A HMAC_DRBG-hez hasonlóan az algoritmus a frissítési függvényt használja a K és V állapotváltozók egyirányú frissítésére , valamint bármilyen további adatbevitelre (amelyek a megadott_data paraméteren keresztül kerülnek átadásra a frissítési függvénynek). A függvény a blokk titkosítást CTR módban futtatja az aktuális kulcs és számláló segítségével, összefűzve az eredményül kapott r j kimeneti blokkokat . Ezután a bal szélső κ+l biteket levágjuk, és a megadott_adat értékeket az XOR művelettel besoroljuk. A frissítési függvényt a többi folyamat úgy hívja meg, hogy az biztosítja, hogy a biztosított_adatok pontosan κ+l bit hosszúak legyenek [3] .
Két lehetőség van a CTR_DRBG-hez attól függően, hogy a generáló funkció használatban van-e. A CTR_DRBG df generáló függvény kombinálja a CBC-MAC alapú függvényt azzal a képességgel, hogy a kellően nagy entrópiájú bemenetekből közel egyenletes kimenetet nyerjen ki. Ha a df generáló függvényt nem használjuk, az addin további bemeneti karakterláncok hossza legfeljebb (κ + l) — bit lehet. Az inicializálási folyamat minden további bemenetet összekapcsol a frissítési funkcióval: ha generáló függvényt használunk, akkor a további bemeneti karakterlánc egy (κ + l) -bitekből álló karakterlánc CTR_DRBG df -vel, mielőtt elindítaná ezt a folyamatot. Ha nem használunk további bemenetet, az állapot változatlan marad, és az addin értéke 0 (κ+l) (a frissítési függvény bemenetét képezi az utolsó eljárás során, amikor a hívás befejeződik). Az r j kimeneti blokkok ezután iteratív módon jönnek létre a blokkrejtjellel CTR módban. A K kulcs ugyanaz marad az összes iteráció során. Amikor a hívás befejeződik, a végső folyamat frissíti a K-t és a V-t is egy frissítési híváson keresztül [3] . frissítési funkció
Bemeneti adatok: megadott adatok, K, V Kimeneti adatok: K, V hőmérséklet ← e m ← [(κ + l)/l] ha j = 1, . . . , m do V ← (V + 1) mod 2^l C(i) ← E(K, V) hőmérséklet ← temp||Ci hőmérséklet ← bal (hőmérséklet, (κ + l)) K||V ← temp ⊕ megadott adatokat vissza (K, V)függvényt generál
Bemenő adatok: S = (K, V, cnt), β, addin Kimenet: S' = (K', V', cnt'), R ha 0 ← check(S, β, addin) akkor visszaküldés (hiba, ⊥) ha addin ≠ ε akkor ha derivációs függvényt használunk akkor addin ← df(addin, (κ + l)) else if len(addin) < (κ + l) akkor addin ← addin||0^(κ+l−len(addin)) (K0, V0) ← frissítés (addin, K, V ) más addin ← 0^κ+l; (K0, V(0)) ← (K, V) temp ← e ; m ← [β/l] ha j = 1, . . . , m do V(j) ← (V(j−1) + 1) mod 2^l r(j) ← E(K0, V(j)) hőmérséklet ← temp||r(j) R ← bal (hőmérséklet, β) (K', V') ← frissítés(addin, K0, V(m)) cnt' ← cnt + 1 vissza (R, (K', V', cnt'))A Dual_EC_DRBG a dokumentum első változatának kiadásával visszavonásra került a közzétételből. Ennek oka egy hátsó ajtó lehetséges létezése volt . A hátsó ajtó egy olyan algoritmus szándékosan beépített hibája, amely lehetővé teszi az adatokhoz való jogosulatlan hozzáférést vagy a számítógép távvezérlését [6] .
A Bullrun program részeként az NSA hátsó ajtókat helyez be a kriptográfiai rendszerekbe. A Dual_EC_DRBG állítólag az egyik cél volt 2013-ban [7] . A szabványosítási munka során az NSA elérte azt, ami végül a szabvány egyetlen szerkesztője lett [8] . A NIST SP 800-90A szabványban elfogadott Dual_EC_DRBG elérésekor az NSA arra hivatkozott, hogy a neves biztonsági cég, az RSA Security a Dual_EC_DRBG-t használja termékeiben. Az RSA Security-nek azonban 10 millió dollárt fizetett az NSA azért, hogy alapértelmezés szerint a Dual_EC_DRBG-t használják termékeikben. A Reuters úgy írja le az ügyletet, mint "az üzletvezetők, nem pedig a technológusok alkották meg". Mivel az RSA Security Dual_EC_DRBG használatára kényszerítéséről szóló 10 millió dolláros szerződést a Reuters titkosnak minősítette, a Dual_EC_DRBG NIST SP 800-90A elfogadási folyamatában részt vevő személyek állítólag nem tudtak erről a látszólagos összeférhetetlenségről [9] . Ez segíthet megmagyarázni, hogy a véletlenszám-generátort, amelyről később kiderült, hogy rosszabb, mint az alternatívák (a valószínű hátsó ajtón kívül), hogyan fogadták el szabványként a NIST SP 800-90A-ban.
Bár Dan Shumov és Nils Ferguson már 2007-ben dokumentálta a Dual_EC_DRBG háttérajtó lehetőségét [10] , 2013-ig továbbra is használták olyan cégek termékeiben, mint például az RSA Security [1] . Tekintettel a Dual_EC_DRBG ismert hiányosságaira, később felmerültek olyan állítások, amelyek szerint az RSA Security szándékosan illesztette be az NSA hátsó ajtót termékeibe. Az RSA tagadja, hogy tudatosan beépített volna hátsó ajtót a termékeibe [11] .
A hátsó ajtó felfedezése után a NIST újraindította a NIST SP 800-90A [7] [12] kormányzati felülvizsgálati folyamatát . A NIST SP 800-90A felülvizsgált változata, amelyből a Dual_EC_DRBG eltávolítva, 2015 júniusában jelent meg [13] .
A Hash_DRBG és a HMAC_DRBG biztonsági bizonyítékokkal rendelkezik pszeudo-véletlen sorozatok generálásához [14] . A Hash_DRBG és HMAC_DRBG biztonsági igazolási dokumentuma idézi a Dual_EC_DRBG biztonsági igazolási kísérleteit, kijelentve, hogy a CTR_DRBG-t nem szabad használni, mert ez az egyetlen generátor a NIST SP 800-90A-ban, amelyre nincs biztonsági bizonyíték [14] .
A HMAC_DRBG géppel ellenőrzött biztonsági igazolással is rendelkezik [15] . A számításilag ellenőrzött biztonsági bizonyítékot tartalmazó tézis azt is bizonyítja, hogy a HMAC_DRBG megfelelően implementált példányának feltörése nem veszélyezteti a feltörés előtt létrehozott számok biztonságát [15] .
Kimutatták, hogy a CTR_DRBG bizonyos paraméterekkel használva biztonsági problémákkal küzd, mivel a kriptográfusok nem vették figyelembe a rejtjelblokk méretét ennek az álvéletlenszám-generátornak a tervezésekor [16] . A CTR_DRBG biztonságosnak tűnik, és nem különböztethető meg a valódi véletlenszerű forrástól, ha az AES -t használják a mögöttes blokk-rejtjelként, és 112 bitet vesznek ebből a pszeudo-véletlenszám-generátorból [16] . Ha AES-t használunk mögöttes blokkrejtjelként, és minden példányból 128 bitet veszünk, a szükséges biztonsági szintet azzal a feltétellel állítjuk be, hogy a 128 bites titkosítás kimenete számláló módban megkülönböztethető a valódi véletlenszám-generátortól [16 ] . Ha az AES-t használják mögöttes blokkrejtjelként, és több mint 128 bitet vesznek ki ebből a pszeudo-véletlenszám-generátorból, akkor az eredményül kapott biztonsági szintet a blokk mérete korlátozza, nem a kulcsméret, így a tényleges biztonsági szint sokkal kisebb. mint a kulcsméret által feltételezett biztonsági szint [16] . Azt is kimutatták, hogy a CTR_DRBG nem tudja biztosítani az elvárt biztonsági szintet Triple DES használatakor, mert 64 bites blokkmérete sokkal kisebb, mint a Triple DES-hez használt 112 bites kulcsméret [16] .
A Security Proof Attempt for Dual_EC_DRBG azzal érvel, hogy a Dual_EC_DRBG három probléma NP -hez kell, hogy biztonságos legyen : a Diffie-Hellman probléma , a diszkrét logaritmus probléma és a csonkapont probléma [17] . A Diffie-Hellman-döntési probléma széles körben elismert matematikailag nehéz [17] . A diszkrét logaritmus probléma nem elfogadott az NP osztályban, néhány bizonyíték azt mutatja, hogy ez a probléma nehéz, de nem bizonyítja [17] . A biztonsági igazolás ezért megkérdőjelezhető, és érvényteleníthető, ha a diszkrét logaritmus-probléma megoldhatónak bizonyul, nem pedig matematikailag nehéz. A csonkapont-probléma megköveteli, hogy a Dual_EC_DRBG által választott pontból elegendő bit legyen csonkolva ahhoz, hogy az ne legyen megkülönböztethető egy valóban véletlen számtól [17] . azonban kimutatták, hogy a Dual_EC_DRBG szabvány által alapértelmezetten beállított 16 bites csonkítás nem elegendő ahhoz, hogy a kimenet ne legyen megkülönböztethető a valódi véletlenszám-generátortól [18] , és ezért érvényteleníti a Dual_EC_DRBG biztonsági igazolást az alapértelmezett csonkítási érték használatakor.
A fenti algoritmusok szabványok, és a nagyvállalatok saját termékeik létrehozásához használják őket ezek alapján. Ezért a Microsoft a CryptoApi -jához „Cryptography API: Next Generation (CNG)” nevű frissítés létrehozása közben az alapértelmezett pszeudo-véletlenszám-generátort CTR_DRBG-re állította [19] .
Az Intel a CTR_DRBG [20] segítségével véletlenszámot generál az RdRand utasítás beépített véletlenszám-generátorával .