ECDSA-Nonce-Wiederverwendung: wie eine wiederholte Zahl den privaten Schlüssel verrät

Die Zahl, die sich nie wiederholen darf

Eine ECDSA-Signatur ist ein Paar ganzer Zahlen, (r, s). Um sie zu erzeugen, braucht es drei Eingaben: den privaten Schlüssel d, den Hash der Nachricht z und eine frische, geheime ganze Zahl k – die Nonce, kurz für „number used once“, also eine nur einmal verwendete Zahl. Der Signierer wählt k aus dem Bereich [1, n−1], wobei n die Ordnung des Basispunkts G der Kurve ist, und berechnet:

R = k * G                      (a point on the curve)
r = x-coordinate of R  mod n
s = k^-1 * (z + r * d) mod n

signature = (r, s)

Sieh dir an, woher jede Ausgabe stammt. In s fließt alles zusammen – die Nonce, der Hash und der Schlüssel. r dagegen wird aus k abgeleitet und aus nichts anderem: Es ist die x-Koordinate von kG, eine Funktion allein der Nonce und der Kurve. Die Nachricht fließt nicht ein. Der private Schlüssel fließt nicht ein.

Das ganze Problem passt in einen Satz: Zwei Signaturen, die mit demselben k erzeugt wurden, tragen dasselbe r, und r wird mit jeder Signatur veröffentlicht. Eine wiederholte Nonce ist kein verborgener Fehler, den erst jemand entdecken müsste – sie verrät sich in aller Offenheit, in einem Feld, das jeder Verifizierer liest und jeder Block-Explorer für immer speichert.

Zwei Signaturen, zwei Unbekannte

Angenommen, ein Signierer hat dasselbe k und denselben Schlüssel d für zwei verschiedene Nachrichten mit den Hashes z1 und z2 verwendet. Beide Signaturen haben dasselbe r, also gilt:

s1 = k^-1 * (z1 + r * d) mod n
s2 = k^-1 * (z2 + r * d) mod n

Bis auf k und d ist hier alles öffentlich bekannt. Zwei Gleichungen, zwei Unbekannte. Multipliziere beide Seiten jeder Gleichung mit k, um die Inverse zu beseitigen:

k * s1 = z1 + r * d mod n
k * s2 = z2 + r * d mod n

Der Term r * d ist in beiden Zeilen identisch, weil derselbe Schlüssel beide Nachrichten signiert und dieselbe Nonce dasselbe r erzeugt hat. Ziehst du die zweite Gleichung von der ersten ab, hebt er sich auf, und der private Schlüssel verschwindet vollständig aus der Rechnung:

k * s1 - k * s2 = z1 - z2      mod n
k * (s1 - s2)   = z1 - z2      mod n

k = (z1 - z2) * (s1 - s2)^-1   mod n

Damit ist die Nonce wiederhergestellt. Setzt du sie in eine der beiden Gleichungen aus Schritt 2 ein, erhältst du den Schlüssel, denn r ist jetzt das Einzige, womit d multipliziert wird:

k * s1     = z1 + r * d        mod n
r * d      = k * s1 - z1       mod n

d = (s1 * k - z1) * r^-1       mod n

Vier Schritte, keine Suche, kein Raten. Der Aufwand: zwei modulare Inversionen und eine Handvoll Multiplikationen – Mikrosekunden auf jedem Rechner, aus Daten, die ohnehin öffentlich sind.

Ein praktischer Haken: Kodierungen bewahren nicht immer genau das s, das ein Signierer berechnet hat. Bitcoin und mehrere Bibliotheken normalisieren auf die Low-S-Form und ersetzen s durch n − s, wenn es in der oberen Hälfte des Wertebereichs liegt. Das ist eine Maßnahme gegen Malleability (die Formbarkeit von Signaturen), vorgeschlagen in BIP-62 und in BIP-146 als Relay-Regel festgelegt; mit Nonces hat sie nichts zu tun, berührt aber genau diese Arithmetik. Der wiederhergestellte Wert kann dann −k statt k entsprechen, und das Vorzeichen muss geklärt werden, bevor die Zahlen zusammenpassen. An der Schwierigkeit ändert das nichts; die Kodierung selbst behandelt ein eigener Artikel: ECDSA-Signaturformate.

