NIST-Kurven-Seeds geknackt: 5 Mythen über ECDSA

Seit fünfundzwanzig Jahren waren die NIST-ECDSA-Kurven-Seeds das Nächste, was die angewandte Kryptografie einem ungelösten Cold Case gleichkam. Fünf scheinbar zufällige 160-Bit-Werte, von der NSA ohne jede Erklärung an das NIST übergeben und doch die Grundlage für Signaturen bei allem, von deinen TLS-Verbindungen bis zu Bitcoin-Transaktionen. Diese Woche ist der Fall geschlossen, und die Antwort ist fast peinlich: Die Seeds waren Ausgaben des lrand48()-Generators der C-Bibliothek, initialisiert mit Unix-Zeitstempeln aus 1997 und 1998. Das war's. Kein Hash einer geheimen Passphrase, keine exotische Maschinerie, sondern srand48(time(NULL)), genau das Muster, von dem dir jeder Security-Kurs sagt, du sollst es nie verwenden.

Die Entdeckung stammt von einem Forschungsmodell von Anthropic, auf das Problem gebracht von einem neugierigen Mitarbeiter. Es erkannte in den veröffentlichten Konstanten die statistische Signatur eines linearen Kongruenzgenerators aus den 1990ern, rechnete den Zustand rückwärts und landete schließlich bei Kalenderdaten. Ich habe genug Jahre mit der Prüfung kryptografischer Systeme verbracht, um zu wissen, dass das wichtig ist. Nicht weil die Kurven gebrochen wären (sind sie nicht), sondern weil es mehrere Dinge zerlegt, an die unsere Branche selbstsicher geglaubt hat. Gehen wir die Mythen der Reihe nach durch.

Mythos 1: Unerklärte Konstanten bedeuten eine versteckte Backdoor

Der Verdacht war nie abwegig. Als das NIST 2000 die Kurven aus FIPS 186-2 veröffentlichte, kam jede mit einem Seed, dessen Hash den Koeffizienten b der Kurve bestimmt. Das NIST sagte, die Seeds garantierten, die Kurven seien „nachweislich zufällig“, konnte oder wollte aber nicht erklären, wie die Seeds selbst erzeugt wurden. Koblitz und Menezes schrieben ein ganzes Paper zu der Kontroverse, bezeichnenderweise mit dem Titel „A Riddle Wrapped in an Enigma“. Die beste Spur der Community war Jerry Solinas von der NSA, der sich 2015 erinnerte, der Input sei ein Hash eines humorvollen Satzes gewesen, etwa „Give Bob and Jerry a raise“. Er starb 2023, ohne dass jemand die Details ans Licht gebracht hätte.

Hier die unbequeme Wahrheit für alle Verschwörungsgläubigen, mich eingeschlossen, zumindest zeitweise: Unerklärt heißt meistens undokumentiert, nicht böswillig. Der tatsächliche Erzeugungsprozess war ein Entwickler, der ein kleines C-Programm laufen ließ, den Standard-PRNG seine Seed aus der Wanduhr ziehen ließ und den ersten Kandidaten nahm, der eine brauchbare Kurve ergab. Der veröffentlichte Seed für P-256 war Kandidat Nummer 1.842 aus einem Lauf, der am 16. August 1997 um 1:52 Uhr nachts gestartet wurde. Das ist nicht der Workflow einer Behörde, die eine zahlentheoretische Falltür einpflanzt. Das ist ein Ingenieur um ein Uhr nachts, der eine Schleife laufen lässt, bis etwas Gültiges herauskommt.

Dieses Muster habe ich in Incident-Reviews öfter gesehen, als ich zählen kann. Ein mysteriöser Konfigurationswert, eine undokumentierte Magic Number, ein Deployment-Schritt, den niemand erklären kann, und die Postmortem-Analyse zeigt, dass es ein damals vernünftiger Abkürzungsweg eines müden Ingenieurs war, nie aufgeschrieben. Die eigentliche Sünde der NSA war hier nicht, die Kurven mit einer Backdoor zu versehen. Sie hat kryptografische Konstanten an die ganze Welt ausgeliefert, ohne eine README.

Mythos 2: Die Erzeugungsmethode beweist, dass die Auswahl ehrlich war

Jetzt die Überkorrektur. Viele Kommentare diese Woche behandeln „es sind nur Zeitstempel“ als totale Rehabilitation. Ist es nicht, und die Forschenden hinter der Arbeit sagen das auch ausdrücklich. Zu wissen, wie die Kandidaten erzeugt wurden, sagt dir nichts darüber, wie die finalen Kurven ausgewählt wurden, und die Auswahl erstreckte sich über Monate, von Mai 1997 bis April 1998.

