SIKE: Los, Stop, Schade

SIKE und NIST

SIKE steht für "Supersinguläre Isogeny Key Exchange". Es handelt sich um ein asymmetrisches Kryptosystem, das auf isogenen elliptischen Kurven basiert. SIKE ist ein Verschlüsselungsverfahren, das die Sicherheit von Datenübertragungen gewährleistet. Es verwendet isogene elliptische Kurven und die Berechnung von Isogenien, um Schlüssel auszutauschen und Daten zu verschlüsseln. SIKE basiert auf supersingulären isogenen elliptischen Kurven und Isogenien, wodurch es eine post-quantum Kryptografie bietet, die vor Angriffen von Quantencomputern sicher ist. Isogenien sind mathematische Transformationen zwischen elliptischen Kurven, die SIKE zur Schlüsselaustausch und Datenverschlüsselung verwendet. NIST (National Institute of Standards and Technology): Das National Institute of Standards and Technology (NIST) ist eine Amerikanische Behörde, die Standards und Richtlinien für verschiedene Bereiche, einschließlich Kryptografie, entwickelt und pflegt. NIST spielt eine wichtige Rolle bei der Festlegung von Standards für kryptografische Algorithmen und Protokolle, um die Sicherheit von Informationen und Kommunikation zu gewährleisten. NIST hat einen Wettbewerb zur Identifizierung von post-quantum-kryptografischen Algorithmen ins Leben gerufen, bei dem SIKE eine bedeutende Rolle spielt. NIST wird voraussichtlich Standards für post-quantum-Kryptografie festlegen, die von Organisationen und Regierungen weltweit übernommen werden.

Sike würde es bis in die 4. Runde des NIST-Wettbewerbs für quantensichere Verschlüsselungsprotokolle schaffen. Leider wurde zu der Zeit, als SIKE an Popularität gewann, ein neues Papier veröffentlicht, das sicherstellte, dass SIKE nicht sicher ist und mit einem Single-core Laptop entschlüsselt werden kann. Der Angriff erforderte weder zu viel Rechenleistung noch dauerte er zu lange, um die vom NIST-Wettbewerb vorgegebenen Parameter zu entschlüsseln.

Der Angriff wurde ursprünglich von dem Duo Wouter Castryck und Thomas Decru durchgeführt. In ihrem Beitrag erklärten sie, dass der Angriff mithilfe des Computer-Algebra-Software-Systems namens Magma möglich war. Da Magma nicht quelloffen ist, stand es nicht vielen Menschen zur Verfügung, so dass nicht viele den Angriff selbst testen konnten. Um die Implementierung für die Öffentlichkeit zugänglicher zu machen, implementierten Giacomo Pope und Rémy Oudompheng den ursprünglichen Angriff erneut in einem Softwaresystem namens SageMath. SageMath ist quelloffen, und jeder kann den Angriff herunterladen und auf seinen eigenen Geräten neu implementieren, solange SageMath auf dem jeweiligen Gerät installiert ist.

SageMath kann hier installiert werden: https://www.sagemath.org/

Die Parameter für den Angriff werden bereits im Vorfeld vom NIST-Wettbewerb vorgegeben. Die Parameter stellen sicher, dass der Schlüssel lang genug ist, damit der Angriff in einer realen Anwendung sinnvoll ist, und auch um sicherzustellen, dass die Verschlüsselung robust genug ist und ein gewisses Maß an Sicherheit bietet. Das bedeutet, dass die Parameter eine Richtlinie für die Entwickler darstellen und ihnen helfen, die richtigen Entscheidungen zu treffen, wenn SIKE implementiert wird.

Abbildung 1: SIKE Parametern in den Code

Wie es auf Abbildung 1 zu sehen ist, sind die SIKE Parametern für die Werten a und b gegeben. Mithilfe diese Parametern kann das Primzahl p definiert werde. $P=2^{a}\cdot 3^{b}-1$. p ist wichtig um die Elliptische Kurven und Isogenien zu generieren. Die elliptische Kurve E_start über einem endlichen Feld Fp2 wird als Startpunkt für die Challange definiert. Eine zufällige ganze Zahl Bobskey wird generiert und auf ternäre Ziffern eingestellt. Zum Abschluss der Challenge wird eine neue elliptische Kurve EB erstellt und von EB zu EB_start eine Isogeniesekette erzeugt. Die Isogeniesekette wird auf der Grundlage der Punkte P3 + Bobskey *Q3 erstellt, wobei P3 und Q3 Torsionspunkte auf E_start sind. Die Länge der Isogeniesekette ist gleich dem Parameter b. Der Aufbau der Challenge besteht im Wesentlichen aus der Wahl der Parameter, der Generierung des privaten Schlüssels Bobskey und der Erstellung der Isogenese von der elliptischen Kurve E_start zur elliptischen Kurve EB auf der Basis von Bobskey und den angegebenen Parametern.

