Dual EC DRBG

Dual_EC_DRBG (Dual Elliptic Curve Deterministic Random Bit Generator) és un algorisme que es va presentar com un generador de números pseudoaleatoris criptogràficament segur (CSPRNG) utilitzant mètodes en criptografia de corba el·líptica. Malgrat les àmplies crítiques públiques, inclosa la identificació pública de la possibilitat que l'Agència de Seguretat Nacional posés una porta del darrere en una implementació recomanada, va ser, durant set anys, un dels quatre CSPRNG estandarditzats al NIST SP 800-90A tal com es va publicar originalment cap al juny de 2006. fins que es va retirar el 2014.

Debilitat: una possible porta del darrere

Les debilitats en la seguretat criptogràfica de l'algoritme eren conegudes i criticades públicament molt abans que l'algoritme es convertís en part d'un estàndard formal aprovat per ANSI, ISO i anteriorment pel National Institute of Standards and Technology (NIST). Una de les debilitats identificades públicament va ser el potencial de l'algorisme per albergar una porta del darrere criptogràfica avantatjosa per a aquells que la coneixen —l'Agència de Seguretat Nacional (NSA) del govern dels Estats Units— i per a ningú més. El 2013, The New York Times va informar que els documents en el seu poder però que mai no s'havien donat a conèixer al públic "semblan confirmar" que la porta del darrere era real i que l'NSA havia inserit deliberadament com a part del seu programa de desxifrat Bullrun. El desembre de 2013, un article de notícies de Reuters va al·legar que el 2004, abans que el NIST estandarditzés Dual_EC_DRBG, la NSA va pagar a RSA Security 10 milions de dòlars en un acord secret per utilitzar Dual_EC_DRBG com a predeterminat a la biblioteca de criptografia RSA BSAFE, la qual cosa va fer que RSA Security es convertís en la més important. distribuïdor de l'algorisme insegur. RSA va respondre que "neguen categòricament" que alguna vegada s'haguessin connivet amb la NSA per adoptar un algorisme que se sabia que era defectuós, però també va afirmar que "mai hem mantingut [la nostra] relació [amb la NSA] en secret".

Un temps abans de la seva primera publicació coneguda el 2004, es va descobrir una possible porta del darrere cleptogràfica amb el disseny de Dual_EC_DRBG, amb el disseny de Dual_EC_DRBG que tenia la propietat inusual que era teòricament impossible per a ningú més que els dissenyadors de Dual_EC_DRBG (NSA) per confirmar l'existència de la porta del darrere. Bruce Schneier va concloure poc després de l'estandardització que la porta del darrere "més aviat òbvia" (juntament amb altres deficiències) significaria que ningú utilitzaria Dual_EC_DRBG. La porta del darrere permetria a NSA desxifrar, per exemple, el xifratge SSL/TLS que utilitzava Dual_EC_DRBG com a CSPRNG.

Els membres del grup estàndard ANSI al qual es va enviar Dual_EC_DRBG per primera vegada eren conscients del mecanisme exacte de la porta del darrere potencial i de com desactivar-la, però no van optar per desactivar o donar a conèixer la porta del darrere. La comunitat criptogràfica general inicialment no era conscient de la possible porta del darrere, fins a la publicació de Dan Shumow i Niels Ferguson, o de la sol·licitud de patent del 2005 de Daniel RL Brown de Certicom i Scott Vanstone que descrivia el mecanisme de la porta del darrere.

El setembre de 2013, The New York Times va informar que les notes internes de la NSA filtrades per Edward Snowden van indicar que la NSA havia treballat durant el procés d'estandardització per convertir-se finalment en l'únic editor de l'estàndard Dual_EC_DRBG, i va concloure que l'estàndard Dual_EC_DRBG sí que contenia una porta del darrere per a la NSA. En resposta, el NIST va declarar que "el NIST no debilitaria deliberadament un estàndard criptogràfic", però segons la història del New York Times, la NSA havia estat gastant 250 milions de dòlars anuals per inserir portes del darrere en programari i maquinari com a part del Bullrun. programa. Un comitè assessor presidencial es va crear posteriorment per examinar la conducta de la NSA va recomanar, entre altres coses, que el govern dels Estats Units "donés plenament suport i no soscavi els esforços per crear estàndards de xifratge".

El 21 d'abril de 2014, el NIST va retirar Dual_EC_DRBG del seu esborrany d'orientació sobre generadors de nombres aleatoris recomanant "els usuaris actuals de Dual_EC_DRBG transiten a un dels tres algorismes aprovats restants tan aviat com sigui possible".

Descripció

Visió general

L'algorisme utilitza un sol enter s s a estat. Sempre que es demana un nou nombre aleatori, aquest nombre sencer s'actualitza. El k -è estat està donat per

$s_{k}=g_{P}(s_{k-1})$ L'enter aleatori retornat r és una funció de l'estat. El k -è nombre aleatori és

$r_{k}=g_{Q}(s_{k})$

La funció $g_{P}(x)$ depèn del punt fix de la corba el·líptica P. $g_{Q}(x)$ és similar excepte que utilitza el punt Q. Els punts P i Q es mantenen constants per a una implementació particular de l'algorisme.

Seguretat

El propòsit declarat d'incloure el Dual_EC_DRBG al NIST SP 800-90A és que la seva seguretat es basi en supòsits de duresa computacional de la teoria dels nombres. Aleshores, una prova de reducció de la seguretat matemàtica pot demostrar que, mentre els problemes teòrics dels nombres siguin difícils, el propi generador de nombres aleatoris és segur. No obstant això, els creadors de Dual_EC_DRBG no van publicar una reducció de seguretat per a Dual_EC_DRBG, i poc després de la publicació de l'esborrany del NIST es va demostrar que Dual_EC_DRBG no era segur, perquè donava massa bits per ronda. La sortida de massa bits (juntament amb els punts de corba el·líptics P i Q escollits amb cura) és el que fa possible la porta del darrere de la NSA, perquè permet a l'atacant revertir el truncament per endevinació de força bruta. La sortida de massa bits no es va corregir a l'estàndard publicat final, deixant Dual_EC_DRBG tant insegur com amb porta posterior.