Quelltext der Seite Dual EC DRBG

{{SEITENTITEL:Dual_EC_DRBG}}
'''Dual_EC_DRBG''' ({{enS|'''''Dual E'''lliptic '''C'''urve '''D'''eterministic '''R'''andom '''B'''it '''G'''enerator''}}) 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.<ref name="NIST-800-90-rev1" />

Kurz nach der Publikation durch das NIST im Jahr 2007 wurden Vermutungen laut, der [[Algorithmus]] enthalte eine [[Kleptographie|kleptographische]] [[Backdoor]].<ref name="wired-schneier" /> Im Zuge der [[Globale Überwachungs- und Spionageaffäre|Enthüllungen von Edward Snowden]] wurden 2013 Dokumente bekannt, die weithin als Beleg für eine von der [[National Security Agency|NSA]] bewusst eingebaute Backdoor betrachtet werden.<ref name="nytimes-2013-1" /><ref name="bernstein-2016" /><ref name="green-2017" />

== Algorithmus ==
Gegeben seien:
* Zwei konstante und öffentlich bekannte Punkte <math>P, Q</math> auf der [[Elliptische Kurve|elliptischen Kurve]] NIST P-256 (alternativ P-384 oder P-521).
* Ein interner Zustand <math>s_i</math> als 256 Bit Integer (bzw. je nach Kurve 384 oder 521 Bit). Der [[Seed key|Startwert]] <math>s_0</math> wird durch eine [[Entropie (Informationstheorie)|Entropiequelle]] erzeugt.<ref name="bernstein-2016" />
* <math>s_i*P</math> ist die [[Elliptische_Kurve#Skalare_Multiplikation_eines_Punktes|skalare Multiplikation eines Punktes]], wobei <math>\varphi(s_i*P)</math> die <math>x</math>-Koordinate des neuen Punkts zurückgibt. Es handelt sich hierbei um eine [[Einwegfunktion]] basierend auf dem Problem des [[Diskreter Logarithmus|diskreten Logarithmus]] in elliptischen Kurven ([[ECDLP]]).

[[Datei:DUAL_EC_DRBG.jpg|800px]]

Der Algorithmus ist in zwei Varianten aus den Jahren 2006<ref name="NIST-800-90" /> und 2007<ref name="NIST-800-90-rev1" /> bekannt. Der Unterschied der überarbeiteten Variante ist eine zusätzliche Punktmultiplikation bei der Rückkopplung in den internen Zustand. Eine Iteration des Algorithmus arbeitet wie folgt:

# Berechne <math>r_i = \varphi(s_i*P)</math>.
# Setze den internen Zustand für die nächste Iteration auf <math>s_{i+1}=r_i</math>. In Variante 2007 erfolgt dies als <math>s_{i+1}=\varphi(r_i*P)</math>.
# Berechne <math>t_i = \varphi(r_i*Q)</math>.
# Schneide die höchstwertigen 16 Bit von <math>t_i</math> ab und gib die restlichen 240 Bit (bzw. je nach Kurve 368 oder 504 Bit) als Pseudozufallsbits zurück.

Falls mehr Zufallsbits benötigt werden, werden weitere Iterationen durchgeführt.

== 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 [[Elliptische Kurve|elliptischen Kurve]] [[Reduktion (Theoretische Informatik)|reduzieren]] lässt. 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.<ref name="Gj06" /><ref name="Br06" /><ref name="BG07" /> Dual_EC_DRBG war der einzige PRNG im NIST-Standard, dessen Sicherheit auf einem zahlentheoretischen Problem basiert.<ref name="NIST-800-90-rev1" /> Dessen Geschwindigkeit ist allerdings auch um drei Größenordnungen langsamer gegenüber den drei anderen standardisierten Verfahren.<ref name="wired-schneier" />

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 [[Stromverschlüsselung|Stromchiffre]] und für weitere Anwendungen ungeeignet.<ref name="Gj06" /><ref name="BG07"/><ref name="SS06" />
* 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 Abschnitt [[#Kontroverse]]).

== 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.<ref name="SF07" /> 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.<ref>{{Internetquelle | autor= | url=http://www.golem.de/news/dual-ec-das-patent-auf-die-nsa-hintertuer-1406-107219.html | titel=Dual EC: Das Patent auf die NSA-Hintertür | werk=[[golem.de]] | datum=2014-06-16 |abruf=2024-02-03}}</ref>

Auf der im Standard definierten Kurve ist ein Punkt ''P'' vorgegeben, der die [[zyklische Gruppe]] [[Erzeuger (Algebra)|erzeugt]]. Zusätzlich ist ein Punkt ''Q'' definiert. Da die Gruppe zyklisch ist, existiert eine Zahl ''d'', mit ''Q = dP'', der [[Diskreter Logarithmus|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.<ref>Matthew Green: [http://blog.cryptographyengineering.com/2013/09/the-many-flaws-of-dualecdrbg.html The Many Flaws of Dual_EC_DRBG]</ref><ref>Aris Adamantiadis: [http://blog.0xbadc0de.be ''Dual_Ec_Drbg backdoor: a proof of concept''], 28. April 2014.</ref> Da es sich bei den Punkten nicht um [[Unverdächtige Konstante|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 [[Whistleblower]]s [[Edward Snowden]] berichteten [[New York Times]] und [[The Guardian|Guardian]] im September 2013 über geheime Dokumente, denen zufolge die [[National Security Agency|NSA]] als Teil des Projekts „Bullrun“ [[Verschlüsselungsverfahren]] geschwächt hat.<ref name="nytimes-2013-2"/><ref name="guardian-2013" /> 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.<ref name="nytimes-2013-1" /><ref name="bernstein-2016" /><ref name="green-2017" />

Mitte September 2013 veröffentlichte das Unternehmen [[RSA Security]], unter anderem Anbieter der Kryptografie-[[Programmbibliothek]] ''RSA BSafe'' und des [[Authentifizierung]]ssystem ''[[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.<ref>[[Wired]]: [http://www.wired.com/threatlevel/2013/09/rsa-advisory-nsa-algorithm/ ''RSA Tells Its Developer Customers: Stop Using NSA-Linked Algorithm''], 19. September 2013.</ref><ref>[[Die Zeit|Zeit Online]]: [http://www.zeit.de/digital/datenschutz/2013-09/rsa-bsafe-kryptografie-nsa ''NSA hackt Kryptografie: Sicherheitsfirma RSA warnt vor sich selbst''], 20. September 2013.</ref> Laut einem Bericht von [[Reuters]] hatte RSA Security von der NSA 10&nbsp;Millionen US-Dollar erhalten, um das Verfahren als Standard in ''BSafe'' zu verwenden.<ref name="reuters-2013" />

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.<ref>{{Internetquelle |url=https://www.nist.gov/news-events/news/2014/04/nist-removes-cryptography-algorithm-random-number-generator-recommendations |titel=NIST Removes Cryptography Algorithm from Random Number Generator Recommendations |abruf=2026-04-06 |datum=2014-04-21}}</ref> Am 21. April 2014 bat das NIST um Kommentare zu einem Entwurf für eine überarbeitete Version des Standards SP 800-90A, die Dual_EC_DRBG nicht mehr enthält.<ref>{{Webarchiv|text=Archivlink|url=http://csrc.nist.gov/groups/ST/toolkit/800-90A-RFC.html|wayback=20140723001417}}</ref> Die überarbeitete Version wurde 2015 als SP 800-90A Revision 1 veröffentlicht.<ref name="NIST-800-90A-rev1" />

== Sicherheitslücke in Juniper ScreenOS ==
Im Dezember 2015 gab der Netzwerkausrüster [[Juniper Networks|Juniper]] bekannt, in seinem Betriebssystem ''ScreenOS'' „unautorisierten Code“ entdeckt zu haben.<ref name="juniper-2015" /> Dies steht in Zusammenhang mit Dual_EC_DRBG: Laut Analysen unabhängiger Sicherheitsforscher<ref name="green-2015" /><ref name="checkoway-2016" /> 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.<ref name="green-2015" /> 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.

== Einzelnachweise ==
<references>
<ref name="NIST-800-90">{{Literatur
 | Herausgeber=[[National Institute of Standards and Technology]]
 | Titel=NIST SP 800-90: Recommendation for Random Number Generation Using Deterministic Random Bit Generators
 | Datum=2006-06
 | DOI=10.6028/NIST.SP.800-90
 | Online=https://csrc.nist.gov/pubs/sp/800/90/final}}</ref>
<ref name="NIST-800-90-rev1">{{Literatur
 | Herausgeber=[[National Institute of Standards and Technology]]
 | Titel=NIST SP 800-90: Recommendation for Random Number Generation Using Deterministic Random Bit Generators (Revised)
 | Datum=2007-03
 | DOI=10.6028/NIST.SP.800-90r
 | Online=https://csrc.nist.gov/pubs/sp/800/90/r1/final}}</ref>
<ref name="NIST-800-90A-rev1">{{Literatur
 | Herausgeber=[[National Institute of Standards and Technology]]
 | Titel=NIST SP 800-90 Revision 1: Recommendation for Random Number Generation Using Deterministic Random Bit Generators
 | Datum=2015-06
 | DOI=10.6028/NIST.SP.800-90Ar1
 | Online=https://csrc.nist.gov/pubs/sp/800/90/a/r1/final}}</ref>
<ref name="wired-schneier">{{Internetquelle
| autor=[[Bruce Schneier]]
| hrsg=[[Wired]]
|url=http://www.wired.com/politics/security/commentary/securitymatters/2007/11/securitymatters_1115
| sprache=en
| titel=Did NSA Put a Secret Backdoor in New Encryption Standard?
| datum=2007-11-15
| archiv-url=https://web.archive.org/web/20120606003723/http://www.wired.com/politics/security/commentary/securitymatters/2007/11/securitymatters_1115
| archiv-datum=2012-06-06
| abruf=2011-10-09}}</ref>
<ref name="nytimes-2013-1">{{Internetquelle
 | autor=Nicole Perlroth
 | titel=Government Announces Steps to Restore Confidence on Encryption Standards
 | werk=New York Times Bits Blog
 | datum=2013-09-10
 | url=https://archive.nytimes.com/bits.blogs.nytimes.com/2013/09/10/government-announces-steps-to-restore-confidence-on-encryption-standards/
 | abruf=2023-10-18
}}</ref>
<ref name="bernstein-2016">{{Literatur
 | Autor=Daniel J. Bernstein, Tanja Lange, Ruben Niederhagen
 | Titel=Dual EC: A Standardized Back Door
 | Hrsg=Peter Y. A. Ryan, David Naccache, Jean-Jacques Quisquater
 | Sammelwerk=The New Codebreakers
 | WerkErg=Lecture Notes in Computer Science
 | Band=9100
 | Verlag=Springer
 | Ort=Berlin/Heidelberg
 | Datum=2016-03-18
 | DOI=10.1007/978-3-662-49301-4_17
}}</ref>
<ref name="green-2017">{{Internetquelle
 | autor=Matthew Green
 | titel=The strange story of “Extended Random”
 | werk=A Few Thoughts on Cryptographic Engineering
 | datum=2017-12-19
 | url=https://blog.cryptographyengineering.com/2017/12/19/the-strange-story-of-extended-random/
 | abruf=2023-10-18
}}</ref>
<ref name=Gj06>
{{Literatur
 | Autor=Kristian Gjøsteen
 | Titel=Comments on Dual-EC-DRBG/NIST SP 800-90
 | Datum=2006
 | Online=http://www.math.ntnu.no/~kristiag/drafts/dual-ec-drbg-comments.pdf
 }} {{Webarchiv|url=http://www.math.ntnu.no/~kristiag/drafts/dual-ec-drbg-comments.pdf|wayback=20110525081912|text=Comments on Dual-EC-DRBG/NIST SP 800-90}}
</ref>
<ref name="Br06">{{Literatur
 | Autor=Daniel R. L. Brown
 | Titel=Conjectured Security of the ANSI-NIST Elliptic Curve RNG
 | Datum=2006
 | Online=http://eprint.iacr.org/2006/117
}}</ref>
<ref name="BG07">{{Literatur
 | Autor=Daniel R. L. Brown and Kristian Gjøsteen
 | Titel=A Security Analysis of the NIST SP 800-90 Elliptic Curve Random Number Generator
 | Sammelwerk=CRYPTO 2007
 | Verlag=Springer
 | Band=4622
 | Datum=2007
 | Seiten=466–481
 | DOI=10.1007/978-3-540-74143-5_26
 | Online=http://eprint.iacr.org/2007/048
}}</ref>
<ref name="SS06">{{Literatur
 | Autor=Berry Schoenmakers und Andrey Sidorenko
 | Titel=Cryptanalysis of the Dual Elliptic Curve Pseudorandom Generator
 | Datum=2006
 | Online=http://eprint.iacr.org/2006/190
}}</ref>
<ref name="SF07">{{Literatur
 | Autor=Dan Shumow und [[Niels Ferguson]]
 | Titel=On the Possibility of a Back Door in the NIST SP800-90 Dual EC PRNG
 | Sammelwerk=CRYPTO Rump Session 2007
 | Datum=2007
 | Online=http://rump2007.cr.yp.to/15-shumow.pdf
}}</ref>
<ref name="nytimes-2013-2">{{Internetquelle
 | autor=Nicole Perlroth, Jeff Larson, Scott Shane
 | titel=N.S.A. Able to Foil Basic Safeguards of Privacy on Web
 | werk=New York Times
 | datum=2013-09-05
 | url=https://www.nytimes.com/2013/09/06/us/nsa-foils-much-internet-encryption.html
 | abruf=2023-10-18
}}</ref>
<ref name="guardian-2013">{{Internetquelle
 | autor=James Ball, Julian Borger, Glenn Greenwald
 | titel=Revealed: how US and UK spy agencies defeat internet privacy and security
 | werk=The Guardian
 | datum=2013-09-06
 | url=https://www.theguardian.com/world/2013/sep/05/nsa-gchq-encryption-codes-security
 | abruf=2023-10-18
}}</ref>
<ref name="reuters-2013">{{Internetquelle
 | autor=Joseph Menn
 | titel=Exclusive: Secret contract tied NSA and security industry pioneer
 | werk=Reuters
 | datum=2013-12-20
 | url=https://www.reuters.com/article/us-usa-security-rsa/exclusive-secret-contract-tied-nsa-and-security-industry-pioneer-idUSBRE9BJ1C220131220
 | abruf=2023-10-18
}}</ref>
<ref name="juniper-2015">{{Internetquelle
 | autor=Derrick Scholl
 | titel=Important Announcement about ScreenOS®
 | datum=2015-12-17
 | url=https://community.juniper.net/blogs/dscholl1/2020/12/23/important-announcement-about-screenos
 | abruf=2023-10-18
}}</ref>
<ref name="green-2015">{{Internetquelle
 | autor=Matthew Green
 | titel=On the Juniper backdoor
 | werk=A Few Thoughts on Cryptographic Engineering
 | datum=2015-12-22
 | url=https://blog.cryptographyengineering.com/2015/12/22/on-juniper-backdoor/
 | abruf=2023-10-18
}}</ref>
<ref name="checkoway-2016">{{Literatur
 | Autor=Stephen Checkoway, Jacob Maskiewicz, Christina Garman, Joshua Fried, Shaanan Cohney, Matthew Green, Nadia Heninger, Ralf-Philipp Weinmann, Eric Rescorla, Hovav Shacham
 | Titel=A Systematic Analysis of the Juniper Dual EC Incident
 | Sammelwerk=Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security
 | Verlag=ACM
 | Ort=Wien
 | Datum=2016-10-24
 | DOI=10.1145/2976749.2978395
}}</ref>
</references>

{{SORTIERUNG:Dual Ec Drbg}}
[[Kategorie:Kryptologisches Verfahren]]
[[Kategorie:Pseudozufallszahlengenerator]]
[[Kategorie:Sicherheitslücke]]
[[Kategorie:Abkürzung]]