A Dual_EC_DRBG ( angolul a Dual E lliptic C urve D eterministic R andom B it Generator szóból ) egy korábban kriptográfiailag biztonságosnak tartott pszeudo-véletlenszám-generátor , amelyet az Egyesült Államok Nemzetbiztonsági Ügynöksége fejlesztett ki , egyike a négy titkosításilag biztonságos generátornak , amelyeket a NIST "Special Publication"-ként szabványosított. 800-90 " ( NIST SP 800-90A ) 2006-ban [1] és 2014-ben visszavonták [2] . Az egyik alkalmazási terület a kulcsok generálására szolgáló kriptográfiai rendszerek. Az algoritmus elliptikus görbék használatán alapul .
A NIST SP 800-90A szabványban 2 függvényt használnak az algoritmus leírásában: [3] [4]
Előrehalad:
1) Egy véletlenszerű értéket t = randomseed()
2) A műveleteket a ciklusban hajtják végre
A Dual_EC_DRBG biztonsága egy nehéz számelméleti problémán , a Diffie-Hellman problémán alapul . Ez volt az oka annak, hogy bekerült a NIST SP 800-90-be. [3] A generátorgyártók azonban nem publikáltak matematikai bizonyítékot a generátor biztonságáról, és a NIST projekt közzététele után bebizonyosodott, hogy a Dual_EC_DRBG nem biztonságos a körkimenetenkénti bitek magas száma miatt. [5] [6] Ha a szabványban meghatározott elliptikus görbe pontokat használja, akkor a túl sok bit miatt a kimenetben egy hátsó ajtó jön létre, amely lehetővé teszi, hogy a támadó kimerítő kereséssel feltörje a generátort . Ezt a problémát a végleges közzétett szabvány nem javította, így a Dual_EC_DRBG nem biztonságos. [7]
Sok más szabványban a tetszőleges konstansokat a Nothing up my sleeve number elv választja ki . A Dual_EC_DRBG-ben a gyártók nem határozták meg, hogyan kell megadni az elliptikus görbe P és Q pontjait. Mivel a szabványosítási bizottság tisztában volt egy lehetséges hátsó ajtóval, a szabvány tartalmazta a P és Q állandók származtatásának módját [8] [9 ] De a szabványban a pontos megfogalmazás úgy lett megírva, hogy a szabványban megadott P és Q használata szükséges a FIPS 140-2 érvényesítéshez , ezért ezeket a konstansokat az OpenSSL -ben implementálták annak ellenére, hogy a hátsó ajtó tudatos volt és a robusztusabb használat iránti vágy. paramétereket. [10] A New York Times később azt írta, hogy az NSA a szabványosítási folyamat során azon dolgozott, hogy végül a szabvány egyetlen szerkesztőjévé váljon. [tizenegy]
Nem sokkal később Daniel Brown és Christian Gjostin közzétett egy biztonsági bizonyítékot a Dual_EC_DRBG-hez, amely megmutatta, hogy egy elliptikus görbe generált pontjai megkülönböztethetetlenek lennének a véletlentől, ha [5] :
A Dual_EC_DRBG meglehetősen lassú oszcillátor az ugyanabban a szabványban szereplő alternatív oszcillátorokhoz képest, azonban ezeknek az alternatíváknak nincs bizonyítéka a biztonságra. [12] Daniel Brown azzal érvel, hogy a biztonság bizonyítása miatt a generátor a sebességétől függetlenül használható, feltéve, hogy megbízható paramétereket alkalmaznak. [12]
Az állítólagos hátsó ajtó lehetővé teszi a támadó számára, hogy meghatározza a véletlenszám-generátor belső állapotát egy kör 30 bájtos kimenetének megtekintése után. A véletlenszám-generátor minden jövőbeni kimenete könnyen kiszámítható mindaddig, amíg egy külső entrópiaforrás újra nem tölti a generátort egy új t 0 értékkel [4] . Ennek a generátornak a használata például az SSL / TLS -t nem biztonságossá teszi , mivel a TLS-kapcsolat létrehozása véletlenszerűen generált szám törlését jelenti. [7] A hátsó ajtó az, hogy az NSA szabványból származó P és Q konstansok használatakor úgy tudja az e-t, hogy e * Q = P. [4] [13] Így az e egy titkos kulcs, amelyet feltehetően az NSA ismer, és feltételezzük, hogy a hátsó ajtó egy kleptográfiai rejtett hátsó ajtó. [tizennégy]
Az első kimenet 30 bájt, r 0 a pont x-koordinátája a bevezető 16 bit nélkül. A szabványban megadott minden görbére felírják az X, a nulla és egy vagy két pont értékeit a görbén. Így az eredeti A pont visszaállításához legfeljebb 17 bit szükséges a teljes felsoroláshoz. [4]
Feltéve, hogy:
3. Ezután megszorozzuk az egyenlet mindkét oldalát
e * A = s 0 * e * Q = s 0 * P [4]
Ez alapján kiszámítható az s 1 = φ ( x ( e * A) ), majd az r 1 , majd az ezt követő s 2 ,...,s n és r 2 ,...,r n . Ehhez csak kimerítő kereséssel meg kell találni A-t, a kapott A -t meg kell szorozni e -vel, majd a kapott értéket megszorozni Q-val, és megjeleníteni a kapott pont x-koordináta értékét az első két bájt nélkül. [négy]
Az NSA először a 2000-es évek elején vezette be a Dual_EC_DRBG-t az ANSI X9.82 DRBG-ben, beleértve a hátsó ajtót engedélyező paramétereket, a Dual_EC_DRBG pedig az ANSI szabványtervezetben jelent meg. Az ISO 18031 szabványba is bekerült. [8]
Az ANSI X9F1 szabványok és ajánlások bizottságának legalább két tagja, Daniel Brown és Scott Vanston a Certicomtól [ 8 ] tisztában volt azzal a pontos mechanizmussal és körülményekkel, amelyek mellett lehetséges a hátsó ajtó, mivel 2005 januárjában szabadalmat nyújtottak be [15] , amely leírta, hogyan kell beszúrni vagy megakadályozni egy hátsó ajtót a Dual_EC_DRBG-ben. Később bebizonyosodott, hogy ez a „csapda” azonos a generátor hátsó ajtajával. 2014-ben Matthew Green, a kriptográfus és a Johns Hopkins Egyetem professzora [16] [17] bírálta a bizottságot, amiért nem távolította el ezt a jól ismert hátsó ajtót. [18] A szabadalom két feltételt írt le ennek a hátsó ajtónak a létezéséhez:
1) Q van kiválasztva.
Az elliptikus görbe véletlenszám-generátora a Q pont véletlenszerű kiválasztásával elkerüli a letéti kulcsokat. A letéti kulcsok szándékos használata tartalékot jelenthet. A P és Q közötti kapcsolatot letéti kulcsként használják, és biztonságos területen tárolják. Az adminisztrátor regisztrálja a generátor kimenetét, és a letéti kulcs segítségével visszaállítja a véletlen számot.
2) A generátor teljesítménye nem csökken
A generátor kimenetének csonkolása egy alternatív módja a letéti kulcs elleni támadások megelőzésének. A kimenet körülbelül felére csökkentése biztosítja, hogy az egyetlen r kimenethez társított R értékek kimenete ne legyen kereshető. Például egy 160 bites elliptikus görbecsoport esetén a potenciális R pontok száma a listában körülbelül 280 , és a keresés olyan nehéz lenne, mint egy diszkrét logaritmus probléma. Ennek a módszernek az a hátránya, hogy a generátor hatásfoka felére csökken, mivel a teljesítménye felére csökken.
John Kelsey , a NIST SP 800-90A egyik szerzője szerint egy érvényes véletlenszerű Q opciót adtak a szabványhoz válaszul egy hátsó ajtóra [9] , de úgy, hogy a generátor csak a FIPS 140-2 -t engedje át. az NSA Q segítségével ellenőrzi. [19] Nem volt világos, hogy a szabvány miért nem a Nothing up my sleeve number-ként határozza meg a pontkiválasztás elvét, vagy hogy a szabvány miért nem rövidítette le a generátor kimenetét, ami megakadályozza a letéti kulcsok támadását.
Az előző EC PRG generátorhoz képest a Dual_EC_DRBG-ben a kimenet csonkolása valósult meg, ami az EC PRG kör eredményének 1/2-2/3-át adta ki. [20] A kibocsátás csökkenése továbbra is kiszámíthatóvá tette a generátor kimenetét, és kriptográfiailag biztonságos pszeudo-véletlenszám-generátorként használhatatlanná tette. A szabvány szerint az implementációknak kis max_outlen értéket kell használniuk, de csak 8 bit többszörösében engedélyezi a használatát. A szabvány C függeléke azt mondja, hogy a kevesebb bit kimenete kevésbé egyenletesen elosztja a kimenetet, de Brown biztonsági bizonyítéka a max_outlen jóval kisebb méretén alapul.
Az ANSI X9F1 szabványok és ajánlások panelje, amely a hátsó ajtót tárgyalta, az RSA Security munkatársait is magában foglalta . [21] 2004-ben az RSA Security bevezette a Dual_EC_DRBG backdoor implementációját az RSA BSAFE -ba az NSA-val kötött titkos megállapodás eredményeként. 2013-ban, miután a New York Times arról számolt be, hogy a Dual_EC_DRBG tartalmaz egy hátsó ajtót, az RSA Security azt mondta, hogy nem voltak tudatában a hátsó ajtónak, amikor alkut kötöttek az NSA-val, ami után arra kérték a felhasználókat, hogy váltsanak generátort. A 2014-es RSA konferencián az RSA Security Art ügyvezető elnöke, Coviello kifejtette, hogy a vállalat pénzt veszít a titkosítás miatt, és úgy döntött, hogy abbahagyja a tevékenységet, és ehelyett olyan szabványokban és szabványjóváhagyó testületekben bízik meg, mint például a NIST. [22]
A NIST SP 800-90A tervezetét, beleértve a Dual_EC_DRBG-t, 2005 decemberében tették közzé. A végleges változat 2006 júniusában jelent meg. A Snowden által bemutatott dokumentumokat úgy értelmezték, mint amelyek azt sugallják, hogy a Dual_EC_DRBG egy NSA hátsó ajtót valósít meg, arra hivatkozva, hogy az NSA a szabvány egyetlen szerkesztője akar lenni. [23] A Dual_EC_DRBG korai használatát az RSA Security-ben az NSA felhozta érvként a generátor NIST SP 800-90A-ba való beépítése mellett. [24] Az RSA Security ezt követően azt mondta, hogy a Dual_EC_DRBG NIST általi elfogadása volt az oka annak használatának. [25]
A lehetséges hátsó ajtót nem tették közzé a szabványügyi bizottságon kívül. Csak Dan Shumov és Nils Ferguson 2007-es bemutatója után vált széles körben ismertté a hátsó ajtó. Azt a feladatot kapták, hogy implementálják a Dual_EC_DRBG-t a Microsoft számára . Ezenkívül Ferguson egy lehetséges hátsó ajtót tárgyalt 2005-ben egy X9 találkozón. [9] Bruce Schneier egy 2007-es Wired cikkében azt írta, hogy a Dual_EC_DRGB hátrányai annyira nyilvánvalóak, hogy senki sem használná. [26]
Az OpenSSL a NIST SP 800-90A minden részét megvalósítja, beleértve a Dual_EC_DRBG-t is, annak kétes hírneve ellenére. Az OpenSSL készítői ugyanakkor megjegyezték, hogy arra törekszenek, hogy az OpenSSL teljes legyen, és ezért még nem biztonságos algoritmusokat is megvalósítsanak. Az OpenSSL alapértelmezés szerint nem használta a Dual_EC_DRBG-t, és 2013-ban kiderült, hogy a Dual_EC_DRBG OpenSSL-megvalósítása megszakadt, és senki sem tudta használni. [19]
Bruce Schneier 2007 decemberében arról számolt be, hogy a Microsoft Dual_EC_DRBG támogatást adott a Windows Vista rendszerhez, bár ez alapértelmezés szerint nem volt engedélyezve, és Schneier figyelmeztetett egy lehetséges hátsó ajtóra. [27] A Windows 10 és újabb verziók a Dual_EC_DRBG hívásokat AES-alapú generátorhívásokra cserélik. [28]
2013. szeptember 9-én Snowden információi, valamint a New York Times Dual_EC_DRBG backdoor-ról szóló jelentése miatt a NIST bejelentette, hogy újra kiadja az SP 800-90A és megnyitja az SP 800-90B/C nyilvános megjegyzéseket. A NIST most „erősen ajánlja”, hogy ne használja a Dual_EC_DRBG-t. [29] [30] A hátsó ajtó közzététele az elfogadott szabványban komoly kínos volt a NIST számára. [31]
Az RSA Security megtartotta a Dual_EC_DRBG-t alapértelmezett generátorként a BSAFE-ban még azután is, hogy a hátsó ajtó széles körben ismertté vált. A széles körben elterjedt backdoor aggodalmakra kísérletet tettek Dual_EC_DRBG-t használó szoftverek felkutatására, amelyek közül kiemelkedett a BSAFE. 2013-ban az RSA biztonsági vezetője, Sam Curry indoklást adott az Ars Technicának, hogy miért válassza a hibás alapértelmezett Dual_EC_DRBG szabványt az alternatív generátorokkal szemben. [32] A nyilatkozat technikai részét széles körben kritizálták a kriptográfusok. [33] 2013. december 20-án a Reuters arról számolt be, hogy az RSA 10 millió dolláros titkos kifizetést fogadott el az NSA-tól, hogy a Dual_EC_DRBG-t állítsa be alapértelmezettként két titkosítási termékben. [24] [34]