Zwei Mathematiker knackten SIKE-Post-Quanten-Krypto in einer Stunde auf einem einzigen PC

Im August 2022, wenige Wochen nachdem NIST vier Post-Quanten-Verschlüsselungsalgorithmen ausgewählt hatte, die RSA und Diffie-Hellman letztlich ersetzen sollen, veröffentlichten Forscher der Forschungsgruppe Computer Security and Industrial Cryptography der KU Leuven „An Efficient Key Recovery Attack on SIDH“ – eine Technik, die die Schlüssel, die SIKE-geschützte Transaktionen sichern, mit komplexer Mathematik und einem einzigen herkömmlichen PC in etwa einer Stunde rekonstruiert. Wouter Castryck und Thomas Decru, die Autoren des Papiers, kamen für eine Prämie von 50.000 US-Dollar von Microsoft in Frage.

SIKE – Supersingular Isogeny Key Encapsulation – war einer von vier zusätzlichen Algorithmen, die NIST als mögliche Backup-Optionen weiterverfolgte, und galt als widerstandsfähig gegen Quantencomputer, weil er Geheimnisse in einem supersingulären Isogenie-Graphen kodiert – eine Konstruktion, die lange als elegant schwer galt. Der neue Angriff zeigt, dass sein Eckpfeiler-Protokoll SIDH (Supersingular Isogeny Diffie-Hellman) anfällig für Glue-and-Split ist, ein Theorem, das der Mathematiker Ernst Kani 1997 bewies, sowie für Werkzeuge von Howe, Leprévost und Poonen aus dem Jahr 2000, aufbauend auf dem bekannten adaptiven GPST-Angriff.

Die Bedeutung war unmittelbar: SIKE war wahrscheinlich aus dem Rennen um die Standardisierung, während die vier Algorithmen, die NIST als Standards ausgewählt hatte – auf völlig anderer Mathematik aufgebaut – nicht betroffen waren. David Jao, Professor an der University of Waterloo und Miterfinder von SIKE, nannte die Schwäche „eindeutig einen schweren Schlag“ und den Angriff „wirklich unerwartet“.

SIDH lieferte stets Hilfspunkte mit einem bekannten Isogenie-Grad mit; ein Theorem von 1997 (Glue-and-Split) verwandelt diese Bequemlichkeit für den Designer in eine Schlüssel-Rekonstruktionsmaschine.

Der Angriff nutzte Mathematik, die ein Vierteljahrhundert alt war und seit 1997 offen vor aller Augen lag.

Er benötigte keinen Quantencomputer – die Bedrohung, für die SIKE entworfen wurde –, nur einen Kern und eine Stunde.

Der Fehler war struktureller Natur: Hilfspunkte und ein bekannter Isogenie-Grad waren in das Design des Protokolls eingebaut.

Das Ergebnis ordnete einen staatlichen Standardisierungswettbewerb innerhalb weniger Tage nach der Veröffentlichung neu.

Bequemlichkeiten, die in ein Protokoll hineinkonstruiert werden, sind latente Schwachstellen: Die Hilfsdaten, die ein Schema für die Benutzbarkeit preisgibt, können genau der Ansatzpunkt sein, den ein Angreifer braucht.

SIKE, ein NIST-Alternativkandidat, wurde faktisch aus der Betrachtung ausgeschlossen; die vier bereits ausgewählten Post-Quanten-Standards beruhten auf anderer Mathematik und blieben unberührt. Die Forscher konnten Microsofts Kopfgeld von 50.000 US-Dollar einstreichen, und SIKE-Miterfinder David Jao bestätigte öffentlich die Schwere des Angriffs.