The paper An efficient key recovery attack on SIDH by Wouter Castryck and Thomas Decru is a major breakthrough in isogeny cryptanalysis. This relates to the SIDH protocol by Jao and De Feo, and the NIST round 4 finalist SIKE.

I do not have time to explain all the technical details, but here are some quick answers to your burning questions.

1. Is the result true?

There is no reason to doubt this. Code is provided (though I haven’t run it myself) and I understand the SIKE team has confirmed the attack. Having solved the Microsoft $IKEp217 challenge, Castryck and Decru are eligible to claim the $50,000 USD prize.

Some aspects of the attack and its complexity analysis are heuristic, but that is normal and acceptable for cryptanalysis. The experimental results show that the attack is very practical.

2. How does the attack work?

The attack exploits the fact that SIDH has auxiliary points and that the degree of the secret isogeny is known. The auxiliary points in SIDH have always been an annoyance and a potential weakness, and they have been exploited for fault attacks, the GPST adaptive attack, torsion point attacks, etc.

Let be the base curve and let have order . Let be given such that there exists an isogeny of degree with , , and

A key aspect of SIDH is that one does not compute directly, but as a composition of isogenies of degree 3. In other words, there is a sequence of curves connected by 3-isogenies.

Essentially, like in GPST, the attack determines the intermediate curves and hence eventually determines the private key. At step the attack does a brute-force search of all possible , and the magic ingredient is a gadget that shows which one is correct.

(The above is over-simplified, the isogenies in the attack are not of degree 3 but of degree a small power of 3.)

3. What is this magic ingredient?

It is a theorem by Ernst Kani about reducible subgroups of abelian surfaces.

4. Is there a simple way to explain the magic ingredient?

Nope. Go learn about Richelot isogenies and abelian surfaces.

5. What does this mean for the NIST round 4 candidate SIKE?

The scheme specified in the SIKE NIST submission is broken.

6. Can SIDH be fixed?

Already on twitter there were several suggestions on how to possibly avoid the attack. For example, follow Peter Kutas @kutasp and Boris Fouotsa @FouotsaB for some threads.

To be able to use the magic ingredient the attacker must efficiently compute a number of isogenies with degrees of the form for various and it is not clear how to do this if we are not close to a curve with small discriminant complex multiplication. So one hope is that SIDH can be saved by choosing a base curve with unknown endomorphism ring (this might require some kind of public setup).

The paper suggests that variants of SIDH such as B-SIDH (using primes other than 2 and 3) should be attackable. So it seems that changing the primes will not prevent the attack.

7. Does it break CSIDH or other isogeny cryptosystems?

No. The attack very specifically relies on two things: (1) that the degree of the secret isogeny is known; (2) the attacker is provided with the auxiliary points. Hence the attack does not seem to break CSIDH or SQISign.

8. Does it break ECC?

No. The attack assumes the degree of the isogeny is known, and that is exactly the secret key in ECC. There is no particular reason to think attacks on SIDH lead to attacks on ECC.

9. Why was it only discovered now?

The theoretical foundations of the attack are described in a paper by Kani from 1997 (and also some useful tools are in a paper by Howe, Leprévost and Poonen from 2000). So in some sense the attack could have been noticed at any time. But a key point is that this is not an attack one is going to discover by thinking only about isogenies between elliptic curves. The attack deeply exploits Richelot isogenies and products of elliptic curves and I doubt the attack can be expressed meaningfully without that language. This is the power of generalisation and extension. So what was necessary to find the attack was to have a community of scholars studying “esoteric” subjects like extending isogeny crypto to abelian surfaces.

10. Implications for PQ crypto

There is no doubt that this result will reduce confidence in isogenies. The sudden appearance of an attack this powerful shows that the field is not yet mature. The relatively recent attack by Ward Beullens on Rainbow has a similar impact on multivariate crypto. The correct response to this is not to attempt to minimise the impact, nor to reflexively declare the subject dead. Instead, we should keep our minds open and let the mathematicians work out the implications, wherever they lead. Personally, I can’t wait to see what Wouter and Thomas and all the isogenists come up with next!

— Steven Galbraith