Die Belege sprechen in beide Richtungen. Im P-256-Lauf erzeugte auch Kandidat 876 eine Kurve mit Primordnung in der richtigen Größe, mit denselben Parameterkonventionen, und wurde trotzdem übergangen. Die veröffentlichte Kurve war Kandidat 1.842. Der P-224-Lauf ließ drei brauchbare Kurven aus, die ANSI-X9.62-Läufe weitere sieben. Wir sehen nur die Historie der verworfenen Kandidaten, die in den dokumentierten Läufen erreichbar war, nicht vollständig. Wollte jemand eine Kurve mit einer bestimmten seltenen Eigenschaft, könnte er prinzipiell über Zeitstempel suchen, bis eine auftaucht, und dann über den Zeitstempel einfach schweigen. „Machen und nichts sagen“ war immer eine Option.

Meine Einschätzung nach Jahren der Beobachtung von Forschung zu schwachen Kurven: Die Backdoor-Hypothese ist schwer angeschlagen, aber formal nicht tot. Die übergangenen Kandidaten sind so wenige, dass Cherry-Picking bedeuten würde, schwache Kurven seien verbreitet und leicht zu finden, was zwei Jahrzehnte öffentlicher Kryptoanalyse nicht bestätigen. Niemand hat je einen Distinguisher veröffentlicht, der diese Kurven von zufälligen unterscheidet. Aber „keine bekannte Schwäche“ und „nachweislich keine Schwäche“ sind verschiedene Aussagen, und die ehrliche Position ist die erste. Das ist genau die Lücke zwischen Spezifikation und Implementierung, die sich auf Standardisierungsebene abspielt: Die Spezifikation sagte „nachweislich zufällig“, und die Implementierung war „was die Uhr eben zeigte“.

Die Seeds wurden so erzeugt, wie ein Doktorand es machen würde: ein Standard-PRNG und die Systemuhr. Der Skandal war nie die Mathematik. Es war die fehlende Dokumentation.

Mythos 3: Schwache alte PRNGs sind harmlos, wenn du sie nur einmal benutzt

Das ist der Mythos, bei dem jeder Ingenieur, der jemals srand(time(NULL)) getippt hat, aufschrecken sollte. Der ganze fünfundzwanzigjährige Schleier des Geheimnisses existierte wegen einer Designeigenschaft von lrand48(): Der Generator verrät seine eigene Struktur. Er gibt nur die oberen 31 Bit eines 48-Bit-Zustands zurück, daher hat jedes Ausgabewort ein Null-Bit ganz oben. In 32-Bit-Wörtern geschrieben zeigen vier der zehn Seeds für die binären Kurven über zwanzig aufeinanderfolgende Wörter lauter Nullen im obersten Bit, ein Ereignis mit einer Wahrscheinlichkeit von etwa eins zu 58.000 unter einer Gleichverteilung. Die Signatur war für jeden mit freiem Auge sichtbar, der hingeschaut hat.

Ab da ist der Angriff peinlich billig. Um die Zustände der binären Kurven zu rekonstruieren, nimmst du das erste Ausgabewort, probierst die 2^17 verborgenen niederwertigen Bits durch und prüfst, ob die nächsten vier Wörter folgen. Das sind ein paar Millisekunden Rechenzeit. Bei den Primkurven haben die Seeds weniger Bits pro Ausgabe behalten, daher brauchte es für die Zustandsrekonstruktion den klassischen Angriff auf den abgeschnittenen LCG: Man modelliert das Problem als Gitterproblem und jagt es durch LLL-Basisreduktion. Wortwörtlich Lehrbuchstoff. Hast du den Zustand, lässt sich ein LCG rückwärts genauso leicht laufen wie vorwärts. Also läufst du ihn zurück, bis die Form der srand48-Initialisierung erscheint, die niederwertigen Bits gleich 0x330E, und liest den Zeitstempel ab, mit dem er initialisiert wurde.

# The whole mystery, reproduced
from datetime import datetime, timezone
def unix(when):
return int(datetime.fromisoformat(when).replace(tzinfo=timezone.utc).timestamp())
def candidate(t, n, per, shift, width):
x, out = (t << 16) | 0x330E, ""   # state set by srand48(t)
for i in range(per * n):
x = (0x5DEECE66D * x + 0xB) % 2**48   # one lrand48 step
if i >= per * (n - 1):
out += "%0*X" % (width, x >> shift)
return out
# P-256: run started 1997-08-16 01:52:34 UTC, candidate 1842
print(candidate(unix("1997-08-16 01:52:34"), 1842, 20, 40, 2))
# -> C49D360886E704936A6678E1139D26B7819F7E90  (the published NIST seed)