Kein Gedankenexperiment

Das ist die ergiebigste Klasse realer ECDSA-Fehler, und keiner davon geht auf die Mathematik zurück. In jedem Fall hat eine Implementierung eine Nonce geliefert, die sie nicht hätte liefern dürfen.

• PlayStation 3, 2010. Sonys Implementierung zum Signieren der Firmware setzte dort, wo k hingehört, einen konstanten Wert ein. Jede damit erzeugte Signatur trug dasselbe r, und der Master-Signaturschlüssel der Konsole ließ sich aus zwei beliebigen davon berechnen. Öffentlich vorgeführt wurde der Fehler auf dem 27C3 im Vortrag Console Hacking 2010. Ein reineres Beispiel gibt es nicht: Der Algorithmus war korrekt implementiert – bis auf eine Variable, die nie variierte.
• Android-Wallets, 2013. Am 14. August 2013 veröffentlichte der Android Developers Blog den Beitrag Some SecureRandom Thoughts. Anlass war die Untersuchung dessen, was der Beitrag als „Kompromittierung einer Bitcoin-Transaktion“ beschreibt, „die am 11. August zur Aktualisierung mehrerer Bitcoin-Anwendungen führte“. Die Ursache: Anwendungen, die die Java Cryptography Architecture nutzen, erhalten auf Android-Geräten „wegen einer fehlerhaften Initialisierung des zugrunde liegenden PRNG möglicherweise keine kryptografisch starken Werte“. Wallets, die auf betroffenen Geräten signierten, bezogen ihre Nonces aus einem Generator, der wiederholt im selben Zustand starten konnte. Google lieferte für die API-Level 16–18 den Workaround PRNGFixes aus und patchte die Plattform. Achte darauf, was hier versagt hat: nicht der Kryptocode der Wallet, nicht die Kurve, sondern das Primitiv des Betriebssystems, auf dem beides aufsetzt.
• Die größere Klasse: verzerrte Nonces. Die vollständige Wiederholung ist die laute Variante. Die leise ist eine Nonce, die lediglich schief verteilt ist – ein paar Bits sind nicht gleichverteilt, weil der Generator Werte in einem leicht falschen Bereich liefert, sie abschneidet oder über das Timing etwas preisgibt. Eine saubere algebraische Abkürzung gibt es hier nicht, doch das Problem lässt sich in die Suche nach einem kurzen Vektor in einem Gitter umformen, und Gitterreduktion löst es. Breitner und Heninger haben das in Biased Nonce Sense (Financial Cryptography 2019) auf öffentliche Blockchains und internetweite Scans angewandt und Hunderte Bitcoin-Schlüssel sowie Dutzende Ethereum-, Ripple-, SSH- und HTTPS-Schlüssel wiederhergestellt – aus Nonces, die sich nie wiederholt hatten, sondern bloß unvollkommen waren. Die Lektion ist bitter: „Größtenteils zufällig“ schützt nicht.

Keiner dieser Fälle setzte eine Schwachstelle in ECDSA voraus, und keiner lässt sich mit einer größeren Kurve beheben. Der Algorithmus verlangt für jede Signatur ein perfekt gleichverteiltes Geheimnis und warnt nicht, wenn er keins bekommt.

Was die Blockchain heute zeigt

Wiederholte Werte von r liegen bis heute in der Bitcoin-Blockchain, und zwar dauerhaft, denn Blockchains vergessen nicht. Unser Nonce-Wiederverwendungs-Checker ruft die letzten Transaktionen einer Adresse über die API von mempool.space ab, liest die DER-Signaturen aus den Eingaben, die Guthaben von dieser Adresse ausgeben, und gruppiert sie nach (öffentlicher Schlüssel, r). Für 1BFhrfTTZP3Nw4BNy4eX4KFLsn9ZeijcMm lieferte er am 20. August 2026 dieses Ergebnis:

