Dual_EC_DRBG ( anglicky ; z Dual E lliptic Curve D eterministic R andom B it Generator ) je dříve považovaný za kryptograficky bezpečný generátor pseudonáhodných čísel vyvinutý americkou Národní bezpečnostní agenturou , jeden ze čtyř kryptograficky bezpečných generátorů standardizovaných NIST jako „Special Publication 800-90 " ( NIST SP 800-90A ) v roce 2006 [1] a stažena v roce 2014 [2] . Jednou z oblastí použití jsou kryptografické systémy pro generování klíčů. Algoritmus je založen na použití eliptických křivek .
Ve standardu NIST SP 800-90A jsou v popisu algoritmu použity 2 funkce: [3] [4]
Pokrok:
1) Nastaví se náhodná hodnota t = randomseed()
2) Operace se provádějí v cyklu
Zabezpečení Dual_EC_DRBG je založeno na obtížném problému teorie čísel , problému Diffie-Hellman . To byl uvedený důvod pro zařazení do NIST SP 800-90. [3] Výrobci generátorů však nezveřejnili matematický důkaz zabezpečení generátoru a po zveřejnění projektu NIST se ukázalo, že Dual_EC_DRBG není zabezpečený kvůli vysokému počtu bitů na výstup kola. [5] [6] Pokud použijete body eliptické křivky specifikované ve standardu, pak se kvůli příliš velkému počtu bitů na výstupu vytvoří zadní vrátka, která útočníkovi umožní prolomit generátor vyčerpávajícím hledáním . Tento problém nebyl opraven v konečném publikovaném standardu, takže Dual_EC_DRBG nebyl bezpečný. [7]
V mnoha jiných standardech jsou konstanty, které musí být libovolné, zvoleny na základě číselného principu Nic v rukávu . V Dual_EC_DRBG dodavatelé nespecifikovali, jak jsou specifikovány body eliptických křivek P a Q. Protože si normalizační komise byla vědoma možného zadního vrátka, byl do standardu zahrnut způsob, jak odvodit jejich konstanty P a Q. [8] [9 ] Přesná formulace ve standardu však byla napsána tak, že použití P a Q uvedených ve standardu je vyžadováno pro schválení FIPS 140-2 , takže tyto konstanty byly implementovány v OpenSSL navzdory povědomí o zadních vrátkách a přání používat robustnější parametry. [10] The New York Times později napsal, že NSA pracovala během procesu standardizace, aby se nakonec stala jediným editorem normy. [jedenáct]
O nějaký čas později Daniel Brown a Christian Gjostin publikovali bezpečnostní důkaz pro Dual_EC_DRBG, který ukázal, že generované body eliptické křivky by byly nerozeznatelné od náhodných, pokud [5] :
Dual_EC_DRBG je poměrně pomalý oscilátor ve srovnání s alternativními oscilátory zahrnutými ve stejném standardu, nicméně tyto alternativy nemají žádný důkaz o bezpečnosti. [12] Daniel Brown tvrdí, že z důvodu prokázání bezpečnosti lze generátor používat bez ohledu na jeho otáčky za předpokladu použití spolehlivých parametrů. [12]
Údajná zadní vrátka umožňují útočníkovi určit vnitřní stav generátoru náhodných čísel po zhlédnutí výstupu jednoho kola po 30 bajtech. Veškerý budoucí výstup generátoru náhodných čísel lze snadno vypočítat, dokud externí zdroj entropie znovu nenačte generátor novou hodnotou t 0 [4] . Například použití tohoto generátoru znejistí zabezpečení SSL / TLS , protože navázání připojení TLS zahrnuje odeslání náhodně vygenerovaného čísla. [7] Backdoor je v tom, že při použití konstant P a Q ze standardu NSA zná e takové, že e * Q = P. [4] [13] Tedy e je tajný klíč, pravděpodobně známý NSA, a předpokládá se, že zadní vrátka jsou kleptografická skrytá zadní vrátka. [čtrnáct]
První výstup je 30 bajtů r 0 je x-ová souřadnice bodu bez úvodních 16 bitů. Pro každou křivku uvedenou v normě jsou zapsány hodnoty X, nula a jeden nebo dva body na této křivce. K úplnému výčtu tedy není potřeba více než 17 bitů, aby se obnovil původní bod A. [4]
Za předpokladu, že:
3. Poté vynásobte každou stranu rovnice
e * A = s 0 * e * Q = s 0 * P [4]
Na základě toho je možné vypočítat s 1 = φ ( x ( e * A) ), a pak r 1 , pak následující s 2 ,...,s n a r 2 ,...,r n . K tomu stačí najít A vyčerpávajícím hledáním, výsledné A vynásobit e , poté výslednou hodnotu vynásobit Q a zobrazit hodnotu x-ové souřadnice získaného bodu bez prvních dvou bajtů. [čtyři]
NSA poprvé představila Dual_EC_DRBG v ANSI X9.82 DRBG na počátku 2000, včetně parametrů umožňujících zadní vrátka, a Dual_EC_DRBG byla publikována v ANSI Draft Standard. Byl také přidán do normy ISO 18031. [8]
Nejméně dva členové ANSI X9F1 Standards and Recommendations Committee, Daniel Brown a Scott Vanston z Certicom , [ 8] věděli o přesném mechanismu a okolnostech, za kterých je zadní vrátka možná, protože v lednu 2005 podali patent [15] , který popisoval, jak vložit nebo zabránit backdooru v Dual_EC_DRBG. Později bylo potvrzeno, že tato „past“ je totožná se zadními vrátky generátoru. V roce 2014 Matthew Green, kryptograf a profesor na Johns Hopkins University , [16] [17] kritizoval výbor za to, že neodstranil tato známá zadní vrátka. [18] Patent popsal 2 podmínky pro existenci tohoto zadního vrátka:
1) Je vybráno Q.
Generátor náhodných čísel eliptické křivky se vyhýbá klíčům u třetí osoby náhodným výběrem bodu Q. Záměrné použití klíčů u třetí osoby může poskytnout zálohu. Spojení mezi P a Q se používá jako klíč úschovy u třetí osoby a je uloženo v zabezpečené oblasti. Správce zaregistruje výstup generátoru a obnoví náhodné číslo pomocí klíče úschovy u třetí osoby.
2) Výkon generátoru není snížen
Zkrácení výstupu generátoru je alternativní způsob, jak zabránit útoku na klíč u třetí osoby. Zkrácení výstupu přibližně na polovinu zajistí, že výstup hodnot R spojených s jedním výstupem r nebude možné prohledávat. Například pro skupinu 160bitové eliptické křivky je počet potenciálních R bodů v seznamu asi 280 a hledání by bylo stejně obtížné jako problém s diskrétním logaritmem. Nevýhodou této metody je, že účinnost generátoru je poloviční, protože jeho výkon je poloviční.
Podle Johna Kelseyho, jednoho z autorů NIST SP 800-90A, byla do standardu přidána platná náhodná volba Q v reakci na zadní vrátka [9] , ale takovým způsobem, že generátor projde pouze FIPS 140-2 kontroluje pomocí Q od NSA . [19] Nebylo jasné, proč norma nespecifikuje princip výběru bodů jako číslo Nic v rukávu, nebo proč norma nezkrátila výkon generátoru, který by zabránil útoku na escrow klíč.
Ve srovnání s předchozím generátorem EC PRG bylo v Dual_EC_DRBG implementováno zkrácení výstupu, které poskytlo 1/2 až 2/3 výsledku kola EC PRG. [20] Toto snížení výkonu stále ponechalo výstup generátoru předvídatelný a nepoužitelný jako kryptograficky bezpečný generátor pseudonáhodných čísel. Standard říká, že implementace by měly používat malý max_outlen, ale umožňuje jeho použití pouze v násobcích 8 bitů. Dodatek C standardu říká, že výstup menšího počtu bitů způsobí, že výstup bude méně rovnoměrně rozložen, ale Brownův důkaz zabezpečení spoléhá na to, že max_outlen je mnohem menší.
Panel standardů a doporučení ANSI X9F1, který diskutoval o zadních vrátkách, zahrnoval také pracovníky z RSA Security . [21] V roce 2004 RSA Security zavedla backdoor implementaci Dual_EC_DRBG do RSA BSAFE jako výsledek tajné dohody s NSA. V roce 2013, poté, co New York Times uvedly, že Dual_EC_DRBG obsahuje zadní vrátka, RSA Security uvedla, že při uzavírání dohody s NSA o těchto zadních vrátkách nevěděla, a poté požádali uživatele, aby generátor přepnuli. Na konferenci RSA v roce 2014 výkonný předseda RSA Security Art Coviello vysvětlil, že společnost přichází o peníze ze šifrování, a rozhodl se s tím přestat a místo toho důvěřovat standardům a orgánům schvalujícím standardy, jako je NIST. [22]
Návrh NIST SP 800-90A, včetně Dual_EC_DRBG, byl zveřejněn v prosinci 2005. Konečná verze byla zveřejněna v červnu 2006. Dokumenty zobrazené Snowdenem byly interpretovány tak, že naznačují, že Dual_EC_DRBG implementuje zadní vrátka NSA, přičemž cituje přání NSA být jediným editorem standardu. [23] Dřívější použití Dual_EC_DRBG v RSA Security bylo předloženo NSA jako argument pro zahrnutí generátoru do NIST SP 800-90A. [24] RSA Security následně uvedla, že důvodem pro jeho použití bylo přijetí Dual_EC_DRBG společností NIST. [25]
Potenciální zadní vrátka nebyla zveřejněna mimo výbor pro standardy. Až po prezentaci Dana Shumova a Nilse Fergusona v roce 2007 se backdoor dostal do širokého povědomí. Měli za úkol implementovat Dual_EC_DRBG pro Microsoft . Kromě toho Ferguson diskutoval o možných zadních vrátkách v roce 2005 na setkání X9. [9] Bruce Schneier v článku Wired z roku 2007 napsal , že nevýhody Dual_EC_DRGB jsou tak zřejmé, že by ho nikdo nepoužil. [26]
OpenSSL implementuje všechny části NIST SP 800-90A, včetně Dual_EC_DRBG, navzdory jeho pochybné pověsti. Tvůrci OpenSSL zároveň poznamenali, že se snaží, aby OpenSSL bylo kompletní, a proto implementovali i nezabezpečené algoritmy. OpenSSL standardně nepoužívalo Dual_EC_DRBG a v roce 2013 bylo zjištěno, že implementace OpenSSL Dual_EC_DRBG byla rozbitá a nikdo ji nemohl používat. [19]
Bruce Schneier v prosinci 2007 oznámil, že Microsoft přidal podporu Dual_EC_DRBG do Windows Vista, i když nebyla ve výchozím nastavení povolena, a Schneier varoval před potenciálními zadními vrátky. [27] Windows 10 a novější nahradí volání Dual_EC_DRBG voláními generátoru založených na AES. [28]
9. září 2013 kvůli informacím od Snowdena a také zprávě New York Times o zadních vrátkách Dual_EC_DRBG NIST oznámil, že znovu vydává SP 800-90A a otevírá SP 800-90B/C k veřejnému komentáři. NIST nyní „důrazně doporučuje“ nepoužívat Dual_EC_DRBG. [29] [30] Zveřejnění zadních vrátek v přijatém standardu bylo pro NIST vážnou ostudou. [31]
RSA Security ponechala Dual_EC_DRBG jako výchozí generátor v BSAFE i poté, co se backdoor stal široce známým. V návaznosti na rozšířený zájem o zadní vrátka byl učiněn pokus najít software, který používal Dual_EC_DRBG, mezi nimiž BSAFE vyčníval. V roce 2013 poskytl bezpečnostní šéf RSA Sam Curry Ars Technica zdůvodnění pro výběr chybného výchozího standardu Dual_EC_DRBG před alternativními generátory. [32] Technická část prohlášení byla široce kritizována kryptografy. [33] Dne 20. prosince 2013 agentura Reuters uvedla, že RSA přijala tajnou platbu 10 milionů dolarů od NSA, aby nastavila Dual_EC_DRBG jako výchozí ve dvou šifrovacích produktech. [24] [34]