KI-Agenten, die unter menschlicher Aufsicht arbeiten, ermöglichten es Google DeepMind, zwei Wege zu identifizieren, um die Angriffskosten für 1024-Bit-RSA-Kryptosysteme zu senken. Diese Arbeiten, die mit Kryptographen der UC San Diego und des Inria durchgeführt wurden, zeigen, dass Angriffe auf das veraltete RSA-1024 weniger Rechenleistung erfordern als bisher angenommen.
- Google DeepMind hat mit KI-Agenten zwei Wege gefunden, um 1024-Bit-RSA billiger anzugreifen.
- Das Padding bietet bei digitalen Signaturen keinen Schutz mehr, wenn der Angreifer etwa die Hälfte des Blocks kontrolliert.
- Im Test sank der Rechenaufwand einer Fälschung auf 391 statt 1.380 CPU-Jahre, der Schlüssel wurde jedoch nicht faktorisiert.
- Pushmeet Kohli betont, dass moderne Verschlüsselung mit 2048 Bit oder mehr sicher bleibt.
RSA ist ein Public-Key-Verschlüsselungssystem, dessen Sicherheit auf der Schwierigkeit beruht, eine große Zahl in Primfaktoren zu zerlegen. Pushmeet Kohli, Vizepräsident von Google DeepMind und Chief Scientist von Google Cloud, möchte die Tragweite dieser Ergebnisse jedoch relativieren: «In der Praxis betreffen diese Ergebnisse nur veraltete 1024-Bit-RSA-Systeme, und moderne Verschlüsselungsprotokolle, die fast durchgängig Schlüssel mit 2048 Bit oder mehr verwenden, bleiben sicher.»
Digitale Signaturen und Padding
Die erste Entdeckung betrifft digitale Signaturen und das Padding, diese vordefinierten Daten, die viele Signaturstandards zu einer Nachricht hinzufügen, um sie auf eine feste Blockgröße zu bringen. Dieser Mechanismus war dafür bekannt, die Fälschung zu erschweren, aber seine Wirksamkeit gegenüber einem Angreifer, der wählen kann, was signiert wird, war unklar. DeepMind hat festgestellt, dass alles davon abhängt, welchen Anteil des signierten Blocks der Angreifer kontrolliert. Wie Pushmeet Kohli erklärt: «Sobald sie etwa die Hälfte des Blocks oder mehr kontrollieren, bietet das Padding keinen Schutz mehr.»
Laut dem wissenschaftlichen Artikel, der diese Arbeiten begleitet, betrifft dies das PKCS#1 v1.5-Format, das von der PKCS#11-Signaturschnittstelle kryptografischer Geräte wie Hardware-Sicherheitsmodulen (HSM) verwendet wird.
In einem Test in einer isolierten Umgebung ließen die Agenten einen bereits in einer akademischen Studie veröffentlichten Fälschungsangriff auf denselben 1024-Bit-Schlüssel erneut laufen. Die Prozessor-Rechenzeit wurde um das 3,5-fache reduziert. Die erste Fälschung erforderte 391 CPU-Jahre, gegenüber 1.380 in der Originalstudie.
Zwei KI-Agenten entwarfen, führten aus und korrigierten die Fälschungsberechnung in weniger als vier Tagen, mit etwa 20 Nachrichten des menschlichen Forschers, hauptsächlich Zustimmungen. Der Schlüssel wurde nicht faktorisiert, eine Operation, die die Quelle auf 500.000 bis 1 Million CPU-Jahre schätzt. Wenn der Angreifer einen kleineren Teil des Blocks kontrolliert, beispielsweise einen 32-Byte-Hash, ist die Fälschung schwieriger. DeepMind gibt jedoch an, einen Algorithmus gefunden zu haben, der nach seinen theoretischen Schätzungen etwa 1.600-mal besser ist als die bisher effektivste Methode gegen 1024-Bit-Schlüssel.
Faktorisierung mehrerer Schlüssel
Die zweite Entdeckung betrifft die Faktorisierung vieler RSA-Schlüssel gleicher Größe. Ein Angreifer kann dann die Kosten einer einzigen großen Anfangskalkulation auf alle diese Schlüssel verteilen. Die DeepMind-Agenten entwickelten einen Algorithmus, der im Durchschnitt die Faktorisierung jedes zusätzlichen 1024-Bit-Schlüssels etwa 30-mal günstiger macht als der bisher beste Ansatz. Diese theoretische Schätzung setzt jedoch eine Anfangskalkulation voraus, die so teuer ist wie die Faktorisierung eines einzelnen Schlüssels, und die Methode wurde nicht implementiert.
Die Forscher betonen, dass der Angriff auf Signaturen nicht die Wiederherstellung des privaten Schlüssels ermöglicht. Er erfordert im Vorfeld etwa 4 Milliarden Signaturanfragen und funktioniert nicht gegen Geräte, die Nachrichten intern hashen. «Zusammen zeigen diese Ergebnisse, dass wir in einer neuen Ära der KI-gestützten Mathematik und Berechnung die kryptografische Schwierigkeit nicht als feste Annahme betrachten können», schließt Pushmeet Kohli. Er fügt hinzu: «Die rigorose Nutzung von The AI / news, um unsere früheren Annahmen zu testen, wird sicherstellen, dass moderne Verschlüsselung sicher bleibt.»
