Sike: the post-quantum scheme that fell to a laptop

In the summer of 2022, isogeny-based cryptography was having a good year. SIDH — Supersingular Isogeny Diffie–Hellman — had been studied for over a decade, and SIKE, the key-encapsulation scheme built on it, was one of the last few candidates standing in NIST's post-quantum competition. It was the elegant one: tiny keys, security resting on a problem with no known efficient solution, classical or quantum.

Then, on July 30th, Wouter Castryck and Thomas Decru posted An efficient key recovery attack on SIDH, with a few hundred lines of Magma attached. On one core of an ordinary laptop, it recovered the secret key of the top SIKE parameter set in about an hour. Re-implementations got that to minutes, then seconds. No quantum computer was involved at any point. The scheme was dead inside a month.

I think this is one of the most instructive failures in modern cryptography, so I turned it into a challenge. This post is the background — and this time I'll write the math out, because the break is genuinely beautiful and you can't feel it from prose alone. The challenge is at the bottom; I won't spoil it.

First, the objects

Everything lives over the field $\mathbb{F}_{p^2}$, with a prime of the shape

$p = 2^{e_A}\,3^{e_B} - 1 .$

Fix a supersingular elliptic curve $E_0/\mathbb{F}_{p^2}$. Supersingularity buys one very clean fact about the group of points:

$\#E_0(\mathbb{F}_{p^2}) = (p+1)^2 = \big(2^{e_A}3^{e_B}\big)^2 .$

So for any $n \mid p+1$ the $n$-torsion is fully rational and is free of rank two:

$E_0[n] = \{\,P \in E_0 : [n]P = \mathcal{O}\,\} \;\cong\; (\mathbb{Z}/n\mathbb{Z})^2 .$

In particular $E_0[2^{e_A}]$ and $E_0[3^{e_B}]$ each have a two-element basis. That rank-two structure is the whole game.

An isogeny $\varphi : E \to E'$ is a non-constant morphism of curves with $\varphi(\mathcal{O}) = \mathcal{O}$; it is automatically a group homomorphism. A separable isogeny is pinned down by its kernel: for any finite subgroup $G \subset E$ there is a curve $E/G$ and a map

$\varphi : E \to E/G, \qquad \ker \varphi = G, \qquad \deg \varphi = |G|,$

unique up to isomorphism of the target and computable from $G$ by Vélu's formulas. "Walking the graph" means repeatedly quotienting by a small cyclic subgroup: the vertices are supersingular curves up to isomorphism (tagged by their $j$-invariant), the edges are degree-$\ell$ isogenies, and the graph is a $(\ell+1)$-regular Ramanujan expander — walks mix fast and look random.

SIDH, written out

The public parameters are $E_0$, a basis $\{P_A, Q_A\}$ of $E_0[2^{e_A}]$, and a basis $\{P_B, Q_B\}$ of $E_0[3^{e_B}]$.

Alice picks a secret $\alpha \in \mathbb{Z}/2^{e_A}\mathbb{Z}$ and walks the 2-isogeny whose kernel is one cyclic subgroup of $E_0[2^{e_A}]$:

$A = \langle P_A + [\alpha]Q_A \rangle, \qquad \varphi_A : E_0 \to E_A = E_0/A .$

Bob picks $\beta \in \mathbb{Z}/3^{e_B}\mathbb{Z}$ and walks the 3-isogeny:

$B = \langle P_B + [\beta]Q_B \rangle, \qquad \varphi_B : E_0 \to E_B = E_0/B .$

Now the subtlety that the cartoon version skips. To finish, Alice has to push her kernel through Bob's isogeny — she needs $\varphi_B(P_A + [\alpha]Q_A)$. She never sees $\varphi_B$, only the curve $E_B$. But an isogeny is a homomorphism, so it commutes with the group law:

$\varphi_B\big(P_A + [\alpha]Q_A\big) = \varphi_B(P_A) + [\alpha]\,\varphi_B(Q_A) .$

