Der größte jemals öffentlich gebrochene RSA-Schlüssel wurde in den Lücken zwischen anderen Jobs gebrochen. Stephen Weis, Ingenieur bei Anthropic, hat am Samstag zwei 448-Bit-Primzahlen veröffentlicht. Multipliziert man sie, erhält man RSA-896, eine 270-stellige Challenge-Zahl, die RSA Security am 23. Mai 2001 mit einem Preisgeld von 75.000 US-Dollar ausgeschrieben hat. Weis ließ Claude CADO-NFS auf GPUs portieren und als niedrig priorisierte Aufgabe auf freier Kapazität einplanen. Zehn Tage, in der Spitze 2.048 GPUs, rund 30 GPU-Jahre. Ich habe die Faktoren multipliziert. Sie stimmen.
Heute, zwei Tage später, verschiebt NIST jedes FIPS-140-2-Zertifikat auf die Historical-Liste.
FIPS 140-2 wurde am 25. Mai 2001 unterzeichnet. Die Zahl und der Standard kamen zwei Tage auseinander zur Welt und gingen fünfundzwanzig Jahre später zwei Tage auseinander in die Historie. Nur eines dieser Daten stand in einem Kalender.
Freie Rechenzeit
1977 druckte Martin Gardner einen 129-stelligen RSA-Modulus in Scientific American ab, und Ron Rivest schätzte 40 Billiarden Jahre für die Faktorisierung. Er fiel 1994. Sechshundert Freiwillige spendeten Leerlaufzeit auf 1.600 Maschinen, zwei davon Faxgeräte, und schickten ihre Ergebnisse an einen Koordinator. Der Klartext lautete „The Magic Words are Squeamish Ossifrage.“ FIPS 140-1 erschien im selben Jahr.
Faktorisierungsrekorde wurden schon immer auf Resten aufgestellt. Was sich ändert, ist die Größe der Reste. 1994 waren es Workstations über Nacht. 2026 sind es zweitausend Beschleuniger, die ein Scheduler zwischen Trainingsläufen sonst dunkel ließe. Niemand hat Hardware gekauft, um RSA-896 zu brechen. Gemietet hat auch niemand welche.
Die Mathematik hat sich nicht bewegt
Weis sagt ausdrücklich, dass das General Number Field Sieve nicht schneller geworden ist. Derselbe Algorithmus wie in den 1990ern, dieselbe quelloffene Implementierung, die die letzten Rekorde aufgestellt hat.
Bewegt hat sich die Arbeit. RSA-250 mit 829 Bit hielt den Rekord von Februar 2020 bis zu diesem Monat. Sechseinhalb Jahre. Dann faktorisierte Eric Lu bei Cognition am 3. September RSA-260 mit 862 Bit, mit einem Schwarm von Devin-Agenten, der einen Lattice-Siever für GPUs baute. Sechzehn Tage später nahm Weis 896, mit einem anderen Agenten bei einem anderen Unternehmen. Eine optimierte CPU-Forschungscodebasis auf GPUs umzuschreiben und über eine Flotte hinweg zu betreuen, erforderte früher eine Handvoll Spezialisten, die einander meist kannten. Diese Knappheit war eine Sicherheitsmaßnahme, die niemand aufgeschrieben hat. Sie ist weg.
1024
Rechnet man die GNFS-Komplexitätsschätzung von 896 Bit auf 1024 hoch, wächst der Aufwand um etwa den Faktor 30. Sagen wir 900 GPU-Jahre. Lus Aufschrieb beziffert RSA-1024 auf rund 30 Millionen US-Dollar pro Schlüssel für einen Hyperscaler oder ein führendes Labor, und er erwartet, dass dieser Wert sinkt. Ein Labor mit hunderttausend GPUs produziert 900 ungenutzte GPU-Jahre als Rundungsfehler. Die Phase der linearen Algebra verteilt sich nicht so über eine Flotte wie das Sieben, diese Rechnung ist also eine Untergrenze für die Laufzeit und keine Prognose. Es bleibt eine Zahl, die in eine Budgetzeile passt.
2015 bezifferten die Logjam-Autoren einen Bruch von 1024-Bit-Diffie-Hellman auf einige hundert Millionen Dollar Spezialhardware, um eine Primzahl pro Jahr zu knacken. Sie nannten das für einen Nationalstaat plausibel und verwiesen auf das NSA-Budget. Das Argument setzte einen Staat voraus. Weis schreibt nun, RSA-1024 sei „für viele Akteure mit Flotten von GPUs auf Rechenzentrumsniveau angreifbar“. Viele Akteure.
RSA-2048 ist etwa eine Milliarde Mal schwerer als 1024. Keine Menge an Leerlaufzeit schließt diese Lücke, und niemand von Rang behauptet etwas anderes.
Dreizehn Jahre Vorwarnung
NIST hat 1024-Bit-RSA zum Signieren Ende 2013 untersagt. Das sind dreizehn Jahre Vorsprung vor einem öffentlichen Bruch bei 896. Das Gremium hat das Datum richtig gesetzt, mit Reserve.
Die Schlüssel sind weiterhin da. SP 800-131A führt die Signaturprüfung mit 1024 Bit als „Legacy Use“, weil alte Firmware und alte Dokumente weiterhin geprüft werden müssen. RFC 8301 setzt die DKIM-Untergrenze weiterhin bei 1024 Bit, und die großen Mailbox-Anbieter prüfen sie weiterhin. Der Zone-Signing-Key der DNSSEC-Root lag bis 2016 bei 1024 Bit. Boot-ROMs tragen öffentliche 1024-Bit-Schlüssel, die nie neu geflasht werden. Jede Sitzung, die in den Jahren aufgezeichnet wurde, in denen 1024 der Standard war, liegt dort, wo sie abgelegt wurde.
Das meiste auf dieser Liste ist Signaturprüfung, was bedeutet, dass nichts im Voraus aufgezeichnet werden musste. Marin Ivezic nennt dieses Muster in seinem Text zu Post-Quanten-DNSSEC Trust Now, Forge Later: Wer einen Signaturschlüssel gewinnt, kann von diesem Tag an alles fälschen, wofür dieser Schlüssel bürgt. Die klassische Variante braucht keinen Quantencomputer, nur ungenutzte GPUs.
Genau das bedeutet „Historical“ auch in der CMVP-Datenbank. Behörden sollen das Modul für neue Systeme nicht mehr beschaffen. In den alten läuft es weiter. Der Status ändert sich in einer Tabelle in Gaithersburg, und im Rack ändert sich nichts. Anbieter, die von der Liste herunterwollen, treffen auf eine Prüfschlange, in der allein der Anteil des CMVP im Schnitt 542 Tage dauert.
Zwei Kalender
Verteidiger arbeiten nach einem veröffentlichten Kalender. FIPS 140-2 hatte sein Enddatum Jahre im Voraus festgelegt. CNSA 2.0 nennt 2027, 2030, 2035. Der Entwurf des NIST-Übergangsplans stuft RSA-2048 nach 2030 als veraltet ein und untersagt es nach 2035. Das sind ausgehandelte Daten, gesetzt von Menschen, die Beschaffungszyklen gegen Risiko abwägen, und sie sind vernünftig.
Angreifer arbeiten nach Kapazität. Ihr Datum ist der Tag, an dem die Reste groß genug sind. Lu und Weis haben ihres im Nachhinein bekannt gegeben, als Zahlen auf einer Webseite. Nichts verpflichtet den Nächsten zur Veröffentlichung. Bei 1024 lag der Kalender der Verteidiger mehr als ein Jahrzehnt vor dem der Angreifer, und für keinen Schlüssel, den niemand gesucht hat, hat das eine Rolle gespielt.
Die Post-Quanten-Daten werden genauso funktionieren. Eine Frist verschiebt ein Zertifikat auf eine Liste. Einen Schlüssel verschiebt sie nicht.
Ein Schlüssel weiß nicht, dass er für veraltet erklärt wurde.