Die Codezeile EB, chain = Pushing3Chain(E_start, P3 + Bobskey * Q3, b) beinhaltet elliptische Kurvenoperationen und ist Teil des Challenge-Setups im Code. P3 und Q3 sind Punkte auf einer elliptischen Kurve E_start. Diese Punkte sind Teil des Challenge-Setups. Bobskey ist eine zufällige ganze Zahl aus dem Bereich [0, 3^b). Diese ganze Zahl ist Bobs privater Schlüssel in ternärer Darstellung. Bobskey * Q3 bedeutet eine skalare Multiplikation des Punktes Q3 mit der ganzen Zahl Bobskey. Diese Operation berechnet Bobskey mal den Punkt Q3 auf der elliptischen Kurve. P3 + Bobskey * Q3 addiert das Ergebnis der skalaren Multiplikation (Bobskey * Q3) zu dem Punkt P3. Dies ist eine Punktaddition auf der elliptischen Kurve. Das Ergebnis ist ein neuer Punkt auf der Kurve. Pushing3Chain(E_start, P3 + Bobskey * Q3, b) erzeugt eine Isogenesekette (Kette) von der elliptischen Kurve E_start zu einer neuen elliptischen Kurve EB, die auf den Punkten P3 + Bobskey * Q3 basiert. Der Parameter b gibt die Länge der Kette an.

Zusammenfassend lässt sich sagen, dass die Codezeile im Wesentlichen eine Herausforderung für den Angreifer darstellt, indem sie ein Problem der Isogenese elliptischer Kurven aufstellt. Das Ziel des Angreifers ist es, Bobs privaten Schlüssel (Bobskey) auf der Grundlage dieser Herausforderung wiederherzustellen, was die Arbeit mit den Operationen der elliptischen Kurve und den Isogeneseberechnungen beinhaltet.

Abbildung 2: Pushing3Chain Funktion

Attack

skB ist als leere Liste definiert, in die die Werte von Bobs geheimem Schlüssel während des Angriffs nacheinander eingefügt werden.

Der Code durchläuft eine Schleife über i von 1 bis b-2. Für jedes i wird geprüft, ob (b-i) ungerade ist, indem die Bedingung (b-i) % 2 == 1 verwendet wird. Ist dies der Fall, wird ein Index berechnet und Daten aus der uvtable auf der Grundlage dieses Index gesammelt. index wird berechnet als (b - i + 1) // 2. exp wird aus uvtable[index-1][1] extrahiert. Wenn exp kleiner oder gleich a ist, werden auch u und v aus uvtable[index-1][2] bzw. uvtable[index-1][3] abgerufen. Diese Daten werden in der Liste expdata an der (i-1)-ten Position als [exp, u, v] gespeichert.

Nehmen wir die Parameter a=216 und b=137

Da `b` 137 ist, wird `expdata` eine Liste mit 134 Unterlisten sein, die jeweils drei Nullen enthalten. Schleife von `i` im Bereich von 1 bis `b - 2`, der von 1 bis 135 reicht. Prüfe, ob `(b - i) % 2 == 1 für jedes i. Diese Bedingung prüft, ob b - i eine ungerade Zahl ist. Wenn `(b - i)` ungerade ist, wird der `Index` als `(b - i + 1) // 2` berechnet. Dieser Index wird für den Zugriff auf Elemente der `uvtable` verwendet.

b = 137, also ist expdata eine Liste mit 134 Unterlisten, gefüllt mit `[0, 0, 0]`. Die Schleife läuft von i = 1 bis i = 135. Wenn i = 1 ist, ist (b - i) % 2 == 0, also passiert nichts. Wenn i = 2 ist, ist (b - i) % 2 == 1, so dass der Index als (137 - 2 + 1) // 2 = 68 berechnet wird. Dann holt es exp = 135, u = 68402650496677101758628224525965 und v = 491073477706829402358064079515557 aus uvtable[68] und aktualisiert expdata[1] mit [135, 68402650496677101758628224525965, 491073477706829402358064079515557]. Dieser Vorgang wird für alle Werte von `i` fortgesetzt, bis die Schleife beendet ist. Nach der Schleife wird bet1 inkrementiert, bis es den Wert 2 erreicht (da expdata[2][0] der erste Nicht-Null-Wert ist).

Für a = 216 und b = 137 ergeben sich mit der uv-Tabelle also folgende Ergebnisse

bet1 = 2 ai = expdata[2-1][0] = 135 u = expdata[2-1][1] = 68402650496677101758628224525965 v = expdata[2-1][2] = 491073477706829402358064079515557

Diese Ergebnisse sind wichtig für die spätere Verwendung dieser Werte beim Orakel für die Split- und Glue-Operationen der Isogenien im Attack.

Die ersten bet1-Ziffern werden für den Angriff berechnet, indem geprüft wird, ob einer der Werte korrekt ist und die Bedingung für das Glue- und Split-Orakel erfüllt. Dies geschieht, um einen bekannten Ausgangspunkt für den Angriff festzulegen und zu beweisen, dass der Angriff Schritte in die richtige Richtung unternimmt.

