How SIKE was broken: lessons from an isogeny attack

Short answer: In 2022, Wouter Castryck and Thomas Decru of KU Leuven presented an efficient key recovery attack on the Supersingular Isogeny Diffie-Hellman protocol (SIDH). Their abstract says it breaks SIKEp434, a SIKE parameter set aimed at security level 1, in about ten minutes on a single core. The running time they describe is classical, so this was a result about the mathematics of a post-quantum candidate and did not need a quantum computer.

What the paper presents

The ePrint paper "An efficient key recovery attack on SIDH" presents an attack on SIDH, the protocol behind SIKE. The abstract says the attack is based on Kani's "reducibility criterion" for isogenies from products of elliptic curves, and that it relies strongly on the torsion point images that Alice and Bob exchange during the protocol.

An earlier preliminary version, listed in the KU Leuven repository, describes the approach as based on a "glue-and-split" theorem due to Kani. It says the attack exploits the existence of a small non-scalar endomorphism on the starting curve, and also relies on the auxiliary torsion point information that Alice and Bob share. That version was described by its authors as preliminary, with a longer article in preparation.

Running time

The later abstract says that, if one assumes knowledge of the endomorphism ring of the starting curve, the classical running time is polynomial in the input size, heuristically. The abstract excludes the factorization of a small number of integers that depend only on the system parameters.

The authors say the attack is particularly fast and easy to implement if one of the parties uses 2-isogenies and the starting curve comes equipped with a non-scalar endomorphism of very small degree. They say this is the case for SIKE, the instantiation of SIDH that had recently advanced to the fourth round of NIST's standardization effort for post-quantum cryptography.

Their Magma implementation breaks SIKEp434, which aims at security level 1, in about ten minutes on a single core. The preliminary version reported about one hour on a single core for the same parameter set.

What this does and does not show

The attack is on a specific protocol and its published parameters. The abstract does not claim it affects other post-quantum candidates, and this article does not either. Lattice-based schemes such as ML-KEM rest on different mathematics, and nothing in these sources addresses them.

The abstract describes a classical algorithm. Whether a post-quantum scheme resists quantum attacks is a separate question from whether it resists clever classical ones, and this paper shows that a candidate can fail on the second even if the first has not been tested. That reading is ours, and the authors do not draw it in the abstract.

What this does not tell you

This article summarises the abstracts of two versions of one paper. We have not checked the mathematics. It does not describe what happened to SIKE afterwards, which readers should check in the current record of the NIST process.

FAQ

Who found the attack?

Wouter Castryck and Thomas Decru of KU Leuven, in a 2022 ePrint paper.

What did it break?

SIKEp434, a parameter set aimed at security level 1, in about ten minutes on a single core according to the abstract. An earlier version reported about one hour.

Did it need a quantum computer?

No. The abstract describes the running time as classical.

What does it depend on?

The torsion point images exchanged in the protocol, Kani's reducibility criterion, and a starting curve with a small non-scalar endomorphism.

Does it affect ML-KEM?

These sources do not say so. They concern SIDH and SIKE only.