Seit 25 Jahren fragt die Kryptografie-Szene, woher die Seeds der NIST-Kurven stammen. Die NSA hatte sie für den Signaturstandard FIPS 186-2 geliefert, kommentarlos. Bei P-256 steht dort C49D3608 86E70493 6A6678E1 139D26B7 819F7E90, und niemand konnte sagen, warum ausgerechnet diese Zahl. Am 16. Oktober hat Anthropic die Auflösung veröffentlicht. Es sind Zeitstempel.
Kein Hash, sondern ein Zufallsgenerator von 1997
Im Oktober fragte ein neugieriger Anthropic-Mitarbeiter ein internes Forschungsmodell, wie die Seeds entstanden sein könnten. Den kursierenden Hinweis gab er bewusst nicht mit. Keine halbe Stunde später hatte Claude die Herkunft der Seeds von P-192, P-224, P-256, P-384 und P-521.
Dahinter steckt lrand48, der Zufallsgenerator der C-Bibliothek, initialisiert mit einem Unix-Zeitstempel. Das Programm zog 20 Bytes je Kandidat und lief weiter, bis ein brauchbarer Wert herauskam. Bei P-256 war das Kandidat 1842. Alle zehn rekonstruierten Startzeiten der Prime-Kurven liegen zwischen Mai 1997 und April 1998.
Die bis dahin beste Erzählung war eine andere. Jerry Solinas, lange bei der NSA, hatte 2015 von einem Scherzsatz berichtet, aus dem die Seeds gehasht worden seien, etwa „Give Bob and Jerry a raise“. Solinas starb 2023, Unterlagen fanden sich nicht. Mehrere Anthropic-Leute hatten dieser Spur vergeblich nachgejagt. Sie war falsch.
Der Weg führte über ein Gitterproblem
Claude probierte es anders herum und fragte, welchen Generator die Software von damals wohl benutzt hat. Alte Generatoren sind schwach genug, dass man ihre Ausgabe wiedererkennt. Ein Scanner verglich die Seeds bitweise gegen 34 Kombinationen aus Generator und Ausschnitt.
Dann fiel ein Muster auf: Bei vier der zehn Seeds ist in allen 32-Bit-Wörtern das oberste Bit null. Zufällig passiert das mit einer Wahrscheinlichkeit von 1 zu 5810. Genau so verhält sich lrand48, das nur 31 der 48 Zustandsbits zurückgibt. Für die übrigen Seeds war mehr nötig, weil weniger Bits sichtbar blieben: Den Zustand eines abgeschnittenen linearen Kongruenzgenerators zurückzurechnen ist ein Gitterproblem, und das löst der LLL-Algorithmus. Alle zehn Prime-Kurven-Seeds folgten demselben Muster, lrand48() >> 23.
Nebenbei fand Claude die Herkunft einiger Basispunkte, die bisher niemand erklärt hatte. Sie stammen aus dem Generator von FreeLIP, Arjen Lenstras Bibliothek für lange Zahlen. Die Basispunkte von P-224, P-256, P-384 und P-521 bleiben offen, ebenso der fünfte Binärseed B-163.
Das Ergebnis spricht für die Kurven
Ein Bruch ist das nicht, im Gegenteil. Wer jahrelang eine Hintertür in den NIST-Parametern vermutet hat, muss sich jetzt vorstellen, dass die NSA sie über eine Uhr und einen simplen Generator eingebaut hat, den heute jeder nachrechnen kann. Viel Platz für Manipulation bleibt da nicht.
Interessanter finde ich den Weg dorthin. Das Rätsel lag 25 Jahre offen, Leute mit mehr Kryptografie-Wissen als ich haben sich daran versucht, und am Ende war es eine Mustererkennung plus Gitterrechnung in einer halben Stunde. Filippo Valsorda, der die Bounty ausgelobt hatte, hat den Algorithmus in Go nachgebaut und bestätigt. Die 36.864 Dollar gehen an die Internet Security Research Group, die hinter Let’s Encrypt steht.
Wie gut Claude mit ähnlich strukturierten Problemen umgeht, zeigt übrigens die Arbeit an Quantenschaltkreisen, die Anthropic am selben Tag veröffentlicht hat.