Das Klebe- und Teilungsorakel wird verwendet, um zu prüfen, ob ein Schritt in die richtige Richtung gemacht wird, indem die gegebenen Kurven geklebt und geteilt werden: die erste Kurve C und die zweite Kurve EB. Die Kurve C wird durch eine Reihe von Transformationen erzeugt, die auf die Ausgangskurve E_start angewandt werden, geleitet von tauhatkernel_distort, und die Funktion Pushing3Chain spielt eine entscheidende Rolle bei diesem Kurvenerzeugungsprozess. Während EB am Anfang des Codes initialisiert wird. Indem man auch die Punkte der Kurven der Ordnung 2^a und 3^b verwendet, kann die Funktion genutzt werden. Die Funktion nutzt die Eigenschaften von Richelot-Isogenien (kein Hinweis), wobei geprüft wird, ob die aus C und der Richelot-Isogenie abgeleitete Kurve in ein Produkt aus sipersingulären elliptischen Kurven zerlegt werden kann. Durch Kleben wird eine neue Isogenie erzeugt, und von dieser Klebekarte werden eine Kurve und ein Paar neuer Punkte durch eine Kette von Isogenien abgebildet.

Der Angriff besteht darin, eine Kette von Isogenien zu konstruieren, ausgehend von einer bekannten Ausgangskurve und einem Punkt. Diese Kette stellt eine Folge von Transformationen dar, die auf die Kurve und den Punkt angewendet werden. Der Angriff besteht darin, eine Kette von Isogenien zu konstruieren, ausgehend von einer bekannten Ausgangskurve und einem Punkt. Diese Kette stellt eine Folge von Transformationen dar, die auf die Kurve und den Punkt angewendet werden. An einem bestimmten Punkt der Kette wird die Funktion "Does22ChainSplit" mit bestimmten Parametern aufgerufen. Diese Funktion prüft, ob der aktuelle Zustand der Isogenesekette in zwei separate Ketten aufgeteilt werden kann. Wenn sie `True` zurückgibt, deutet dies darauf hin, dass die aktuellen Berechnungen zu einer Situation geführt haben, in der die elliptische Kurve in zwei getrennte Kurven zerlegt werden kann.

Wenn eine Kettenaufspaltung auftritt, zeichnet der Angreifer die Ziffern oder Parameter auf, die zum Erreichen dieser Aufspaltung verwendet wurden. Diese Ziffern sind potenzielle Kandidaten für Teile von Bobs geheimem Schlüssel, da sie mit der Transformation verbunden sind, die zur Aufspaltung der Kurve geführt hat. Das erste Teil des Angriffs kann in Abbildung 3 gesehen werden.

Abbildung 3: Angriff mit den Glue and Split Oracle.

Der Angriff wird fortgesetzt, in der Hoffnung, weitere Aufspaltungen zu finden und weitere Ziffern aufzuzeichnen. Mit der Zeit, wenn mehr Ziffern aufgezeichnet werden, kann der Angreifer genügend Informationen zusammensetzen, um Bobs gesamten geheimen Schlüssel wiederherzustellen. Das liegt daran, dass jede aufgezeichnete Ziffer einen Schritt in der Kette der Isogenese darstellt und dazu beiträgt, eine Folge von Transformationen zu bilden, die schließlich zum geheimen Schlüssel führt.

Ein einziger Kettensplit verrät zwar nicht sofort Bobs geheimen Schlüssel, ist aber ein entscheidender Schritt im Angriffsprozess. Er bedeutet einen Fortschritt in der Fähigkeit des Angreifers, die Kurve in einfachere Komponenten zu zerlegen und potenzielle Kandidaten für Teile des geheimen Schlüssels aufzuzeichnen

Der letzte Teil des Codes beinhaltet die Angriffsphase, um die letzten Ziffern von Bobs geheimem Schlüssel zu erzwingen. Es gibt eine Schleife, die die potenziellen Werte durchläuft und eine elliptische Kurve mit denselben Parametern und derselben Kette wie im Setup erzeugt. Die Schleife prüft, ob die j-Invariante der generierten elliptischen Kurve, mit der Bobs Schlüssel gefunden werden soll, mit der j-Invariante der zuvor generierten Kurve übereinstimmt. Wenn sie übereinstimmen, bedeutet dies, dass die richtigen Werte für die letzten Ziffern gefunden wurden.

Am Ende wird Bobs Schlüssel ausgedruckt, der mit dem privaten Schlüssel übereinstimmt, der während des Einrichtungsteils des Codes erzeugt wurde.

Quellen https://research.nccgroup.com/2022/08/08/implementing-the-castryck-decru-sidh-key-recovery-attack-in-sagemath/

https://doc.sagemath.org/html/en/tutorial/programming.html

https://eprint.iacr.org/2022/975.pdf#page=13

https://www.normalesup.org/~oudomphe/textes/202208-castryck-decru-shortcut.pdf