Der Backdoor-Vorfall bei Dual EC DRBG

Dual Elliptic Curve Deterministic Random Bit Generator (Dual EC DRBG) war einer von vier DRBGs, die NIST in SP 800-90A (2006) standardisierte. Er erzeugt pseudozufällige Bits mithilfe zweier elliptischer Kurvenpunkte P und Q: In jedem Schritt wird r_i = x(s_i * P) berechnet (die x-Koordinate der Skalarmultiplikation), anschließend aktualisiert s_{i+1} = x(r_i * P) den Zustand, und output = x(r_i * Q) erzeugt die Bits. Der Generator wirkte in akademischer Notation legitim. Er wurde in NIST SP 800-90A aufgenommen und später von RSA Security als Standard in deren kryptografischer BSAFE-Bibliothek empfohlen, wodurch er in Unternehmens- und Regierungssoftware Verbreitung fand.

Die Hintertür in Dual EC DRBG nutzt die Beziehung zwischen P und Q aus. Kennt ein Angreifer einen geheimen Skalar e mit Q = e * P, kann er ausgehend von jedem Ausgabe-Block Folgendes berechnen: Aus output = x(r * Q) kann er durch Brute-Force die y-Koordinate von r*Q bestimmen und anschließend r*P = (1/e) * (r*Q) mod n berechnen. Aus r*P kann er alle zukünftigen Ausgaben vorhersagen und den internen Zustand wiederherstellen. Die Kenntnis von e ist die Hintertür – sie entspricht dem diskreten Logarithmus von Q bezüglich P. Der NIST-Standard stellte P- und Q-Werte ohne Erklärung ihrer Auswahl bereit, sodass nicht überprüfbar war, ob sie ohne eine Hintertür zufällig erzeugt worden waren.

Im August 2007 präsentierten Dan Shumow und Niels Ferguson auf der Rump Session der CRYPTO ein wegweisendes Paper mit dem Titel „Über die Möglichkeit einer Hintertür in der NIST SP800-90 Dual Ec Prng“. Sie zeigten formal, dass jemand, der e (den ECDLP von Q bezüglich P) kennt, bei Kenntnis von ungefähr 32 Byte Ausgabe die gesamte Ausgabe von Dual EC DRBG vorhersagen kann. Sie demonstrierten dies anhand eines vereinfachten Beispiels. Ihre Präsentation fand in der Kryptografie-Community große Beachtung. Bruce Schneier schrieb: „Wir haben keine Möglichkeit festzustellen, ob die NSA die Ausgabe von Dual_EC_DRBG lesen kann oder nicht.“ Trotz dieser Warnung blieb Dual EC DRBG noch sechs weitere Jahre Bestandteil des Standards.

Im September 2013 veröffentlichten The New York Times, The Guardian und ProPublica Berichte auf Grundlage von Dokumenten, die Edward Snowden zugespielt worden waren und enthüllten, dass die NSA heimlich Schwachstellen in kryptografische Standards eingeführt hatte. Ein Dokument mit dem Titel „Sigint Enabling Project“ beschrieb ein 250-Millionen-Dollar-pro-Jahr-Programm, um Verschlüsselungsstandards und -produkte „heimlich zu beeinflussen“. Obwohl das Dokument Dual EC DRBG nicht ausdrücklich nannte, kam die Kryptografie-Community in Verbindung mit der mathematischen Demonstration von Shumow und Ferguson weithin zu dem Schluss, dass die NSA die Hintertür eingefügt hatte, indem sie P und Q mit einem bekannten Zusammenhang e auswählte, e geheim hielt und die Konstanten anschließend an NIST übermittelte.