That one identity is the reason SIDH publishes torsion-point images. If Bob hands over $\varphi_B(P_A)$ and $\varphi_B(Q_A)$, Alice can evaluate the right-hand side for her own secret $\alpha$ without ever knowing $\varphi_B$. So the public keys are

$$\text{Alice}: \big(E_A,\ \varphi_A(P_B),\ \varphi_A(Q_B)\big), \qquad \text{Bob}: \big(E_B,\ \varphi_B(P_A),\ \varphi_B(Q_A)\big) .$$

Each side re-walks on the other's curve,

$$E_{BA} = E_B \big/ \big\langle \varphi_B(P_A) + [\alpha]\varphi_B(Q_A) \big\rangle, \qquad E_{AB} = E_A \big/ \big\langle \varphi_A(P_B) + [\beta]\varphi_A(Q_B) \big\rangle,$$

and because both quotients equal $E_0/\langle A, B\rangle$ up to isomorphism, the two parties land on the same curve. The shared secret is its fingerprint:

$j(E_{AB}) = j(E_{BA}) =: \text{shared key}.$

Hold onto that identity $\varphi_B(P_A + [\alpha]Q_A) = \varphi_B(P_A) + [\alpha]\varphi_B(Q_A)$. The torsion images are the gear that makes SIDH turn — and the crack the whole thing splits along.

Why it looked hard

Breaking Bob means solving the supersingular isogeny problem with torsion: given $E_0$, $E_B$, and the images $\varphi_B(P_A), \varphi_B(Q_A)$, recover $\varphi_B$ (equivalently $\beta$). The secret lives in a space of size $3^{e_B} \approx \sqrt{p}$, and the best generic method is a meet-in-the-middle / claw-finding walk from both endpoints, which costs

$\approx 3^{e_B/2} \approx p^{1/4}.$

At SIKE's sizes ($p \approx 2^{434}$) that is $\approx 2^{108}$ — out of reach. No quantum algorithm did meaningfully better once you account for memory. For ten years, $p^{1/4}$ was the security level, and the torsion images — published in plain sight the whole time — were assumed to be harmless.

The break, in two dimensions

Castryck and Decru's move is to stop searching for $\varphi_B$ and instead certify guesses about it, by building a higher-dimensional object that only fits together when the guess is right.

The engine is Kani's lemma (Ernst Kani, 1997), a statement about when a 2-dimensional isogeny between abelian surfaces is "reducible." Set $d = \deg\varphi_B = 3^{e_B}$ and pick an auxiliary power

$N = 2^{e_A} \quad\text{with}\quad N > d .$

Kani packages $\varphi_B$, together with a complementary isogeny of degree $N - d$, into a single $N$-isogeny of abelian surfaces

$\Phi : E_0 \times E_B \longrightarrow \mathcal{A},$

whose kernel is essentially the graph of $\varphi_B$ on the $N$-torsion:

$\ker \Phi \;=\; \big\lbrace\, \big(\theta(P),\ \varphi_B(P)\big) : P \in E_0[2^{e_A}] \,\big\rbrace,$

where $\theta \in \mathrm{End}(E_0)$ is an endomorphism realizing the complementary degree, $\theta\hat{\theta} = [\,N - d\,] = [\,2^{e_A} - 3^{e_B}\,]$. Two things make this computable:

• You can write $\ker\Phi$ down only because $\varphi_B(P_A), \varphi_B(Q_A)$ are public. The attack's input is the helper data.
• Building $\theta$ needs $N - d$ expressed as a norm in $\mathrm{End}(E_0)$ — e.g. $N - d = u^2 + v^2$ and $\theta = u + v\,\iota$ when $\iota = \sqrt{-1}$ is an explicit endomorphism. This is why CD needs a starting curve with known endomorphism ring (the SIKE base, or $j = 1728$, where $\sqrt{-1}$ is a map you can apply to points). On a random supersingular curve you would not have $\theta$.

