New cryptanalysis of M-SIDH isogeny cryptography

Posted on October 4, 2023 by ellipticnews

This post is about the paper A polynomial time attack on instances of M-SIDH and FESTA by Wouter Castryck and Frederik Vercauteren.

As we all know, SIDH was broken in 2022 by using knowledge of exact images of torsion points under a secret isogeny. (For more details, see previous blog post, and another, and Quanta article.) Precisely, in SIDH the secret isogeny \phi : E_0 \to E_1 has known degree A, and one is given \phi(P), \phi(Q) \in E_1 where P, Q are a basis for E_0[B]. Here \gcd(A,B) = 1. The key technique is a result from Kani, which involves isogenies of Abelian varieties of dimension more than one.

In response, several papers proposed ways to fix it by “blinding” the images of the torsion points and/or the degree of the isogeny \phi. The M-SIDH paper proposed to hide the degree of \phi and to blind the points as S = \lambda \phi(P), T = \lambda \phi(Q) for some secret \lambda that squares to one modulo B. FESTA is a bit more general, and I won’t talk about it in detail here.

Sections 4.2 and 4.3 of the M-SIDH paper show an attack on the scheme for special curves E_0 using “lollipop” maps (see below). Section 5 of the M-SIDH paper explains that hiding the degree adds no security, in the sense that one can reduce the problem to a case of known degree. Hence whatever is the security, it is coming from the fact that \lambda is unknown to an attacker.

The reason why exact knowledge of the torsion is needed for the SIDH attacks is because these attacks set up an isogeny F of Abelian varieties that is defined by an explicit kernel subgroup in terms of \phi(P), \phi(Q) and also the exact images of P, Q under some other (known) isogeny. When given only \lambda \phi(P), \lambda \phi(Q) the kernel is wrong and the isogeny F is not the desired map (indeed, it may not even be an isogeny of polarized abelian varieties). So it was plausible that M-SIDH and FESTA might resist attack.

Castryck and Vercauteren show a more general attack strategy on these proposals than considered in the previous works. The paper builds on the well-known idea of “lollipops” (the terminology was introduced in this paper by de Quehen, Kutas, Leonardi, Martindale, Panny, Petit, and Stange). In isogeny crypto a lollipop is formed by taking an isogeny from one curve E to another curve E_0, applying an endomorphism on E_0, and then applying the dual map back to the original curve E, so that the whole composition is cyclic. See the picture below from the paper linked above. Be warned that lollipops are not as sweet as they sound!

The obvious idea is to try to do a Kani-type attack on the isogeny \phi : E_0 \to E_1, but this seems to be prevented by the blinding. The clever idea is to do Kani-type attack on a different isogeny \psi : E_1 \to E_1^{(p)} which uses the images of the blinded points S, T rather than the original points on E_0. The map \psi is a sort-of lollipop map with \phi, but one can also evaluate it (up to known scalar multiple) as the Frobenius map. Hence one can compute \psi(S), \psi(T). Knowing these points, one can mount the Kani-type attack and learn \psi.

We present one of the cases that is handled in the paper. Suppose that E_0 is defined over \mathbb{F}_p. We have E_1 and want to compute the unknown map \phi : E_0 \to E_1. Suppose that \phi is not defined over \mathbb{F}_p. Consider the Frobenius maps \sigma_1 : E_1 \to E_1' and \sigma_0 : E_0 \to E_0. Let \phi' : E_0 \to E_1' be the “pushforward” of the unknown map \phi , which is just the Frobenius conjugate of \phi. We have \phi' \circ \sigma_0 = \sigma_1 \circ \phi. We don’t know \phi or \phi', but we can consider the composition, where \hat{\phi} denotes the dual isogeny,

\psi = \phi' \circ \hat{\phi} .

Note that the degree of \psi is A^2. Further, we generally expect \psi to be cyclic, since for R \in E_1[A] we have \hat{\phi}(R) \in ker( \phi ) which is not usually equal to ker( \phi' ) = \sigma_0( ker( \phi )).

The key result is Lemma 3 of the paper. Let S = \lambda \phi(P), T = \lambda \phi(Q) \in E_1. Let S' = \sigma_1(S), T' = \sigma_1(T) \in E_1', which an attacker can compute. The lemma shows that from these points one can determine \psi(S), \psi(T) exactly. I emphasise the main point: the scalar multiplications by \lambda somehow don’t matter, as we are directly attacking the points S, T. To finish the attack, one runs the previous SIDH attack on \psi, using Kani’s technique, to learn it completely. Finally, evaluate the isogeny on points of order A to learn \phi (since \psi is cyclic we can expect to learn the kernel we desire).

This gives an attack on M-SIDH when the starting curve E_0 is defined over \mathbb{F}_p. The paper shows a more general attack that covers some more special cases of E_0. The general case of M-SIDH is not yet broken, but the paper discusses some strategies (and defenses) against a malicious party installing a backdoor in E_0.

The paper then studies a special case of FESTA, which is not proposed in the FESTA paper, and shows an attack. The paper says “FESTA with overstretched parameters is insecure”. But I believe no proposed case of FESTA is broken by this paper. The paper remarks that “similar information” is leaked in CSIDH, since \phi maps the eigenspaces of Frobenius on E_0 to the corresponding eigenspaces on E. However, there is no efficient attack known on CSIDH either. More generally, the information you get for free from an orientation does not seem to lead to any new attack.

While on the subject of CSIDH, these papers also do not break CSIDH:

Both papers are about knowledge of one endomorphism. The first shows that if one can generate one endomorphism for any random supersingular curve, then there is an efficient algorithm to compute the endomorphism ring (and hence solve isogeny problems) for any fixed supersingular curve. It sounds like this would break CSIDH, since in CSIDH we do know one endomorphism. But that’s not how the algorithm works. The idea is to take a target curve E and generate random isogenous curves E', find an endomorphism on each curve E', and then pull these endomorphisms back to E. This then allows to compute End(E). But the one known endomorphism on every CSIDH curve does not allow to make this approach work. The second paper is about extending the known attacks on CSIDH to other curves, and it does not change the current understanding of the security of CSIDH.

What can we conclude from this about the security of fixes to SIDH, such as M-SIDH and FESTA? My personal opinion is that it seems unlikely that such simple tweaks to SIDH are enough to be secure. But I await more research to understand this better. On the other hand, CSIDH continues to withstand scrutiny by cryptanalysts, and no attacks are known that are better than the well-known subexponential-quantum-time Kuperberg algorithm.

— Steven Galbraith

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a comment