Dual_EC_DRBG

Dual_EC_DRBG (englisch Dual Elliptic Curve Deterministic Random Bit Generator) ist ein von der National Security Agency entwickelter und veröffentlichter kryptographisch sicherer Zufallszahlengenerator (PRNG). Trotz öffentlicher Kritik war das Verfahren eines von vier (jetzt drei) in der NIST Special Publication 800-90 standardisierten PRNGs.

Kurz nach der Publikation durch das NIST im Jahr 2007 wurden Vermutungen laut, der Algorithmus enthalte eine kleptographische Backdoor. Im Zuge der Enthüllungen von Edward Snowden wurden 2013 Dokumente bekannt, die weithin als Beleg für eine von der NSA bewusst eingebaute Backdoor betrachtet werden.

Sicherheit

Der Grund für die Aufnahme von Dual_EC_DRBG 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ößenordnungen gegenüber den anderen drei standardisierten Verfahren 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.

Nach der Veröffentlichung 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.
• 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 warnten die damaligen Microsoft-Mitarbeiter Dan Shumow und Niels Ferguson, dass der Algorithmus eine Schwäche aufweist, die als Backdoor ausgenutzt werden kann. PRNGs sind ein vielfach genutztes kryptographisches Primitiv, und diese Schwäche kann ausgenutzt werden, um jedes kryptographische Verfahren, das auf Dual EC beruht, zu brechen.

Tanja Lange und Daniel Bernstein fanden 2013 die erste Beschreibung der Hintertür – ausdrücklich gegen das TLS-Protokoll gerichtet – in einer vorläufigen Patentanmeldung der Firma Certicom vom 21. Januar 2005.

Auf der im Standard definierten Kurve ist ein Punkt P vorgegeben, der die zyklische Gruppe erzeugt. Zusätzlich ist ein Punkt Q definiert. Da die Gruppe zyklisch ist, existiert eine Zahl d, mit Q = dP, der diskrete Logarithmus von Q zur Basis P in der hier additiv geschriebenen Gruppe. Shumow und Ferguson konnten zeigen, dass die Kenntnis von d es einem Angreifer erlauben würde, das Verfahren zu brechen. Es ist nicht klar, wie diese Konstanten P und Q gewählt wurden. Wenn Q echt zufällig gewählt wurde, ist es praktisch unmöglich, d zu berechnen. Es besteht jedoch die Möglichkeit, dass P und d gewählt wurden und Q = dP berechnet wurde. In diesem Fall könnte derjenige, der die beiden Punkte wählte, jede Instanz des PRNG auf dieser Kurve brechen. Da es sich bei den Punkten nicht um unverdächtige Konstanten handelt, kann eine Hintertür nicht ausgeschlossen werden. Im Anhang A des Standards ist allerdings eine Methode definiert, wie eine eigene Kurve mit selbstgewählten Konstanten erzeugt werden kann.

Im Zuge der Enthüllungen des Whistleblowers Edward Snowden berichteten New York Times und Guardian im September 2013 über geheime Dokumente, denen zufolge die NSA als Teil des Projekts „Bullrun“ Verschlüsselungsverfahren geschwächt hat. Laut Beschreibung der New York Times soll unter anderem ein NIST-Standard aus 2006, in dem zwei Microsoft-Kryptographen 2007 eine schwere Schwachstelle entdeckt hätten, Teil des Projekts sein. Der Bericht wird weitgehend als Bestätigung einer Backdoor in Dual_EC_DRBG gewertet.

Mitte September 2013 veröffentlichte das Unternehmen RSA Security, unter anderem Anbieter der Kryptografie-Programmbibliothek RSA BSafe und des Authentifizierungssystem SecurID, eine Empfehlung an Entwickler die mit ihren Programmbibliotheken arbeiten, den darin als Standard enthaltenen Dual_EC_DRBG nicht weiter zu verwenden und stattdessen einen anderen Zufallszahlengenerator einzusetzen. Betroffen davon sind alle Anwendungen, die auf RSA BSafe zurückgreifen. Laut einem Bericht von Reuters hatte RSA Security von der NSA 10 Millionen US-Dollar erhalten, um das Verfahren als Standard in BSafe zu verwenden.

Als Reaktion auf die Kontroverse unterzog das NIST Dual_EC_DRBG einer neuen Überprüfung und entschied schließlich, das Verfahren aus dem Standard zu entfernen. Am 21. April 2014 veröffentlichte das NIST einen Entwurf für eine überarbeitete Version des Standards SP 800-90A, die Dual_EC_DRBG nicht mehr enthält.

Sicherheitslücke in Juniper ScreenOS

Im Dezember 2015 gab der Netzwerkausrüster Juniper bekannt, in seinem Betriebssystem ScreenOS „unauthorisierten Code“ entdeckt zu haben. Dies steht in Zusammenhang mit Dual_EC_DRBG: Laut Analysen unabhängiger Sicherheitsforscher sollten mittels Dual_EC_DRBG erzeugte Zufallszahlen eigentlich durch einen weiteren Zufallszahlengenerator weiterverarbeitet werden, was jedoch durch einen (absichtlichen oder unabsichtlichen) Programmierfehler verhindert wurde. Dadurch wurden die mit dem Verfahren erzeugten Zufallszahlen direkt verwendet, was aufgrund von dessen Schwäche einer Backdoor gleichkommt.

Im Jahr 2012 tauschten unbekannte Angreifer den Parameter Q im ScreenOS-Quellcode aus, wodurch sie prinzipiell die Schwachstelle in Dual_EC_DRBG ausnutzen konnten. Es handelte sich also um einen Supply-Chain-Angriff gegen Kunden von Juniper. Dabei wurde eine vorhandene Backdoor angepasst, um eine neue Backdoor zu erzeugen.