Dual_EC_DRBG

Dual_EC_DRBG (Dual Elliptic Curve Deterministic Random Bit Generator) ist ein von der National Security Agency entwickelter und veröffentlichter kryptographisch sicherer Zufallszahlengenerator (PRNG). Das Verfahren ist eines von vier in der NIST Special Publication 800-90 standardisierten PRNGs.^[1] Kurz nach der Publikation durch das NIST wurden Vermutungen laut, der Algorithmus enthalte eine kleptographische Backdoor.^[2]

Sicherheit

Der Grund für die Aufnahme von Dual_EC_DBRG in den Standard war, dass sich seine Sicherheit auf ein schwieriges zahlentheoretisches Problem, das Decisional-Diffie-Hellman-Problem (DDH) in der verwendeten elliptischen Kurve, reduzieren lässt. Das dadurch gewonnene zusätzliche Vertrauen in die Sicherheit des Verfahrens kann in manchen Fällen den Geschwindigkeitsverlust von drei Grössenordnungen gegenüber den anderen drei standardisierten Verfahren^[2] rechtfertigen. Unter der Annahme, dass DDH ein schwieriges Problem ist, sind die vom Verfahren erzeugten Zwischenwerte, eine Folge von Punkten auf der elliptischen Kurve, ununterscheidbar von einer Folge zufälliger Punkte.^[3][4][5]

Nach der Publikation des Standards fanden Forscher zwei Sicherheitsprobleme:

• Die Bitfolge, die aus der Punktfolge erzeugt wird, kann für manche Parameter von einer gleichverteilt zufälligen Bitfolge unterschieden werden. Damit ist der PRNG für eine Anwendung als Stromchiffre und für weitere Anwendungen ungeeignet.^[3][5][6]

• Die Sicherheit des PRNG basiert auf der Annahme, dass das DDH-Problem schwierig ist. Für die von NIST empfohlene Kurve besteht aber die Möglichkeit, dass die Parameter der Kurve ausgehend von weiteren Werten gewählt wurden, die das Lösen dieses Problems wesentlich erleichtern (siehe den nächsten Abschnitt).

Kontroverse

Im August 2007 entdeckten Dan Shumow und Niels Ferguson, dass der Algorithmus eine Schwäche aufweist, die als Backdoor ausgenutzt werden könnte.^[7] Da PRNGs ein vielfach genutztes kryptographisches Primitiv sind, könnte diese Schwäche ausgenutzt werden um jedes kryptographische Verfahren, das darauf beruht, zu brechen.

Die im Standard definierte Kurve ist durch eine mathematische Gleichung definiert, in der Konstanten vorkommen. Shumow und Ferguson konnten zeigen, dass diese Konstanten in einer Beziehung zu weiteren, geheimen Zahlen stehen. Kenntnis dieser geheimen Zahlen würde es jedem Angreifer erlauben, das Verfahren zu brechen. Es ist nicht klar, wie diese Konstanten gewählt wurden, es besteht aber die Möglichkeit, dass derjenige, der sie wählte, dies auf der Basis dieser geheimen Schlüsselwerte tat. Damit besteht die Möglichkeit, dass diese Person jede Instanz des PRNG auf dieser Kurve brechen kann. Im Anhang A des Standards ist allerdings eine Methode definiert, wie eine eigene Kurve mit selbstgewählten Konstanten erzeugt werden kann.

Einzelnachweise

1. ↑ National Institute of Standards and Technology (Hrsg.): NIST SP 800-90: Recommendations for Random Number Generation Using Deterministic Random Bit Generators (Revised). 2007 (http://csrc.nist.gov/publications/nistpubs/800-90/SP800-90revised_March2007.pdf).
2. ↑ ^{a b} Bruce Schneier: Did NSA Put a Secret Backdoor in New Encryption Standard? Wired News, 15. November 2007, abgerufen am 9. Oktober 2011 (englisch). 
3. ↑ ^{a b} Kristian Gjøsteen: Comments on Dual-EC-DRBG/NIST SP 800-90. 2006 (http://www.math.ntnu.no/~kristiag/drafts/dual-ec-drbg-comments.pdf).
4. ↑ Daniel R. L. Brown: Conjectured Security of the ANSI-NIST Elliptic Curve RNG. 2006 (http://eprint.iacr.org/2006/117).
5. ↑ ^{a b} Daniel R. L. Brown and Kristian Gjøsteen: A Security Analysis of the NIST SP 800-90 Elliptic Curve Random Number Generator. In: CRYPTO 2007. 4622, Springer, 2007, S. 466–481, doi:10.1007/978-3-540-74143-5_26 (http://eprint.iacr.org/2007/048).
6. ↑ Berry Schoenmakers und Andrey Sidorenko: Cryptanalysis of the Dual Elliptic Curve Pseudorandom Generator. 2006 (http://eprint.iacr.org/2006/190).]
7. ↑ Dan Shumow und Niels Ferguson: On the Possibility of a Back Door in the NIST SP800-90 Dual EC PRNG. In: CRYPTO Rump Session 2007. 2007 (http://rump2007.cr.yp.to/15-shumow.pdf).