Google DeepMind hat am 6. November zwei Ergebnisse vorgelegt, die beide ausschließlich 1024-Bit-RSA betreffen – eine Schlüssellänge, die Standardsetzer vor mehr als einem Jahrzehnt für neue Signaturen ausgemustert haben, die aber in alter Hardware, langlebigen Zertifikaten und eingebetteten Systemen weiterlebt. Geleitet wurde die Arbeit von Krishnamurthy (Dj) Dvijotham und Abhradeep Thakurta, mit Nadia Heninger (UC San Diego) und Emmanuel Thomé (Inria) als Mitautoren. Kohli, DeepMinds Vizepräsident für Wissenschaft, sagt, die Ergebnisse seien in Wochen statt Jahren erreicht worden.

Ergebnis eins: Padding schützt weniger als gedacht

RSA-Signaturen werden nicht über einen rohen Hash gebildet. Das Verfahren packt den Nachrichten-Hash zuerst in eine feste Padding-Struktur, und diese Starrheit gilt seit langem als Schutz gegen Fälschung. Die Agenten fanden laut DeepMind, dass dieser Schutz schnell verfällt, sobald ein Angreifer einen großen Teil des signierten Blocks kontrolliert: Ab etwa der Hälfte trägt das Padding keinen nennenswerten Schutz mehr, und eine Fälschung wird ungefähr so schwer wie bei einem System ohne Padding.

Getestet wurde in einer Sandbox gegen einen 1024-Bit-Benchmarkschlüssel, der bereits Gegenstand einer akademischen Studie war. Die von der KI erzeugte Implementierung reproduzierte das Ergebnis mit 3,5-mal weniger CPU-Zeit und mit weniger als einem Tausendstel des Aufwands, den die Faktorisierung des Schlüssels selbst kosten würde. Die Referenz ist die im September veröffentlichte Arbeit von Laura Shea, Miro Haller, Adam Suhl, Nadia Heninger und Emmanuel Thomé, die Signaturen über Black-Box-API-Aufrufe aus einem Hardware-Sicherheitsmodul fälschten – mit 1.380 CPU-Kernjahren über fünf Kalendermonate und 2^32 Abfragen an ein Signatur-Orakel. Eine Reduktion um Faktor 3,5 brächte dieselbe Aufgabe auf rund 390 Kernjahre.

Für den schwierigeren Fall – der Angreifer kontrolliert nur einen kleinen Teil des Blocks, etwa einen 32-Byte-Digest – will das Team einen neuen Algorithmus gefunden haben, der schätzungsweise rund 1.600-mal besser sei als die bisher beste bekannte Methode. Diese Zahl ist eine theoretische Schätzung, die betroffenen Padding-Verfahren nennt DeepMind nicht, und ein vollständiges Paper zum Signatur-Ergebnis lag bei Redaktionsschluss nicht öffentlich vor.

Ergebnis zwei: eine "Fan-Fabrik" für viele Schlüssel

Das zweite Ergebnis steht in einem Working Paper vom 5. November: "Fan Factories: Multiple Number Fields in Factorization Factories and Batch NFS". Es baut auf Don Coppersmiths Idee der Faktorisierungsfabrik von 1993 auf. Eine Fabrik lohnt sich, wenn viele Zahlen derselben Größe zu faktorisieren sind: Man zahlt einmal für eine große Vorberechnung und danach je Ziel weniger.

Die DeepMind-Konstruktion gibt jeder Zielzahl einen eigenen "Fächer" von Zahlkörpern, alle gespeist aus einer gemeinsam vorberechneten rationalen Seite, und leitet daraus die minimalen Kosten pro Zahl für jedes Vorberechnungsbudget ab. Bei einem Budget von einem GNFS-Lauf sinken die Kosten für jeden weiteren 1024-Bit-Schlüssel auf etwa 1/58 eines GNFS-Laufs – in der Notation L[c] also L[1,793] gegen L[1,902] für das Multiple Number Field Sieve, die beste Batch-Methode seit 1993. Das sind rund 30-mal weniger pro Schlüssel. Rechnet man die Vorberechnung mit, ist die Fabrik bereits ab drei Zielen günstiger als MNFS; der Vorteil wächst mit der Batch-Größe und nähert sich dem 30-Faktor.

Wie die Agenten eingesetzt wurden

Das Paper beschreibt einen Zwei-Agenten-Aufbau: ein Modell erzeugt die Beweise, ein zweites prüft sie. Die algebraischen Identitäten und exakten Machbarkeitszeugen der Hauptsätze sind im Lean-4-Proof-Assistenten maschinell verifiziert; die analytischen Argumente, die die Optimierung abschließen, wurden numerisch geprüft. Genau diese Aufteilung macht das Ergebnis für Außenstehende prüfbar – bei maschinell erzeugten Behauptungen ist die Verifikation der eigentliche Flaschenhals, nicht die Idee.

Die Grenzen sind Teil des Ergebnisses

Das Paper lässt niedrigere Terme weg, stützt sich auf Standard-Heuristiken zur Glattheit von Zahlen und ein einfaches Kostenmodell. Der Speicher ist ein zweites Hindernis: Bei einem Budget von einem GNFS-Lauf hält die gespeicherte Tabelle Größenordnung L[1,66] Paare. Keine Fan-Fabrik wurde gebaut, und ab welcher Schlüssellänge sie eine gut abgestimmte GNFS-Implementierung praktisch schlägt, ist offen. Mit unbegrenzter Vorberechnung bleibt Coppersmiths ursprüngliche Fabrik optimal – die theoretische Untergrenze sinkt also nicht.

Und was heißt das für 2048 Bit? DeepMind und das Paper sagen es beide deutlich: moderne Schlüssel ab 2048 Bit sind nicht bedroht. NIST erlaubt seit Ende 2013 keine kürzeren Schlüssel für neue Signaturen.

Was Organisationen trotzdem tun sollten

- Betreiber von Signaturdiensten und HSMs: Wo 1024-Bit-Signaturen über eine API erreichbar sind, sollte teilweise Angreiferkontrolle über den signierten Block als Fälschungsrisiko gelten. Rohe oder schwach gepolsterte Signaturoperationen einschränken und Schlüssel rotieren. - Wer große Bestände alter Schlüssel betreibt: Bei Batch-Angriffen zählt das Inventar, nicht der einzelne Schlüssel. Eingebettete Geräte, ältere Smartcards, langlebige Code-Signing-Roots, archivierte Zertifikate. - Wer die Post-Quanten-Migration plant: Ein weiterer dokumentierter Grund, 1024-Bit-RSA jetzt auszumustern und RSA-2048 auf dem Post-Quanten-Zeitplan einzuplanen.

Das eigentliche Signal ist nicht, dass RSA gebrochen wurde – das wurde es nicht. Es ist, dass ein Team aus Menschen und Agenten in Wochen Kryptanalyse vorangebracht hat, deren Prüfung nun öffentlich nachvollziehbar ist.