Die Lehre reicht über Standardisierungsgremien hinaus. Jeder „zufällig aussehende“ Wert, den du ausgibst, etwa Session-Tokens, Request-IDs, Salts oder Dateinamen, trägt den Fingerabdruck des Generators, der ihn erzeugt hat. Ist dieser Generator eine lineare Kongruenz-Engine oder ein Mersenne Twister, rekonstruieren wenige Ausgaben den internen Zustand, und alles, was du davor und danach erzeugt hast, wird vorhersagbar. Eine einzige Verwendung vor 25 Jahren, in einer Datei, die wie Rauschen aussehen sollte, wurde vollständig umgekehrt. Wenn ich Code prüfe, der nicht-kryptografische RNGs für alles verwendet, was ein Angreifer beobachten kann, zitiere ich ab jetzt diese Kriegsgeschichte.

Mythos 4: Nothing-up-my-sleeve-Zahlen waren nie der eigentliche Schutz

Die Idee der „Nothing-up-my-sleeve“-Zahlen, also Konstanten aus etwas offensichtlich Unschuldigem abzuleiten wie den Nachkommastellen von Pi, soll die Freiheitsgrade des Designers begrenzen. Kann ich zeigen, dass meine Konstante aus einem öffentlichen, starren Verfahren stammt, hatte ich keinen Spielraum, eine Falltür einzuschmuggeln. Die NIST-Seeds sind an diesem Test prozedural gescheitert: Das Verfahren war geheim, also war die Begrenzung der Freiheitsgrade unbekannt. Aber was diese Episode wirklich offenlegt, ist: Der Sleeve-Test ist schwächer, als wir uns eingeredet haben, selbst wenn er funktioniert.

Bedenke, was „nachweislich zufällig aus einem Zeitstempel“ tatsächlich bringt. Ein Zeitstempel hat für ein plausibles Fenster etwa 31 Bit Entropie. Jeder, auch der ursprüngliche Autor, kann Millionen Zeitstempel durchgehen, Millionen Kandidatenkurven erzeugen und nur die veröffentlichen, die er will, zusammen mit dem harmlos aussehenden Seed. Gäbe es Kurven mit einer geheimen Schwäche mit einer Rate von eins zu einer Million, fände das Zeitstempel-Grinding eine an einem Nachmittag. Der Seed beweist, woher die Zahl kommt, und sagt fast nichts darüber, warum genau diese gewählt wurde. Dasselbe gilt für Hash-einer-Passphrase-Schemata, weshalb das Gerücht um Solinas' Scherzsatz auch nie ganz beruhigend war.

Die modernere, stärkere Praxis ist die starre Kurvenkonstruktion: Man wählt den kleinsten Koeffizienten, der eine öffentliche Liste von Sicherheitskriterien erfüllt, und die Auswahlregeln stehen fest, bevor die Suche beginnt. Darauf beruht die Philosophie hinter Curve25519, und Dan Bernsteins Argumente zur Rigidität haben geprägt, wie die Community Kurven bewertet. Der eigentliche Schutz gegen böswillige Konstanten war nie eine nette Herleitungsgeschichte. Er besteht darin, den Suchraum zu minimieren, die Kriterien im Voraus zu veröffentlichen und genügend unabhängige Augen auf die Mathematik zu haben, damit eine versteckte Eigenschaft nicht verborgen bleiben kann. Konstanten zu auditieren heißt, den Prozess zu auditieren, der sie gefiltert hat. Deshalb sollten die offenen Fragen hier (die übergangenen Kandidaten, die ungeklärten Basispunkte für P-256 und Co., der bis heute nicht identifizierte Seed für B-163) offen im Protokoll bleiben, statt von der Feierstimmung in Vergessenheit gedrückt zu werden.

Mythos 5: LLMs reproduzieren nur, originäre Kryptoanalyse können sie nicht

Das ist der Mythos, der am meisten wehtut, weil ich eine Version davon selbst geglaubt habe. Das offene Problem lag ein Vierteljahrhundert ungelöst da, trotz eines öffentlichen Bounties von 36.864 US-Dollar und ernsthafter Aufmerksamkeit von fähigen Amateuren. Mehrere Forschende bei Anthropic hatten es selbst verfolgt, der Spur des „Hashs eines lustigen Satzes“ folgend, und standen mit leeren Händen da. Dann probierte ein internes Forschungsmodell, ohne das Gerücht vorgesetzt zu bekommen, innerhalb von knapp einer halben Stunde einen anderen Ansatz: Statt den Input eines Hashes zu raten, fragte es, welche Software die Seeds erzeugt haben könnte, stellte die Hypothese eines PRNG aus der C-Bibliothek der 1990er auf und schrieb einen Scanner, der über jeden Seed glitt und 34 Kombinationen aus Generator und Ausgabe-Slice testete. Es erkannte das Muster der Null-Bits ganz oben, führte den Gitterangriff auf die abgeschnittenen Ausgaben aus und lief die Zustände zurück bis zu Kalenderdaten.

