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.

SIKE Schlüsselaustausch

Im Folgenden geben wir einen zugegeben sehr groben Überblick, wie ein Diffie-Hellman Schlüsselaustausch im SIKE Protokoll funktioniert und anschließend, warum der private Schlüssel von Bob effizient berechnet werden kann.

Wie bei einem klassischen Diffie-Hellman Verfahren stehen auch bei SIKE öffentliche Systemparameter fest. Dazu gehören zwei natürliche Zahlen e und f, eine Primzahl $p=2^{e}\cdot 3^{f}-1$ und eine Elliptische Kurve E auf $\mathbb {F} _{p^{2}}$ der Form $y^{2}=x^{3}+6x^{2}+x$, d.h. allen Punkten $(x,y)$ in $\mathbb {F} _{p^{2}}$, die die Gleichung erfüllen. Der zugrundeliegende Körper $\mathbb {F} _{p^{2}}$ hat als Grundmenge genau die komplexen Zahlen, deren Real- als auch Imaginärteil in der Restklasse $\mathbb {F} _{p}{\mbox{ }}(={0,1,2,\dots ,p-1})$ enthalten sind. Desweiteren gibt es noch vier sogenannte Hilfspunkte $\mathrm {P} _{A},\mathrm {Q} _{A},\mathrm {P} _{B},\mathrm {Q} _{B}$ auf E, dessen Bedeutung wir gleich beleuchten werden. Wichtig für uns ist, dass die Punkte auf einer Elliptischen Kurve zusammen mit der Punktaddition eine Gruppe bilden. Können mit Homomorphismen, also strukturerhaltenden Abbildungen, auf Untergruppen abgebildet werden. Einen nicht-konstanten Gruppen Homomorphismus von einer elliptischen Kurve auf sich selbst nennen wir hier auch Isogenie. Der Kern einer Isogenie ist die Menge aller Punkte, die auf das neutrale Element abgebildet werden. Der Grad einer Isogenie ist die Größe ihres Kerns. Der Gedanke des SIKE Schlüsselaustauschs ist, dass sich Alice und Bob jeweils geheime Isogenien ausdenken, die sich zu einer dritten Isogenie verknüpfen lassen. Allerdings können sie nicht einfach die Isogenien bzw. ihre Kerne über den ungesicherten Kanal verschicken. Darum legen sie zwei (öffentliche) jeweils öffentliche Hilfspunktpaare fest, die Punkte $\mathrm {P} _{A},\mathrm {Q} _{A}$ der Ordnung $2^{e}$ für Alice und die Punkte $\mathrm {P} _{B},\mathrm {Q} _{B}$ der Ordnung $3^{f}$ für Bob. Alice denkt sich nun eine geheime ganze Zahl $a$ aus, und erhält mit $A=\langle \mathrm {P} _{A}+a\cdot \mathrm {Q} _{A}\rangle$ den Kern ihrer Isogenie $\varphi _{A}$ der Ordnung $2^{e}$. Bob erhält analog eine Isogenie $\varphi _{B}$ der Ordnung $3^{b}$. Nun tauschen sie über den unsicheren Kanal die Bildwerte der Hilfspunkte des jeweils anderen unter der eigenen Isogenie aus, also $\varphi _{A}(\mathrm {P} _{B})$, $\varphi _{A}(\mathrm {Q} _{B})$ und $\varphi _{B}(\mathrm {P} _{A})$, $\varphi _{B}(\mathrm {Q} _{A})$ aus. Somit kann der jeweils können sie mit dem eigenen Geheimnis und den Bildwerten der Isogenie des anderen auf einen gemeinsamen Kern und somit auch eine gemeinsame Isogenie kommen, die ein Angreifer ohne eines der privaten Geheimnisse $a$ oder $b$ nicht effizient ermitteln kann.

Mathematischer Angriff

Der Angriff von Castryck und Decru zeigt, wie eine bösartige Alice Bobs geheime Isogenie rekonstruieren kann. Der Grundgedanke dabei ist, dass die gemeinsame Isogenie von Alice und Bob eine besondere Isogenie ist, die wir hier, um mathematische Definitionen und Genauigkeiten zu ersparen, einfach nur reduzierbar nennen. Man kann sich das so vorstellen, dass ihr Bild das Produkt zweier elliptischer Kurven ist. Das Ereignis, dass man von einer belibigen elliptischen Kurve durch eine (2,2)-Isogenie auf einem Produkt zweier Kurven landet, beträgt ungefähr $10/p$, also unfassbar klein. Castryck und Decru ziehen sich Kanis Theorem zur Hilfe, was grob besagt, dass wenn wir eine Isogenie haben und zwei Kerne, die bis (bis auf das neutrale Element) disjunkt den Kern der Isogenie aufspannen, die Isogenie reduzierbar ist bzw. wir auf einem Produkt zweier Kurven landen. Die in SIKE von Alice und Bob errechnete Isogenie zusammen mit den Kernen A und B entspricht genau den Bedingungen von Kanis Theorem und bildet somit auf eine Produktkurve ab. Im Angriff betrachten wir Bobs $3^{f}$-Isogenie als Verkettung von f vielen 3-Isogenien, die von Alice Bildkurve auf eine Produktkurve abbilden. Für die erste 3-Isogenie haben wir drei Möglichkeiten zu raten. Wir probieren eine und wissen nun, dass wenn wir richtig liegen, wir von der entstehenden Kurve mit einer $3^{f-1}$-Isogenie auf unsere Produktkurve gelangen. Wir konstruieren nun eine $2^{e}-3^{f-1}$-Isogenie, deren Pseudoinverse zusammen mit Bobs übriger $3^{f-1}$-Isogenie eine $2^{e}$-Isogenie ergibt, die laut Kanis Theorem wieder reduzierbar ist. Wir erinnern uns, dass es extrem unwahrscheinlich ist, mit solch einer Isogenie, die auch nur die e-fache Verknüpfung von 2-Isogenien ist, auf einer Produktkurve zu landen. Ob wir dies tun lässt sich sehr effizient überprüfen. Wenn die nicht der Fall ist, haben wir die 3-Isogenie auf jeden Fall falsch geraten, wenn doch können wir jedoch mit hoher Sicherheit ausschließen, dass wir falsch geraten haben, da es so unwahrscheinlich ist aus Zufall auf einer Produktkurve gelandet zu sein. So erraten wir schritt für Schritt Bobs 3^f Isogenie, indem wir immer wieder eine $2^{e}-3^{f-j}$-Isogenie ($j\in \{1,\dots ,e-1\}$) bauen und überprüfen, ob wir mit der entstehenden $2^{f}$ Isogenie auf einer Produktkurve landen. Kanis Theorem liefert uns hier sozusagen ein Entscheidungskriterium.

