SIDH und SIKE: Design und Kryptoanalyse

Supersingular Isogeny Diffie-Hellman (SIDH), 2011 von Jao und De Feo vorgeschlagen, ist ein Public-Key-Austauschprotokoll, das dem Diffie-Hellman-Verfahren ähnelt, jedoch Isogenien auf supersingulären elliptischen Kurven verwendet. Beide Parteien beginnen mit derselben supersingulären Kurve E über Fp2. Alice berechnet eine geheime Isogenie phi_A: E -> E_A (zufälliger Kern in der 2^a-Torsion), veröffentlicht E_A sowie die Bilder von Bobs Torsionsgeneratoren unter phi_A. Bob berechnet phi_B: E -> E_B (zufälliger Kern in der 3^b-Torsion), veröffentlicht E_B sowie die Bilder von Alices Torsionsgeneratoren unter phi_B. Alice verwendet die von Bob veröffentlichten Daten, um phi_A': E_B -> E_AB zu berechnen; Bob berechnet phi_B': E_A -> E_AB. Beide erhalten j(E_AB) als gemeinsamen geheimen Wert.

Die spezielle Primzahlform p = 2^a * 3^b * f - 1 (f ist ein kleiner Kofaktor für die Primzahligkeit) stellt sicher, dass die Kurve E über Fp2 die erforderliche Torsionsstruktur besitzt. Für SIKEp434 (NIST-Stufe 1, Post-Quanten-Sicherheit von 128 Bit) gilt: p = 2^216 * 3^137 - 1, a = 216, b = 137. Das bedeutet, dass Alice eine Kette aus 216 Schritten von 2-Isogenien durchläuft und Bob 137 Schritte von 3-Isogenien. Schlüsselgrößen: Alices öffentlicher Schlüssel besteht aus E_A sowie zwei Fp2-Punkten (phi_A(P_B), phi_A(Q_B)) = 3 * 2 * 54 = 324 Byte. SIKEp751 zielt auf eine klassische Sicherheit von 192 Bit beziehungsweise eine Quanten-Sicherheit von 128 Bit ab und besitzt 564 Byte große öffentliche Schlüssel. Dies sind die kleinsten öffentlichen Schlüssel aller NIST-PQC-Kandidaten – allerdings um den Preis, dass das Verfahren 100- bis 1000-mal langsamer ist.

SIKE (Supersingular Isogeny Key Encapsulation) ist ein IND-CCA2-sicheres KEM, das mithilfe der Fujisaki-Okamoto-Transformation aus SIDH aufgebaut ist. SIKE.Encaps: Wählen Sie eine zufällige Nachricht m, berechnen Sie (c0 = SIDH public key with seed m, c1 = H2(m) XOR pk) und senden Sie (c0, c1). SIKE.Decaps: Stellen Sie m mithilfe des geheimen Schlüssels aus c0 wieder her, überprüfen Sie c1, berechnen Sie (c0, c1) zur Konsistenzprüfung erneut und geben Sie K = H3(m, c0) aus. Die FO-Transformation wandelt den CPA-sicheren SIDH-Austausch in ein CCA2-sicheres KEM um. SIKE nahm an allen vier Runden des NIST-PQC-Wettbewerbs (2017–2022) teil und überstand umfangreiche kryptanalytische Untersuchungen – bis im Juli 2022 ein verheerender klassischer Angriff entdeckt wurde.

Von 2011 bis 2022 widerstand SIDH erheblichen kryptanalytischen Bemühungen. Die besten bekannten Angriffe auf SIDH waren: (1) Der generische SSIP-Algorithmus: klassisch O(p^{1/4}), quantenbasiert O(p^{1/6}) unter Verwendung von Tanis Algorithmus. (2) Meet-in-the-Middle auf dem Isogeniepfad: klassisch O(p^{1/4}), also genauso wie SSIP. (3) Polynomielle Algorithmen für spezifische strukturelle Angriffe (van Oorschot-Wiener): auf SIDH nicht anwendbar. Dutzende Veröffentlichungen analysierten die Sicherheit von SIDH, und in 11 Jahren wurde kein polynomieller klassischer oder quantenbasierter Angriff gefunden. Diese Bilanz machte SIKE zu einem glaubwürdigen NIST-Finalisten. Der letztendliche Bruch erfolgte nicht durch einen direkten Angriff auf SSIP, sondern durch die Ausnutzung der zusätzlichen Informationen über Torsionspunkte von SIDH.