address                 1BFhrfTTZP3Nw4BNy4eX4KFLsn9ZeijcMm  (P2PKH)
transactions returned   50      <- API cap, not the full history
  spending from it      30
inputs from address     110
signatures parsed       110     (unattributed 0, taproot 0, unparsed 0)
distinct public keys    1
distinct r values       73      <- 110 signatures, only 73 nonces
repeated-r groups       6
identical duplicates    0

Ein Schlüssel, 110 Signaturen, 73 verschiedene Nonces. Die Differenz erzählt die ganze Geschichte: 43 der 110 Signaturen gehören zu einer Gruppe, die ihr r mit mindestens einer anderen Signatur teilt, und in jeder der sechs Gruppen unterscheiden sich die Werte von s – das schließt die harmlose Erklärung einer doppelt veröffentlichten Signatur aus. Die größte Gruppe:

r = d47ce4c025c35ec440bc81d99834a624875161a26bf56ef7fdc0f5d52f843ad1
pubkey = 04dbd0c6...49c5ff (uncompressed)

ad698b53bbba9e7d807559ec7d3a466fccb669dd3659a1604a206eeb9965c527  vin 0  2012-12-21
b4922bc8cc3624487cdcf4b0ed5a98a21a4552a48dfe495490a7443dd546821e  vin 0  2012-12-21
8ab813e5a4039eb79484c315e9c0e201c9d80385c3f3650a4c4b974db9172148  vin 0  2012-12-21
0b5315f4d472a22a6937a20a8d44b8e77099f2a951b65c53c9ebf912352504fa  vin 0  2012-12-19
952d8301780ca74fca5f6541db44ba49e47e8514dfdef36bc7e3d534085dbbf6  vin 0  2012-12-19
    ... 5 more, the oldest on 2012-08-16

Zwei Details verdienen einen zweiten Blick. Erstens besteht die zweitgrößte Gruppe aus weiteren zehn Signaturen mit einem anderen r – und in beiden Gruppen steht jede Signatur am selben Eingabeindex ihrer Transaktion (Index 0 bei der einen, Index 1 bei der anderen). So sieht keine gelegentliche Kollision des RNG aus. So sieht ein Generator aus, der zu Beginn jedes Signiervorgangs auf denselben Zustand zurückgesetzt und dann weitergeschaltet wird: Eingabe 0 bekommt immer den ersten Wert, Eingabe 1 den zweiten. Zweitens reicht die Wiederverwendung von August bis Dezember 2012 – fast ein Jahr vor der Offenlegung des SecureRandom-Problems von Android. Die Fehlerklasse war in freier Wildbahn aktiv, bevor sie einen öffentlichen Namen hatte – eine Erinnerung daran, dass solche Bekanntmachungen markieren, wann ein Problem bemerkt wurde, nicht, wann es begann.

Die Lösung: Schluss mit dem Würfeln

Die dauerhafte Antwort lautet nicht „Nimm einen besseren Zufallszahlengenerator“, sondern: Entferne den Zufallszahlengenerator ganz aus dem Signierpfad.

RFC 6979, deterministisches ECDSA. Statt k zufällig zu ziehen, wird es abgeleitet: Ein HMAC-basierter deterministischer Zufallsbitgenerator (HMAC-DRBG) erhält den privaten Schlüssel und den Hash der Nachricht als Seed, und k wird aus seiner Ausgabe genommen; liegt der Wert außerhalb von [1, n−1], wird neu gezogen. Das Ergebnis wirkt gleichverteilt, ist ohne den Schlüssel nicht vorhersagbar und – das ist entscheidend – eine Funktion der Nachricht. Eine andere Nachricht ergibt zwangsläufig ein anderes k, eine versehentliche Wiederverwendung ist damit strukturell unmöglich statt nur unwahrscheinlich. Signierst du dieselbe Nachricht zweimal, entstehen dieselben Bytes – das ist harmlos und zugleich eine praktische Eigenschaft für Tests. Beim Signieren wird keine Entropiequelle abgefragt, eine defekte kann dir also nicht schaden. FIPS 186-5 erlaubt deterministisches ECDSA neben der randomisierten Variante.