Beachte, was dieser Workflow ist. Es ist kein Abrufen, denn kein Trainingsdokument enthielt die Antwort, weil die Antwort nirgends existierte. Es ist Hypothesenbildung plus Tool-Nutzung plus Verifikation, und genau so sieht echte kryptoanalytische Arbeit aus. Das Modell prüfte sogar seine eigene Plausibilität mitten im Lauf: Ist das eine simulierte Testumgebung? Würde so etwas Offensichtliches wirklich 25 Jahre unentdeckt bleiben? Schließt eine 160-Bit-Übereinstimmung aus einem 32-Bit-Seed einen Zufall aus? Diese Selbstskepsis ist genau das, was ich mir von einem menschlichen Analysten wünsche, und ehrlich gesagt lassen sie manche menschlichen Analysten aus. Wir haben auf dieser Seite schon seit einer Weile die Mythen geprüft, was diese Modelle tatsächlich tun, und das hier ist ein sauberer Datenpunkt: LLMs können inzwischen mehrstufiges forensisches Schlussfolgern gegen reale Artefakte ausführen, nicht nur gegen Benchmarks.

Der faire Gegenpunkt aus der Praxis betrifft die Herkunft. Das Modell hat die LCG-Zustandsrekonstruktion oder LLL nicht erfunden. Es steht auf Jahrzehnten veröffentlichter Kryptoanalyse von benannten und unbenannten Forschenden, und es kann dir nicht sagen, wessen Paper seinen Ansatz geprägt haben. Das stört mich weniger als manche andere. Der Scanner, der Verifikationscode und das Reproduktionsskript sind öffentlich; die Menschen im Team haben die Frage formuliert und das Ergebnis validiert. Die Arbeitsteilung sollte man ehrlich würdigen: Die Maschine lieferte unermüdliche Hypothesensuche, die Menschen lieferten Urteilsvermögen und Verantwortung. Das Bounty von 36.864 US-Dollar an die Internet Security Research Group zu zahlen, war ein stilvoller Abschluss.

Was sich für Sicherheitsaudits ändert

Wo steht also ein Ingenieur im Alltag? Ein paar konkrete Verschiebungen, wie ich von jetzt an Audits angehen würde. Erstens: Behandle jede Magic Constant in einem Protokoll oder einer Codebasis als forensisches Artefakt, nicht als Naturtatsache. Frag, welcher Generator sie erzeugt haben könnte, und prüfe auf strukturelle Fingerabdrücke wie verzerrte Top-Bits, LCG-korrelierte aufeinanderfolgende Wörter oder zeitstempelplausible Zustandsrekonstruktionen, bevor du „ist eben zufällig“ als Antwort akzeptierst. Die Werkzeuge dafür sind inzwischen trivial verfügbar.

Zweitens: Wenn du Konstanten veröffentlichst, veröffentliche auch den Generator. Quellcode, exakte Eingaben, exakte Umgebung. „Nachweislich zufällig“ ohne reproduzierbares Rezept kostet dich 25 Jahre Verdacht und ein Bounty auf dein Vermächtnis. Drittens: Nutze weiterhin P-256. Der Befund erhöht das Vertrauen in die Kurven, statt es zu senken, und das reale Bedrohungsmodell für elliptische Kurven ist Quantenhardware, nicht die Uhr einer Workstation von 1997. Lies aber die offenen Fragen ehrlich: ungeklärte Basispunkte und übergangene Kandidaten sind lose Enden, und reife Sicherheitsarbeit heißt, sie auf der Liste zu behalten.

Die tiefste Erkenntnis betrifft das institutionelle Gedächtnis. Jerry Solinas erinnerte sich an einen Scherz über Gehaltserhöhungen, der sich als falsch herausstellte. Die Archive lagen, in seinen eigenen Worten, wahrscheinlich auf einer Festplatte irgendwo nahe der Bundeslade. Dass wir die Wahrheit heute kennen, liegt allein daran, dass die Ausgabe selbst genug Struktur bewahrt hat, um zu gestehen. Deine Systeme schreiben gerade ihre eigenen Geständnisse, in jeder ID, jedem Token und jeder Konstante, die du ausliefert. Sorg dafür, dass sie etwas gestehen, auf das du stolz bist.