Reuters berichtete im Dezember 2013, dass die NSA RSA Security 10 Millionen US-Dollar dafür gezahlt hatte, Dual EC DRBG zum Standardwert im kryptografischen Toolkit BSAFE von RSA zu machen. RSA Security, damals eine Abteilung von EMC, hatte BSAFE in Unternehmenssoftware verbreitet, die von Finanzinstituten, Gesundheitsunternehmen und staatlichen Auftragnehmern eingesetzt wurde. In einer Stellungnahme bestritt RSA, wissentlich eine Hintertür implementiert zu haben, bestätigte jedoch die Annahme des Vertrags. Diese Enthüllung war besonders schwerwiegend: BSAFE wurde als Sicherheitsprodukt vermarktet, und die Kunden hatten sich gerade wegen der kryptografischen Sicherheit dafür entschieden. Der Vorfall beschädigte den Ruf von RSA Security schwer und führte 2014 zu Boykotten der RSA Conference.

Nach den Enthüllungen im Zuge von Snowden ergriff NIST mehrere Maßnahmen. Im September 2013 öffnete NIST SP 800-90A erneut für öffentliche Stellungnahmen und empfahl, Dual EC DRBG während der laufenden Überprüfung nicht zu verwenden. Im April 2014 veröffentlichte NIST SP 800-90A Revision 1, in der Dual EC DRBG vollständig entfernt wurde — übrig blieben nur Hash_DRBG, HMAC_DRBG und CTR_DRBG. NIST leitete außerdem eine Überprüfung aller kryptografischen Standards und Richtlinien ein, wobei insbesondere untersucht wurde, ob der Einfluss der NSA andere Standards beeinträchtigt hatte. Die Arbeitsgruppe NIST Cryptographic Standards and Guidelines Process wurde eingerichtet, um Transparenz und öffentliche Beteiligung an künftigen Standardisierungsverfahren zu erhöhen.

Die Hintertür in Dual EC DRBG hatte tiefgreifende Auswirkungen auf das Vertrauen der Kryptografie-Community in Standardisierungsgremien. Sie zeigte, dass ein nationaler Nachrichtendienst bereit war, kryptografische Standards, die weltweit eingesetzt wurden, absichtlich zu schwächen — und damit nicht nur Gegner, sondern auch Verbündete, Unternehmen und Privatpersonen zu beeinträchtigen. Der Vorfall beschleunigte die Einführung offener, überprüfbarer Algorithmen mit Nothing-up-my-sleeve-Zahlen: SHA-3s Keccak verwendete einen dokumentierten Algorithmus zur Erzeugung seiner Konstanten; BLAKE2 und BLAKE3 leiten Konstanten aus den Nachkommaanteilen mathematischer Konstanten ab; Curve25519 verwendet eine Primzahl (2^255 - 19), die speziell so gewählt wurde, dass sie überprüfbar ist. Die Erzeugung „nachweislich zufälliger“ Parameter für elliptische Kurven wurde zum Standardverfahren.

Der Skandal um Dual EC DRBG machte das Konzept der „Nothing-up-my-sleeve“- (NUMS-)Konstanten populär — kryptografische Parameter, die aus öffentlich überprüfbaren Quellen erzeugt werden und keine verborgenen Hintertüren enthalten können. Beispiele: SHA-2 verwendet anfängliche Hashwerte, die aus den Quadratwurzeln der ersten 8 Primzahlen abgeleitet werden, sowie Rundungskonstanten aus den Kubikwurzeln der ersten 64 Primzahlen. BLAKE2 leitet Konstanten aus den Nachkommaentwicklungen von pi und anderen mathematischen Konstanten ab. Ed25519 verwendet die Primzahl 2^255 - 19 und einen Basispunkt, dessen diskreter Logarithmus bezüglich jedes anderen Punkts nachweislich unbekannt ist (er wird als Hash eines Strings gewählt). Dadurch kann jeder überprüfen, dass die Konstanten nicht aufgrund geheimen Wissens ausgewählt wurden.