RFC 8032, EdDSA. Ed25519 und Ed448 machen dieselbe Idee zur Pflicht, indem sie sie fest ins Verfahren einbauen: Das Geheimnis pro Signatur entsteht, indem ein aus dem Schlüssel abgeleitetes Präfix zusammen mit der Nachricht gehasht wird, und die API bietet keine Stelle, an der jemand bei der Implementierung stattdessen einen Zufallswert einsetzen könnte. Wenn du ein Verfahren auswählst, statt eines zu übernehmen, beseitigt das diese Fehlerquelle schon durch die Konstruktion. Die Taproot-Signaturen von Bitcoin folgen derselben Philosophie: BIP-340 schreibt eine deterministische Ableitung der Nonce mit optionalem zusätzlichem Zufall vor.

Hedged-Signaturen. Reiner Determinismus hat einen Nachteil, den du kennen solltest: Ein beim Signieren ausgelöster Fehler – ein Glitch am Takt oder an der Spannung einer Smartcard – kann einen deterministischen Signierer dazu bringen, über dieselbe Nachricht mit demselben abgeleiteten k zwei verschiedene Signaturen zu erzeugen; das ist wieder genau die Bedingung der wiederverwendeten Nonce. RFC 6979 geht darauf in §3.6 ein. Die Hedged-Variante mischt frischen Zufall in die deterministische Ableitung, statt sie zu ersetzen; die Nonce ist dann sicher, wenn die Ableitung oder der RNG intakt ist – eines von beiden genügt. Das Go-Paket crypto/ecdsa signiert auf diese Weise; @noble/curves bietet es als Option extraEntropy an; der zusätzliche Zufall in BIP-340 folgt derselben Idee.

So verhalten sich gängige Bibliotheken standardmäßig:

Ein „Nein“ in dieser Tabelle ist kein Fehlerbericht. Eine randomisierte Nonce aus einem intakten CSPRNG des Betriebssystems ist eine völlig konforme Art zu signieren, und genau das sieht jede Fassung von FIPS 186 vor; FIPS 186-5 (2023) hat daneben die deterministische Variante aufgenommen. Die Spalte misst Abhängigkeit, nicht Korrektheit: Bei den „Nein“-Zeilen hängt dein privater Schlüssel an der Entropiequelle im Moment des Signierens, bei den „Ja“-Zeilen nicht. Ob das ins Gewicht fällt, hängt von deiner Umgebung ab – ein gehärteter Server ist ein ganz anderes Risiko als ein frisch gebootetes Embedded-Gerät, ein geklontes VM-Image oder ein Smartphone aus dem Jahr 2013. Das Interop-Cheatsheet für Bibliotheken stellt diesen und die übrigen Unterschiede im Standardverhalten nebeneinander dar.

Was du konkret tun solltest

• Liefere nie dein eigenes k. Akzeptiert eine Signatur-API einen Nonce-Parameter, betrachte ihn als Stolperfalle, nicht als Feature – und greif nie danach, nur weil ein Test reproduzierbare Bytes brauchte. Die liefert dir deterministisches Signieren bereits, und zwar sicher.
• Schreib den Generator nie selbst. „Als Seed nehmen wir den Zeitstempel und die Request-ID“ – genau so fangen solche Vorfälle an. Nutze den CSPRNG der Plattform oder eine Bibliothek, die keinen braucht.
• Prüfe, welche Nonce-Strategie bei dir tatsächlich läuft. Ein zweizeiliger Test verrät dir das meiste – lies das Ergebnis aber genau, denn er kann eine zufällige Nonce nicht von einer Hedged-Nonce unterscheiden:

import { generateKeyPairSync, sign } from "node:crypto";

const { privateKey } = generateKeyPairSync("ec", { namedCurve: "P-256" });
const msg = Buffer.from("same message, twice");

const a = sign("sha256", msg, privateKey);
const b = sign("sha256", msg, privateKey);

console.log(a.equals(b));
// false in node:crypto  -> random or hedged nonce
// true                  -> deterministic derivation (RFC 6979 or EdDSA-style)

Unterscheiden sich die Bytes, weißt du noch nicht, ob die Nonce rein zufällig oder hedged ist – das klärt nur die Dokumentation der Bibliothek. Stimmen sie überein, vergewissere dich, dass es RFC 6979 ist und nichts Selbstgebautes: Vergleiche deine Ausgabe mit den Known-Answer-Testvektoren in RFC 6979, Anhang A.2. Unser ECDSA-Testvektorgenerator erzeugt Signaturen nach RFC 6979 für P-256, P-384, P-521 und secp256k1 aus einem Seed, sodass sich dieselben Vektoren später Byte für Byte neu erzeugen lassen.

• Sei misstrauisch bei Momenten mit wenig Entropie. Der erste Start auf Embedded-Hardware, aus einem gemeinsamen Snapshot wiederhergestellte VMs und Container sowie die frühe Init-Phase, bevor der Entropie-Pool einen Seed erhalten hat: Hier enttäuscht eine zufällige Nonce am ehesten. Deterministisches Signieren macht die Frage gegenstandslos.
• Findest du eine Wiederverwendung, ist der Schlüssel verloren. Nicht geschwächt – verloren, und zwar rückwirkend, für alle, die diese beiden Signaturen je gesehen haben. Verschiebe das Guthaben, rotiere den Schlüssel überall, wo er im Einsatz ist, und rechne damit, dass jede Signatur, die er je erzeugt hat, ebenso gut von jemand anderem stammen kann.

Primärquellen

• RFC 6979 – deterministische Verwendung von DSA und ECDSA. Die Ableitung per HMAC-DRBG, ihre Begründung und Known-Answer-Testvektoren in Anhang A; der Vorbehalt zu Fehlerinjektionsangriffen steht in §3.6.
• RFC 8032 – EdDSA (Ed25519, Ed448), bei dem die deterministische Ableitung der Nonce Teil des Verfahrens ist und keine Option.
• FIPS 186-5 – der aktuelle Digital Signature Standard, der ECDSA spezifiziert und die deterministische Erzeugung der Nonce erlaubt.
• Some SecureRandom Thoughts – Android Developers Blog, 14. August 2013: der Initialisierungsfehler im PRNG der Plattform, sein Zusammenhang mit der Kompromittierung der Bitcoin-Wallets und der Workaround PRNGFixes.
• Biased Nonce Sense – Breitner und Heninger, IACR ePrint 2019/023 / Financial Cryptography 2019: gitterbasierte Angriffe auf lediglich verzerrte Nonces, gemessen an echten Daten aus Blockchains und internetweiten Scans.
• Console Hacking 2010 – 27C3, die öffentliche Vorführung des PlayStation-3-Fehlers mit der konstanten Nonce.
• BIP-62 und BIP-146 – Low-S-Kanonisierung (eine Maßnahme gegen Malleability, nicht gegen Nonce-Fehler, aber der Grund, warum wiederhergestellte Werte eine Vorzeichenkorrektur brauchen können), dazu BIP-340 für die von Taproot vorgeschriebene deterministische Nonce.
• libsecp256k1 und @noble/curves – zwei vielfach auditierte Implementierungen, die standardmäßig RFC 6979 nutzen und deren Quellcode am klarsten dokumentiert, wie eine Ableitung der Nonce aussehen sollte.

Warum diese Anforderung an die Nonce einer der wenigen echten betrieblichen Vorteile ist, die RSA noch hat, und wie sich die beiden Algorithmen sonst unterscheiden, erklärt ECDSA vs. RSA.