Because $N = 2^{e_A}$ is a power of two, $\Phi$ factors into a chain of $e_A$ $(2,2)$-isogenies between principally polarized abelian surfaces — each step an explicit Richelot isogeny on a genus-2 curve. And here is the punchline. A principally polarized abelian surface is exactly one of two things:

$\mathcal{A} \;\cong\; \mathrm{Jac}(\mathcal{C}) \quad(\text{genus-2 curve}) \qquad\text{or}\qquad \mathcal{A} \;\cong\; E \times E' \quad(\text{product of elliptic curves}).$

Kani's criterion says the chain splits into a product of elliptic curves precisely when the diamond closes — i.e. when the piece of $\varphi_B$ you fed in is the real one. That boolean,

$\texttt{Does22ChainSplit}(\cdot) \in \{\text{true},\ \text{false}\},$

is an oracle for correctness. Now turn it into key recovery. Write Bob's secret in base 3,

$\beta = \sum_{i} d_i\, 3^{i}, \qquad d_i \in \{0,1,2\},$

guess the top handful of digits, assemble the corresponding $(2,2)$-chain from the torsion images, and ask whether it splits. Correct guesses split; wrong ones do not. Peel off digits a few at a time (a refinement by Oudompheng recovers the rest directly from the first split). Each test is a fixed-length chain of Richelot steps — polynomial in $\log p$ — and there are $O(e_B)$ of them:

$\text{cost} \;=\; O\!\big(\mathrm{poly}(\log p)\big) \quad\text{vs.}\quad p^{1/4}.$

The wall is gone. The irony is exact: the data that made the key exchange possible is the data that makes the attack possible. The one delicate point is the inequality $N = 2^{e_A} > 3^{e_B}$; SIKE's most balanced sets ($2^{216}$ vs $3^{137} \approx 2^{217}$) sit a hair on the wrong side, repaired by a short auxiliary isogeny. Within weeks, Maino–Martindale and Robert generalized the whole thing to provably polynomial time in every case. SIKE was withdrawn.

"Quantum-safe" was never the whole promise

The part I keep coming back to: SIKE's quantum resistance was real. There was no good quantum algorithm for the underlying problem, and there still isn't. It fell to a classical attack nobody had found in ten years — one that climbed the scheme's algebraic structure, not its key size.

• Security isn't the size of the search space; it's whether that space has structure an attacker can exploit. SIDH had a lot of it.
• Any helper data you publish to make a protocol work is part of the attack surface, modeled or not. SIDH's torsion images were both at once.
• "Resistant to attack $X$" quietly gets read as "secure." They are not the same sentence.

None of this was obvious in advance. The torsion images had been published for a decade and studied by experts. The break needed a tool — Kani's lemma, genus-2 isogenies — that simply wasn't in the average cryptographer's kit. It wasn't a bug; it was a bridge between two fields that hadn't been crossed yet.

A challenge: SIKE!

I built a challenge around exactly this, and it's live on Dreamhack: SIKE!.

It hands you one complete run of the key exchange — both public keys, the torsion images $\varphi(\cdot)$, and a flag sealed under $j(E_{AB})$. The parameters are real-SIKE-sized: large enough that the brute-force instincts (guess $\beta$, meet in the middle at $p^{1/4}$) are hopeless, small enough that the right attack finishes in seconds. (An earlier version of mine was small enough to meet-in-the-middle — which missed the entire point, because the torsion images went untouched, the one part that actually matters. So I grew it until the only door left was the structure.)

I won't tell you which attack. If you read this far, you already know its name, and you've seen the shape of the oracle it's built on. The real work is the part this post skipped: going from "I know this break exists" to "I made it run on these numbers." That gap is most of applied cryptanalysis, and it's a genuinely satisfying one to cross.

Go break it. It won't even take an afternoon.