Bruce Schneier berichtete am 15. November über eine mögliche Hintertür im Zufallszahlengenerator DUAL_EC_DRBG. Dieser wurde auf Empfehlung des US-amerikanischen Geheimdienstes National Security Agency (NSA) in den im März 2007 erschienenen, neuen NIST-Standard für die Erzeugung von Zufallszahlen (SP800-90) aufgenommen. Genauer gesagt, hatte die NSA DUAL_EC_DRBG trotz signifikanter Effizienzschwächen (er ist um drei Größenordnungen langsamer als die anderen Algorithmen) und existierender Alternativen massiv beworben.
Eine Antwort auf die Frage, warum die NSA genau diesen (bereits einige Jahre vorher erstmals veröffentlichten Algorithmus) in der NIST-Empfehlung sehen wollte, mag die Möglichkeit einer existierenden Hintertür sein, mit der sich DUAL_EC_DRBG aushebeln lässt. Auf diese Schwäche machten erstmals Dan Shumow und Niels Ferguson auf der Crypto 2007 Konferenz im August diesen Jahres aufmerksam.
Der DUAL_EC_DRBG verwendet zwei Konstanten P und Q, die im Appendix A.1 des SP800-90 aufgeführt sind. Deren Ursprung ist aber unbekannt, d.h. wir wissen nicht, wie diese Konstanten ausgewählt wurden. Aus mathematischer Sicht besteht ein Verbindung zwischen P und Q in Form einer Zahl k. Ist jemand in Besitz dieser Zahl k, kann er aufgrund der Struktur des Algorithmus mit Hilfe von nur 32 Byte des Outputs den internen Zustand des Systems berechnen, d.h. den Zufallsgenerator knacken.
Wer die Bedenken von Shumow und Ferguson genauer verstehen möchte, braucht etwas Zahlentheorie bzw. Algebra: DUAL_EC_DRBG arbeitet mit elliptischen Kurven (elliptic curves) über endlichen Körpern. Die Punkte einer solchen elliptischen Kurve bilden dann mit der punktweisen Addition eine endliche abelsche Gruppe. Diese habe die Ordnung p mit p prim. Es gilt dann: Zu zwei Punkten P und Q auf dieser Kurve (also zu Elementen P und Q aus der Gruppe) existiert nun ein k mit Q = kP. Sei nun P das Erzeugende der elliptischen Kurve E, d.h. jeder Punkt lässt sich als k-faches von P darstellen. Dann gilt das natürlich insbesondere für Q.
DUAL_EC_DRBG verwendet nun zwei solcher Punkte P und Q als Konstanten. Allgemein lässt sich dann daraus nicht der Faktor k berechnen (Problem des diskreten Logarithmus über endlichen Körpern). Gleichwohl wird nichts darüber ausgesagt, wie diese Konstanten gewonnen wurden. Es ist also möglich, dass P und Q systematisch in Kenntnis von k bestimmt wurden. Wäre dies der Fall, kann der ganze Algorithmus ausgehebelt werden: Mit nur 32 Byte des Outputs kann dann aufgrund der Struktur des Algorithmus auf den internen Zustand des Systems schließen. Mehr dazu lese man bei Shumow und Ferguson nach. In SP800-90 wird im Appendix A.2 sogar auf dieses mögliche Sicherheitsproblem hingewiesen:
[…] The security of Dual_EC_DRBG requires that the points P and Q be properly generated. To avoid using potentially weak points, the points specified in Appendix A.1 should be used. However, an implementation may use different pairs of points, provided that they are verifiably random […]
Ungeachtet dessen hat Microsoft im Service Pack 1 für Windows Vista den neuen Standard SP800-90 samt DUAL_EC_DRBG als Programmierschnittstelle implementiert. Bruce Schneier rät jedoch dringend von der Verwendung dieses offensichtlich gefährdeten Algorithmus zur Erzeugung von Zufallszahlen ab. Speziell kryptographische Software, die gute Zufallszahlen für die Erzeugung der Schlüssel benötigt, sollte unbedingt auf DUAL_EC_DRBG verzichten. Leider ist es für den Nutzer kaum nachzuvollziehen, welche Zufallsgeneratoren ein Programm oder Betriebssystem verwendet. Das als „sicherstes Windows“ gepriesene Vista wird deshalb mit der Einführung von DUAL_EC_DRBG viel weniger sicher.