„Dual EC DRBG“ – Versionsunterschied

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen
Versionsgeschichte interaktiv durchsuchen
[gesichtete Version][gesichtete Version]
← Zum vorherigen VersionsunterschiedZum nächsten Versionsunterschied →
Inhalt gelöscht Inhalt hinzugefügt
VisuellWikitext
Backdoor-Enthüllungen präzisiert
Zeile 1: Zeile 1:
{{SEITENTITEL: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" /> Kurz nach der Publikation durch das NIST im Jahr 2007 wurden Vermutungen laut, der Algorithmus enthalte eine [[Kleptographie|kleptographische]] [[Backdoor]], welche sich im September 2013 bewahrheiteten.<ref name="wired-schneier" />
'''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" />

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" />


== Sicherheit ==
== Sicherheit ==
Zeile 14: Zeile 16:
[[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>http://www.golem.de/news/dual-ec-das-patent-auf-die-nsa-hintertuer-1406-107219.html</ref>
[[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>http://www.golem.de/news/dual-ec-das-patent-auf-die-nsa-hintertuer-1406-107219.html</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 D. 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.
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" /> Diese Berichte werden weitgehend als Bestätigung einer Backdoor in Dual_EC_DRBG gewertet.<ref name="nytimes-2013-1" /><ref name="bernstein-2016" /><ref name="green-2017" />
⚫
Laut einem Bericht der [[New York Times]] im September 2013 über die Enthüllungen des [[Whistleblower]]s [[Edward Snowden]] bestätigen geheime Memos des [[Vereinigte Staaten von Amerika|US]]-[[Nachrichtendienst|Auslandsgeheimdienstes]] [[National Security Agency|NSA]], dass diese Schwachstelle durch die [[National Security Agency|NSA]] entwickelt worden war.<ref>http://www.nytimes.com/2013/09/06/us/nsa-foils-much-internet-encryption.html?pagewanted=3</ref> 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. Das Normungsinstitut NIST hat angekündigt, den Standard einer neuen Überprüfung zu unterziehen.<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>
Die Implementierungsliste der US-Normungsbehörde NIST gibt einen Überblick über die von Implementierungen verwendeten Zufallszahlengeneratoren.<ref>[[NIST]]: [http://csrc.nist.gov/groups/STM/cavp/documents/drbg/drbgval.html ''Liste der Implementierung von Zufallszahlen-Erzeugungsverfahren''], 28. April 2014.</ref>


⚫
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>
⚫
Das NIST entschied nach einer Anhörungsphase, Dual_EC_DRBG 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.<ref> {{Webarchiv|text=Archivlink |url=http://csrc.nist.gov/groups/ST/toolkit/800-90A-RFC.html |wayback=20140723001417 |archiv-bot=2018-04-07 09:11:52 InternetArchiveBot }}</ref>

⚫
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.<ref> {{Webarchiv|text=Archivlink |url=http://csrc.nist.gov/groups/ST/toolkit/800-90A-RFC.html |wayback=20140723001417 |archiv-bot=2018-04-07 09:11:52 InternetArchiveBot }}</ref>


== Einzelnachweise ==
== Einzelnachweise ==
Zeile 36: Zeile 39:
| datum=2007-11-15
| datum=2007-11-15
| abruf=2011-10-09}}</ref>
| 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>
<ref name=Gj06>
{{Literatur
{{Literatur
Zeile 73: Zeile 104:
| Datum=2007
| Datum=2007
| Online=http://rump2007.cr.yp.to/15-shumow.pdf
| 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>
</references>
</references>

Version vom 18. Oktober 2023, 16:35 Uhr

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.[1]

Kurz nach der Publikation durch das NIST im Jahr 2007 wurden Vermutungen laut, der Algorithmus enthalte eine kleptographische Backdoor.[2] 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.[3][4][5]

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[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.[6][7][8]

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.[6][8][9]
  • 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 Dan Shumow und Niels Ferguson, dass der Algorithmus eine Schwäche aufweist, die als Backdoor ausgenutzt werden kann.[10] 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.[11]

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.[12][13] 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.[14][15] Diese Berichte werden weitgehend als Bestätigung einer Backdoor in Dual_EC_DRBG gewertet.[3][4][5]

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.[16][17]

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.[18]

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 (nist.gov [PDF]).
  2. ↑ a b Bruce Schneier: Did NSA Put a Secret Backdoor in New Encryption Standard? Wired, 15. November 2007, abgerufen am 9. Oktober 2011 (englisch).
  3. ↑ a b Nicole Perlroth: Government Announces Steps to Restore Confidence on Encryption Standards. In: New York Times Bits Blog. 10. September 2013, abgerufen am 18. Oktober 2023.
  4. ↑ a b Daniel J. Bernstein, Tanja Lange, Ruben Niederhagen: Dual EC: A Standardized Back Door. In: Peter Y. A. Ryan, David Naccache, Jean-Jacques Quisquater (Hrsg.): The New Codebreakers. Lecture Notes in Computer Science. Band 9100. Springer, Berlin/Heidelberg 18. März 2016, doi:10.1007/978-3-662-49301-4_17.
  5. ↑ a b Matthew Green: The strange story of “Extended Random”]. In: A Few Thoughts on Cryptographic Engineering. 19. Dezember 2017, abgerufen am 18. Oktober 2023.
  6. ↑ a b Kristian Gjøsteen: Comments on Dual-EC-DRBG/NIST SP 800-90. 2006 (ntnu.no [PDF]). Comments on Dual-EC-DRBG/NIST SP 800-90 (Memento des Originals vom 25. Mai 2011 im Internet Archive)  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.@1@2Vorlage:Webachiv/IABot/www.math.ntnu.no
  7. ↑ Daniel R. L. Brown: Conjectured Security of the ANSI-NIST Elliptic Curve RNG. 2006 (iacr.org).
  8. ↑ 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. Band 4622. Springer, 2007, S. 466–481, doi:10.1007/978-3-540-74143-5_26 (iacr.org).
  9. ↑ Berry Schoenmakers und Andrey Sidorenko: Cryptanalysis of the Dual Elliptic Curve Pseudorandom Generator. 2006 (iacr.org).
  10. ↑ 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 (yp.to [PDF]).
  11. ↑ http://www.golem.de/news/dual-ec-das-patent-auf-die-nsa-hintertuer-1406-107219.html
  12. ↑ Matthew Green: The Many Flaws of Dual_EC_DRBG
  13. ↑ Aris Adamantiadis: Dual_Ec_Drbg backdoor: a proof of concept, 28. April 2014.
  14. ↑ Nicole Perlroth, Jeff Larson, Scott Shane: N.S.A. Able to Foil Basic Safeguards of Privacy on Web. In: New York Times. 5. September 2013, abgerufen am 18. Oktober 2023.
  15. ↑ James Ball, Julian Borger, Glenn Greenwald: Revealed: how US and UK spy agencies defeat internet privacy and security. In: The Guardian. 6. September 2013, abgerufen am 18. Oktober 2023.
  16. ↑ Wired: RSA Tells Its Developer Customers: Stop Using NSA-Linked Algorithm, 19. September 2013.
  17. ↑ Zeit Online: NSA hackt Kryptografie: Sicherheitsfirma RSA warnt vor sich selbst, 20. September 2013.
  18. ↑ Archivlink (Memento des Originals vom 23. Juli 2014 im Internet Archive)  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.@1@2Vorlage:Webachiv/IABot/csrc.nist.gov
Abgerufen von „https://de.wikipedia.org/w/index.php?title=Dual_EC_DRBG&oldid=238275506“