Am 30. Juli 2022 veröffentlichten Wouter Castryck und Thomas Decru ein Preprint, das einen klassischen Angriff mit polynomialer Laufzeit auf SIDH zeigte. Der Angriff nutzt die zusätzlichen Informationen in SIDHs zusätzlichen Torsionspunkten phi_A(P_B), phi_A(Q_B): Diese Informationen legen im Wesentlichen die Wirkung von phi_A auf der 3^b-Torsionsuntergruppe offen. Zusammen mit der Bildkurve E_A ermöglicht dies, den Kern von phi_A (und damit phi_A selbst) mithilfe von Verfahren aus der Theorie elliptischer Kurven mit komplexer Multiplikation und von Richelot-Isogenien zu rekonstruieren. Der Angriff lief bei SIKEp434 auf einem Laptop 62 Minuten – bei einem Parametersatz, der eigentlich eine Post-Quanten-Sicherheit von 128 Bit bieten sollte. Innerhalb weniger Tage bestätigten unabhängige Forschende den Angriff und erweiterten ihn auf alle SIDH-Parameter.

Das Design von SIDH erforderte, dass beide Parteien die Bilder der Torsionsbasispunkte der jeweils anderen Partei unter ihrer geheimen Isogenie veröffentlichten. Dies war für das Funktionieren des Protokolls notwendig: Ohne phi_A(P_B) und phi_A(Q_B) hätte Bob seine Isogenie nicht auf Alices Kurve übertragen können, um den gemeinsamen geheimen Wert zu berechnen. Diese zusätzlichen Informationen – die die auf die 3^b-Torsion beschränkte Wirkung von phi_A offenlegen – erwiesen sich jedoch als katastrophal umfangreicher als erwartet. Der Angriff von Castryck und Decru verwendet Kurven vom Geschlecht 2 (Richelot-Isogenien), um das Problem auf Objekte höheren Geschlechts zu heben, bei denen die eingeschränkte Wirkung phi_A vollständig bestimmt. Dieses Leck ist strukturell in SIDH verankert und kann nicht behoben werden, ohne das grundlegende Design des Protokolls zu ändern.

Am 5. Juli 2022, also vor dem Angriff von Castryck und Decru, hatte NIST seine ursprüngliche Auswahl für die PQC-Standardisierung bekannt gegeben: ML-KEM (Kyber), ML-DSA (Dilithium), SLH-DSA (SPHINCS+) und FN-DSA (Falcon) – SIKE war nicht darunter, sondern befand sich in einer zweiten Bewertungsrunde. Der Angriff von Castryck und Decru im Juli 2022 veranlasste NIST, SIKE vollständig aus dem Auswahlverfahren zu streichen. NIST erklärte: "SIKE is no longer under consideration for standardization." Dies war die spektakulärste kryptanalytische Entwicklung im NIST-PQC-Wettbewerb und zeigte, dass selbst ein Verfahren, das 11 Jahre lang analysiert worden war, durch eine grundlegend neue mathematische Erkenntnis gebrochen werden konnte.

Innerhalb einer Woche nach Castryck und Decru veröffentlichten Thomas Decru und Luciano Maino unabhängig voneinander und später Damien Robert weitere Verbesserungen. Roberts Variante des Angriffs nutzt dieselbe Erkenntnis, berechnet jedoch den Endomorphismenring von E_A, statt den Isogeniekern direkt zu berechnen, und lässt sich mathematisch wohl einfacher beschreiben. Diese schnellen unabhängigen Wiederentdeckungen bestätigten, dass der Angriff von Castryck und Decru eine grundlegende strukturelle Schwäche und keinen obskuren Trick aufgedeckt hatte. Die Geschwindigkeit der folgenden Veröffentlichungen spiegelte außerdem wider, dass viele Forschende die Schwachstelle durch den Torsionspunkt-Leakage von SIDH bereits als möglichen Angriffsvektor untersucht hatten. Sie wussten, dass es sich um eine ungewöhnliche Informationspreisgabe handelte, konnten sie jedoch erst ausnutzen, als Castryck und Decru die Brücke zu Kurven vom Geschlecht 2 fanden.

