ed25519-unsafe-libs

Double Public Key Signing Function Oracle Attack auf Ed25519

Eine Liste potenziell unsicherer Ed25519-Signatur-Bibliotheken, die eine öffentliche API bereitstellen, bei der geheimer und öffentlicher Schlüssel unabhängig voneinander als Eingaben für die Signierfunktion angegeben werden können. Eine missbräuchliche Verwendung dieser öffentlichen APIs kann zur Offenlegung des privaten Schlüssels führen.

Die meisten Repositories in unserer Analyse sind in IANIX :: Things that use Ed25519 aufgeführt.

Anzahl betroffener Bibliotheken: 45
Anzahl der Bibliotheken, die das Problem nach der Ankündigung behoben haben: 8
zuletzt aktualisiert: 4. Mai 2023

Proof-of-Concept-Implementierungen, die diesen potenziellen Exploit demonstrieren:

• Rust: ed25519-chalkias-exploit
• Python: Ed25519 Vulnerability in Python, Buchanan, William J (2022). Ed25519 Vulnerability in Python (Recovering Private Key). Asecuritysite.com.

Vorträge:

• Eingeladener Vortrag beim Crypto Reading Club des US-amerikanischen National Institute of Standards and Technology (NIST): Folien – Taming the Many EdDSAs (Seiten 28–39), Konstantinos Chalkias, François Garillot, Valeria Nikolaenko (2023). Taming the Many EdDSAs & Ed25519 Signing Attacks.

Nachrichten- und Social-Media-Berichterstattung zu diesem Angriff

• NIST Crypto Reading Club „Taming the Many EdDSAs" (8. März 2023)
• The Daily Swig „Dozens of cryptography libraries vulnerable to private key theft" (28. Juni 2022)
• Risky Biz News „New crypto vulnerability: Tens of cryptography libraries have misimplemented the Ed25519 digital signature algorithm" (28. Juni 2022)
• SafeHeron-Blogbeitrag „Analysis on Ed25519 Use Risks: Your Wallet Private Key Can Be Stolen" (17. Juni 2022)
• kryptera.se „Vulnerability in most ed25519 libraries" (auf Schwedisch) (29. Juni 2022)
• Difesa e Sicurezza und Yoroi „Librerie crittografiche ed25519 potenzialmente non sicure" (auf Italienisch) (1. Juli und 29. Juni 2022)
• Medium-Beitrag von Prof. Bill Buchanan OBE „Ed25519 is Great, But ..." (1. Juli 2022)
• Reddit r/crypto (bester Beitrag des Monats – 18. Juni 2022)
• Reddit r/cryptography (17. Juni 2022)
• Interessante Tweets:
  • Tweet 1 (von Kostas Kryptos – „The original 26 vulnerable libs")
  • Tweet 2 (von Kostas Kryptos – „Aftermath of the 40 vulnerable libs")
  • Tweet 3 (von Catalin Cimpanu – „40 cryptography libraries are impacted by same Ed25519 misimplementation")
  • Tweet 4 (von Kenny Paterson – „Potential for widespread EdDSA private key recovery, cf. http://kopenpgp.com where same vector exploited in OpenPGP libs")
  • Tweet 5 (von Steven Galbraith – „A hazard for deterministic signatures: better check it is the correct public key!")
  • Tweet 6 (von Riyaz Faizullabhoy – „If you’re using EdDSA in prod please take a look")
  • Tweet 7 (von Bart Preneel – „Reminder that implementing cryptographic algorithms securely and correctly is hard").
• CTF-Herausforderungen (Capture the Flag), die diesen Angriff thematisieren:
  • ImaginaryCTF - JWT25519 (200 Pkt.) (30. Juni 2022)

Worum geht es?

Beachte, dass EdDSA-Signaturen gemäß der zugehörigen rfc8032 normalerweise deterministisch sind. Für dieselbe zu signierende Eingabenachricht wird also eine eindeutige Signaturausgabe zurückgegeben, die zwei Elemente enthält: einen Kurvenpunkt R und einen Skalar S.

Ein algorithmisches Detail ist, dass der öffentliche Schlüssel des Unterzeichners nur in die deterministische Berechnung des S-Teils der Signatur einfließt, nicht jedoch in den R-Wert. Das bedeutet, dass ein Angreifer, wenn er die Signierfunktion irgendwie als Orakel nutzen könnte (das beliebige öffentliche Schlüssel als Eingaben erwartet), für dieselbe Nachricht zwei Signaturen erhalten könnte, die dasselbe R teilen und sich nur im S-Teil unterscheiden. Wenn dies geschieht, kann man leider leicht den privaten Schlüssel extrahieren; dieser StackOverflow-Beitrag erklärt, warum dies machbar ist.

Öffentliche APIs sollten es daher NICHT erlauben, ein entkoppeltes privates/öffentliches Schlüsselpaar als Signiereingabe zu verwenden. Um dies zu umgehen, speichern viele Implementierungen den öffentlichen Schlüssel zusammen mit dem privaten Schlüssel (oder Seed) und behandeln das gesamte Schlüsselpaar als Geheimnis, ODER sie leiten den öffentlichen Schlüssel innerhalb der Signierfunktion immer neu ab. Leider versäumen es zahlreiche bestehende Bibliotheken, dieses Problem zu beheben, indem sie beliebige öffentliche Schlüssel als Eingaben zulassen, ohne zu prüfen, ob der eingegebene öffentliche Schlüssel zum eingegebenen privaten Schlüssel gehört.

Natürlich bedeutet das nicht, dass alle Anwendungen mit Abhängigkeiten zu diesen Bibliotheken anfällig für Schlüsseloffenlegungsangriffe sind; tatsächlich sind die meisten wahrscheinlich sicher, weil sie die betroffene API ihren Benutzern normalerweise nicht öffentlich zugänglich machen und ihr öffentliches/privates Schlüsselpaar direkt vor dem sign-Aufruf koppeln. Andererseits gibt es selbst dann, wenn diese APIs nicht exponiert sind, Anwendungen mit unterschiedlichen TCB-Bedrohungsmodellstrategien, wie private und öffentliche Schlüssel verwaltet und gespeichert werden. Um diesen Angriff zu verhindern, sollten Entwickler daher auch ein Integritätsschutzprotokoll für die öffentlichen Schlüssel durchsetzen.

Hier listen wir einige betroffene Bibliotheken zusammen mit den zugehörigen Code-Referenzen auf.

Abb. 1. Ein Beispiel für API-Missbrauch in der Rust-Crate ed25519-dalek.

Betroffene Bibliotheken

• C: OpenGNB
  https://github.com/gnbdev/opengnb/blob/master/libs/ed25519/sign.c#L7