Angewandter Angriff

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.

SIKE_parameters = {
    "SIKEp434" : (216, 137),
    "SIKEp503" : (250, 159),
    "SIKEp610" : (305, 192),
    "SIKEp751" : (372, 239)
}

Code Beispiel 1: SIKE Parametern in den Code

Wie es auf Beispiel 1 zu sehen ist, sind die SIKE Parametern für die Werten $a$ und $b$ gegeben. Mithilfe dieser Parameter kann die Primzahl $p$ definiert werden. $p=2^{a}\cdot 3^{b}-1$. $p$ ist wichtig, um die Elliptische Kurven und Isogenien zu generieren. Die elliptische Kurve E$_{\mathrm {start} }$ über einem endlichen Feld $\mathbb {F} _{p^{2}}$ wird als Startpunkt für die Challenge definiert. Eine zufällige ganze Zahl Bobskey wird generiert und auf ternäre Ziffern eingestellt. Zum Abschluss der Challenge wird eine neue elliptische Kurve E$_{B}$ erstellt und von E$_{B}$ zu E$_{B_{\mathrm {start} }}$ eine Isogeniekette erzeugt. Die Isogeniekette wird auf der Grundlage der Punkte P3 + Bobskey *Q3 erstellt, wobei P3 und Q3 Torsionspunkte auf E$_{\mathrm {start} }$ sind. Die Länge der Isogeniekette 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$_{\textrm {start}}$ zur elliptischen Kurve E$_{B}$ 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$_{\mathrm {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 Isogeniekette (Kette) von der elliptischen Kurve E$_{\mathrm {start} }$ zu einer neuen elliptischen Kurve E$_{B}$, 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 Isogenie 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 Isogenieberechnungen beinhaltet.

# generate challenge key
Bobskey = randint(0,3^b)

EB, chain = Pushing3Chain(E_start, P3 + Bobskey*Q3, b)
# Speeds things up in Sage
EB.set_order((p+1)^2)
PB = P2
for c in chain:
    PB = c(PB)
QB = Q2 
for c in chain:
    QB = c(QB)

print(f"If all goes well then the following digits should be found: {Integer(Bobskey).digits(base=3)}")

Code Beispiel 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/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 = 68berechnet 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=137ergeben sich mit der uv-Tabelle also folgende Ergebnisse:

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 E$_{B}$. Die Kurve C wird durch eine Reihe von Transformationen erzeugt, die auf die Ausgangskurve E$_{\mathrm {start} }$ angewandt werden, geleitet von tauhatkernel_distort, und die Funktion Pushing3Chain spielt eine entscheidende Rolle bei diesem Kurvenerzeugungsprozess. Während E$_{B}$ 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.

# for j in CartesianPower([0,1,2], bet1) do
for j in product([0,1,2], repeat=int(bet1)):
    print(f"Testing digits: {[j[k] for k in range(bet1)]}")

    # tauhatkernel = 3^bi*P3 + sum([3^(k-1)*j[k-1] for k in range(1,beta+1)])*3^bi*Q3
    tauhatkernel = 3^bi*P3 
    for k in range(1, bet1+1):
        tauhatkernel += (3^(k-1)*j[k-1])*3^bi*Q3

    tauhatkernel_distort = u*tauhatkernel + v*two_i(tauhatkernel)

    C, tau_tilde = Pushing3Chain(E_start, tauhatkernel_distort, bet1)

    P_c = u*P2 + v*two_i(P2) 
    for taut in tau_tilde:
        P_c = taut(P_c)
    Q_c = u*Q2 + v*two_i(Q2)
    for taut in tau_tilde:
        Q_c = taut(Q_c)

    # if j eq <2 : k in [1..bet1]> or Does22ChainSplit(C, EB, 2^alp*P_c, 2^alp*Q_c, 2^alp*PB, 2^alp*QB, ai) then
    if j == (2,)*bet1 or Does22ChainSplit(C, EB, 2^alp*P_c, 2^alp*Q_c, 2^alp*PB, 2^alp*QB, ai):
        print("Glue-and-split! These are most likely the secret digits.")
        for k in j:
            skB.append(k)
        break

print(skB)

Code Beispiel 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://sike.org/files/SIDH-spec.pdf
• https://eprint.iacr.org/2022/975.pdf
• https://www.youtube.com/watch?v=rwri6Ai4H1I (sehr empfehlenswert!)
• 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