FESTA (Fast Encryption from Supersingular Torsion Attacks, 2023) ist ein von SIDH inspiriertes KEM-Design, das jedoch auf die zusätzlichen Torsionspunktdaten verzichtet. FESTA verwendet eine andere Protokollstruktur: Der öffentliche Schlüssel enthält nicht die Bilder der Torsionsbasis der Gegenpartei – stattdessen wird die geheime Isogenie ausschließlich über die Bildkurve festgelegt (ohne zusätzliche Punkte). FESTA verschlüsselt mithilfe von Isogenien auf eine Weise, die weniger strukturelle Informationen preisgibt. Erste Sicherheitsanalysen legen nahe, dass FESTA die Struktur des Angriffs von Castryck und Decru vermeidet. FESTA ist jedoch neuer und wurde weniger eingehend untersucht als SIKE während seiner 11-jährigen Analyse. Daher steht die Isogenie-Community dem Einsatz neuer Verfahren vor einer umfassenden Untersuchung vorsichtig gegenüber.

Der Bruch von SIKE liefert wichtige Erkenntnisse. (1) Die Preisgabe zusätzlicher Informationen ist gefährlich: Die zusätzlichen Torsionspunktdaten von SIDH waren für das Protokoll notwendig, legten jedoch fatal viele Informationen offen. Protokolldesigner müssen jedes öffentlich zugängliche Datenelement analysieren, nicht nur die zentralen Werte. (2) Eine bisherige Sicherheitsbilanz ist kein Sicherheitsbeweis: 11 Jahre ohne bekannten Angriff sind beruhigend, aber keine Garantie. Kryptografische Beweise (die Reduktion auf ein klar definiertes schwieriges Problem) sind zuverlässiger als ein Argument, das sich auf Autorität oder überstandene Prüfungen stützt. (3) Neue mathematische Werkzeuge bergen Risiken: Der Angriff von Castryck und Decru verwendete Richelot-Isogenien auf Kurven vom Geschlecht 2 – ein Werkzeug aus der Mathematik, das zuvor nicht für die Kryptanalyse von Isogenien eingesetzt worden war. Kryptanalysten, die neue Primitive untersuchen, müssen auch neue mathematische Gebiete berücksichtigen.

Trotz des Bruchs von SIKE wird die isogeniebasierte Kryptografie weiterhin erforscht. Signaturen von SQISign (177 Byte auf Stufe 1) sind nach wie vor die kompaktesten bekannten PQC-Signaturen und beruhen auf einer anderen Härteannahme (dem Endomorphismenringproblem), die vom SIDH-Angriff nicht betroffen ist. Protokolle auf Basis von CSIDH verwenden die Wirkungsstruktur der Klassengruppe (kommutative Isogenien) ohne Torsionspunkt-Leakage, wobei CSIDH eigene Herausforderungen aufweist (langsamer als SIDH und mit noch laufender Analyse der Quanten-Sicherheit). Die Isogenie-Community betrachtet den Bruch von SIKE als lehrreiche Erfahrung, durch die sich das Verständnis dafür geschärft hat, welche Informationen in Isogenieprotokollen verborgen bleiben müssen – wertvolles Wissen für die Entwicklung zukünftiger Verfahren.

Welcher Aspekt des SIDH-Designs ermöglichte den Angriff von Castryck und Decru?

SIDH verwendet abwechselnde Isogenieketten der Grade 2^a und 3^b zwischen zwei Parteien und teilt Bilder zusätzlicher Torsionspunkte, um den Schlüsselaustausch zu ermöglichen. SIKE versieht SIDH mithilfe von Fujisaki-Okamoto mit CCA2-Sicherheit. SIKE hatte mit 374 Byte die kleinsten Schlüssel aller NIST-PQC-Kandidaten, war jedoch 100- bis 1000-mal langsamer. Nach 11 Jahren Sicherheitsanalyse wurde SIKE im Juli 2022 von Castryck und Decru gebrochen, die mithilfe von Richelot-Isogenien auf Kurven vom Geschlecht 2 das Leakage von Torsionspunkten ausnutzten. NIST strich SIKE aus dem Verfahren. FESTA vermeidet die Preisgabe von Torsionspunkten. SQISign verwendet weiterhin die Härte des Endomorphismenringproblems. Der Bruch von SIKE zeigt, dass zusätzliche öffentliche Daten genauso sorgfältig analysiert werden müssen wie die primären Protokollwerte.