Paper 2023/1433
A polynomialtime attack on instances of MSIDH and FESTA
Abstract
The recent devastating attacks on SIDH rely on the fact that the protocol reveals the images $\varphi(P)$ and $\varphi(Q)$ of the secret isogeny $\varphi : E_0 \rightarrow E$ on a basis $\{P, Q\}$ of the $N$torsion subgroup $E_0[N]$ where $N^2 > \deg(\varphi)$. To thwart this attack, two recent proposals, MSIDH and FESTA, proceed by only revealing the images upto unknown scalars $\lambda_1, \lambda_2 \in \mathbb{Z}_N^\times$, i.e., only $\lambda_1 \varphi(P)$ and $\lambda_2 \varphi(Q)$ are revealed, where $\lambda_1 = \lambda_2$ for MSIDH and $\lambda_1 = \lambda_2^{1}$ for FESTA. Similar information is leaked in CSIDH since $\varphi$ maps the eigenspaces of Frobenius on $E_0$ to the corresponding eigenspaces on $E$. In this paper, we introduce a new polynomial time attack that generalizes the well known "lollipop" attack and analyze how it applies to MSIDH, FESTA and CSIDH. We show that MSIDH can be broken in polynomial time whenever $E_0$ or $E$ is $\mathbb{F}_p$rational, even when the endomorphism rings of $E_0$ and $E$ are unknown. This can be generalized to the case where the starting (or end) curve is not $\mathbb{F}_p$rational, but is connected to its Frobenius conjugate by an isogeny of small degree. For FESTA, where the curve $E_0$ is already $\mathbb{F}_p$rational, we obtain a polynomial time attack under the added requirement that at least one of the basis points $P, Q$ spans an eigenspace of Frobenius, of an endomorphism of low degree, or of a composition of both. We note that the current implementation of FESTA does not choose such a basis. Since it is always possible to construct an endomorphism, typically of large degree, with either $P, Q$ an eigenvector, we conclude that FESTA with overstretched parameters is insecure. Although the information leaked in CSIDH is very similar to FESTA, we show that our attack does not reveal any new information about the secret isogeny, i.e., we only learn that it is $\mathbb{F}_p$rational, which is a priori knowledge. Finally, we analyze if and how it would be possible to backdoor MSIDH and FESTA by choosing system parameters that look inconspicuous, but in fact reduce to the special cases above via a secret isogeny chosen by the adversary.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Published by the IACR in ASIACRYPT 2023
 Keywords
 isogenybased cryptographyFrobeniusMSIDHFESTACSIDH
 Contact author(s)

wouter castryck @ gmail com
frederik vercauteren @ gmail com  History
 20230924: approved
 20230921: received
 See all versions
 Short URL
 https://ia.cr/2023/1433
 License

CC BY
BibTeX
@misc{cryptoeprint:2023/1433, author = {Wouter Castryck and Frederik Vercauteren}, title = {A polynomialtime attack on instances of M{SIDH} and {FESTA}}, howpublished = {Cryptology ePrint Archive, Paper 2023/1433}, year = {2023}, note = {\url{https://eprint.iacr.org/2023/1433}}, url = {https://eprint.iacr.org/2023/1433} }