Seit mehr als 25 Jahren rätseln Fachleute, woher die NSA die Startwerte für die Verschlüsselungskurven P-256 und Co. hatte. Ein KI-Modell von Anthropic hat die Antwort nun in unter einer halben Stunde gefunden: ein gewöhnlicher Zufallsgenerator mit einem Zeitstempel aus dem Jahr 1997.
Was die KI herausgefunden hat
Die sogenannten Seeds der NIST-Kurven P-192, P-224, P-256, P-384 und P-521 sind keine Hashwerte einer geheimen Passphrase, sondern Ausgaben des C-Zufallsgenerators lrand48, der mit einem Unix-Zeitstempel gestartet wurde. Das berichtet das KI-Unternehmen Anthropic in einer am 16. Oktober veröffentlichten Forschungsarbeit. Ein internes Modell der Claude-Reihe habe die Lösung in weniger als einer halben Stunde gefunden, ohne einen Hinweis auf die vermutete Passphrase zu bekommen.
Jeder Kandidat besteht demnach aus 20 Bytes, die der Generator nacheinander ausgibt. Veröffentlicht wurde jeweils der erste Kandidat, der eine gültige Kurve ergab. Bei P-256 war das Kandidat Nummer 1842, der zugehörige Zeitstempel fällt auf den 16. August 1997. Die Zeitstempel der Primzahlkurven liegen zwischen Mai 1997 und April 1998. Vier Seeds binärer Kurven folgen offenbar demselben Muster, allerdings mit halbiertem Zeitwert.
Warum die Kurven seit Jahren Misstrauen wecken
Die US-Standardbehörde NIST nahm das Signaturverfahren ECDSA im Jahr 2000 in den Standard FIPS 186-2 auf. Die Kurven, die heute unter anderem verschlüsselte Webverbindungen absichern, enthalten einen Startwert, aus dessen Hash ein zentraler Parameter berechnet wird. Diese Startwerte lieferte der US-Geheimdienst NSA, ohne zu erklären, wie sie entstanden waren.
Das nährte über Jahre den Verdacht, die NSA könnte Kurven mit einer versteckten Schwäche ausgesucht haben. Weit verbreitet war die Erzählung, der 2023 verstorbene NSA-Mathematiker Jerry Solinas habe die Werte aus dem Hash einer humorvollen Passphrase gewonnen. Laut Anthropic war diese Geschichte falsch. Der Kryptograf Filippo Valsorda hatte für die Aufklärung eine Belohnung von 36.864 Dollar ausgesetzt, die nun an die gemeinnützige Internet Security Research Group gespendet wird.
So ging das Modell vor
Das Modell vermutete zunächst, welcher Zufallsgenerator aus den 1990er-Jahren verwendet worden sein könnte, und schrieb ein Programm, das nach dessen typischen Spuren sucht. Auffällig war, dass die obersten Bits mehrerer Seeds durchwegs null waren, ein Erkennungsmerkmal von lrand48. Bei den binären Kurven ließ sich der innere Zustand des Generators per Durchprobieren rekonstruieren.
Bei den Primzahlkurven blieben weniger Bits pro Ausgabe erhalten, hier setzte das Modell den Gitterbasisreduktions-Algorithmus LLL ein. Mit den gefundenen Zuständen ließen sich alle 160 Bits der jeweiligen Seeds exakt reproduzieren. Ein Zufallstreffer sei damit ausgeschlossen, schreiben die zehn Autorinnen und Autoren der Arbeit, die den Code zum Nachrechnen veröffentlicht haben.
Was das für die Sicherheit bedeutet
Ausdrücklich halten die Forschenden fest, dass es sich nicht um einen kryptografischen Bruch, einen neuen Angriff oder eine Schwäche der ECDSA-Kurven handelt. Im Gegenteil: Weil die Startwerte aus einem einfachen, öffentlich nachvollziehbaren Verfahren stammen, werde eine absichtlich eingebaute Hintertür deutlich unwahrscheinlicher. Die Parameter seien vertrauenswürdig.
Bemerkenswert ist der Fall auch, weil er zeigt, wie KI-Modelle bei forensischer Analyse helfen können. Die Kombination aus Hypothesenbildung, Programmieren und mathematischen Verfahren, für die Fachleute sonst viel Zeit brauchen, lief hier weitgehend automatisiert ab. Die Ergebnisse lassen sich unabhängig überprüfen, weil die Arbeit alle Zeitstempel und Kandidatennummern auflistet.
Welche Fragen offen bleiben
Ganz gelöst ist das Rätsel nicht. Der Seed der Kurve B-163 bleibt unerklärt, ebenso die Basispunkte von P-224, P-256, P-384 und P-521. Die Basispunkte von P-192 und fünf weiteren Beispielkurven stammen dagegen aus dem Zufallsgenerator der Rechenbibliothek FreeLIP des Mathematikers Arjen Lenstra.
Offen ist auch, warum einzelne gültige Kandidaten übersprungen wurden, bei P-256 etwa Kandidat 876. Ob das Absicht war und nach welchen Kriterien ausgewählt wurde, wissen die Autorinnen und Autoren nicht. Es gebe zudem keinen Hinweis darauf, wie oft das Programm damals insgesamt laufen gelassen wurde.