Im Dezember 2015 gab Juniper Networks bekannt, dass seit 2012 nicht autorisierter Code in ScreenOS, dem Firewall-Betriebssystem des Unternehmens, vorhanden gewesen war. Die Untersuchung enthüllte zwei Hintertüren: Eine ersetzte die Q-Konstante von Dual EC DRBG durch einen vom Angreifer kontrollierten Wert und ermöglichte es dem Angreifer, der das entsprechende e kannte, VPN-Datenverkehr zu entschlüsseln; eine zweite Hintertür befand sich im administrativen SSH-Passwort. Der Austausch von Dual ECs Q war besonders raffiniert: Juniper hatte bereits einen nicht standardkonformen Q-Wert verwendet, und der Angreifer ersetzte ihn durch seinen eigenen und nutzte damit die Hintertürenstruktur von Dual EC doppelt aus. Dies zeigte, dass auch Implementierungen, die von den P/Q-Werten von NIST abwichen, von jedem angegriffen werden konnten, der sein eigenes Q einsetzte.

Der Vorfall um Dual EC DRBG lehrt mehrere Dinge. (1) Transparenz: Kryptografische Parameter müssen überprüfbare Ursprünge haben — Konstanten ohne dokumentierte Herleitung sind verdächtig. (2) Algorithmendesign: Algorithmen sollten keine Strukturen aufweisen, in denen sich Hintertüren verbergen könnten; der Zusammenhang zwischen Q und P bei Dual EC bietet gegenüber einfacheren DRBG-Entwürfen keinen Sicherheitsvorteil. (3) Interessenkonflikte: Standardisierungsgremien müssen Interessenkonflikte mit Nachrichtendiensten konsequent handhaben. (4) Überprüfung durch die Community: Akademische Kryptografen sollten in die Lage versetzt werden, Bedenken vor der Veröffentlichung von Standards vorzubringen, nicht erst danach. (5) Wachsamkeit bei der Bereitstellung: Organisationen sollten prüfen, welche DRBGs ihre kryptografischen Bibliotheken verwenden, und nicht empfohlene Optionen proaktiv entfernen.

Nach der Entfernung von Dual EC konzentrierte sich die empfohlene DRBG-Landschaft auf Hash_DRBG, HMAC_DRBG und CTR_DRBG. Die Open-Source-Community verwendet außerdem DRBGs außerhalb der NIST-Standards in Bereichen, in denen den NIST-Standards misstraut wird: Auf ChaCha20 basierende RNGs, die seit Version 5.17 im Linux-Kernel sowie in OpenBSD und libsodium verwendet werden, gelten weithin als resistent gegen Hintertüren, da ChaCha20 eine einfache Stromchiffre ohne Hintertürenstrukturen ist. Fortuna, das in FreeBSD und älteren Versionen von macOS verwendet wird, ist älter als SP 800-90A und genießt weiterhin Vertrauen. Der Vorfall um Dual EC weckte außerdem erneut das Interesse an Hardware-RNGs wie RDRAND als Entropiequellen — allerdings wurde auch RDRAND vorgeworfen, möglicherweise mit einer Hintertür versehen zu sein. Daher wird empfohlen, RDRAND mit Software-Entropie zu mischen, statt es ausschließlich zu verwenden.

Welche mathematische Beziehung ermöglicht die Hintertür in Dual EC DRBG?

Dual EC DRBG wurde 2006 in NIST SP 800-90A standardisiert. Shumow und Ferguson zeigten 2007, dass die Kenntnis von e (wobei Q=e*P gilt) es ermöglicht, anhand von 32 Byte die gesamte Ausgabe vorherzusagen. Die Snowden-Veröffentlichungen bestätigten 2013 den Einfluss der NSA auf kryptografische Standards. Berichten zufolge erhielt RSA Security 10 Millionen US-Dollar dafür, Dual EC zum Standardwert in BSAFE zu machen. NIST entfernte Dual EC in SP 800-90A Revision 1 (2014). Der Vorfall bei Juniper im Jahr 2015 zeigte, dass die Hintertür in einem realen Produkt ausgenutzt wurde. Zu den Lehren gehören NUMS-Konstanten, eine transparente Herleitung, der Umgang mit Interessenkonflikten und Prüfverfahren nach der Standardisierung. Auf ChaCha20 basierende RNGs entwickelten sich zu einer vertrauenswürdigen Alternative.