On the supersingular GPST attack

Andrea Basso; Fabien Pazuki

doi:10.1515/jmc-2021-0020

Open Access Published by De Gruyter September 8, 2021

On the supersingular GPST attack

Andrea Basso and Fabien Pazuki

From the journal Journal of Mathematical Cryptology

https://doi.org/10.1515/jmc-2021-0020

Abstract

The main attack against static-key supersingular isogeny Diffie–Hellman (SIDH) is the Galbraith–Petit–Shani–Ti (GPST) attack, which also prevents the application of SIDH to other constructions such as non-interactive key-exchange. In this paper, we identify and study a specific assumption on which the GPST attack relies that does not necessarily hold in all circumstances. We show that in some circumstances the attack fails to recover part of the secret key. We also characterize the conditions necessary for the attack to fail and show that it rarely happens in real cases. We give a link with collisions in the Charles-Goren-Lauter (CGL) hash function.

Keywords: isogenies; supersingular elliptic curves; modular invariants

MSC 2010: 14H52; 14K02; 11T71; 94A60; 81P94; 65P25

1 Introduction

In 2011, Jao and De Feo [1] introduced supersingular isogeny Diffie–Hellman (SIDH), a post-quantum key exchange protocol that mimics the Diffie–Hellman protocol in the settings of isogenies between supersingular curves. Its security relies on the hardness of the supersingular isogeny path finding problem with additional torsion image information. A detailed study of its security is reported in ref. [2]. The authors also report three attacks under different scenarios. The first attack, the so-called GPST attack, is an active attack against static keys, where one of the two parties sends maliciously chosen torsion information that lead to the protocol failing or succeeding based on a single bit of the secret key of the other party. This can then be used to fully recover the secret key by repeating the process for each bit of the key.

The problem can be solved by applying the Fujisaki–Okamoto transform [3] to obtain a CCA-secure key-encapsulation mechanism called SIKE. However, this prevents static–static key exchanges that can be used to create a non-interactive key exchange (NIKE) protocol. Indeed, developing an efficient SIDH-based NIKE remains partially an open problem. There have been some proposed solutions, such as k -SIDH [4], but their performance and communication costs are almost impractically large.

The GPST attack thus plays an essential role in the security and the development of SIDH and other isogeny-based protocols. In this paper, we identify a specific property of the j -invariant of elliptic curves that is used by the GPST attacks which is not guaranteed to hold in all circumstances. In such circumstances, we show the attack fails to recover the secret key. We then characterize these specific circumstances and show they occur with negligible probability in real cases. We conclude by analyzing special starting curves, such as those used in SIDH.

1.1 Preliminaries

For an elliptic curve E defined over a field k , we denote the neutral element of the elliptic curve by O and the modular invariant of E by j ( E ) . The invariant is an element of k that characterizes the k ¯ -isomorphism class of E . For P ∈ E ( k ) rational over k , we denote by ⟨ P ⟩ the subgroup of E ( k ) generated by P .

The parameters of the SIDH protocol are the following:

A prime p = 2 n 3 m f − 1 , where n , m , f are natural numbers, f is small and 2 n ≈ 3 m .
A supersingular elliptic curve E 0 defined over F p 2 .
Points P A , Q A ∈ E 0 which form a basis of E 0 [ 2 n ] and points P B , Q B ∈ E 0 which form a basis of E 0 [ 3 m ] .

We refer the reader to the original paper [2] for the presentation of the attack. We introduce here the two assumptions that are required for the GPST attack to take place:

Alice uses a static key ( a 1 , a 2 ) . The values a 1 , a 2 are elements of Z ∕ 2 n Z , not both divisible by 2.
The attacker has access to an oracle O such that, if E , E ′ denote supersingular elliptic curves defined over F p 2 and R , S denote any two points on E ,

(1) O ( E , R , S , E ′ ) = true , if j ( E / ⟨ [ a 1 ] R + [ a 2 ] S ⟩ ) = j ( E ′ ) , false , otherwise .
Such an oracle can be realized in practice by having a mechanism in place that ensures the two parties obtain the same shared key.

The attacker does not need any additional information, which makes the GPST attack one of the most powerful attacks against SIDH known in the literature.

2 Attacking the attack

Alice’s static key ( a 1 , a 2 ) is always equivalent (i.e., it leads to the same shared secret) to a key of the form ( 1 , α ) or ( α , 1 ) , where α is again an element of Z ∕ 2 n Z [2, Lemma 2.1]. Without loss of generality, we may assume we are in the former case.

Each iteration of the GPST attack relies on the following implication, used in the paragraph first step of the attack of ref. [2]:

(2) ( j ( E / ⟨ T 1 ⟩ ) = j ( E / ⟨ T 2 ⟩ ) ) ⇒ ( ⟨ T 1 ⟩ = ⟨ T 2 ⟩ )

to recover a single bit of the key. In particular, the oracle query (1) is used to recover whether ⟨ R ′ + α S ′ ⟩ is equal to ⟨ R + α S ⟩ , where R , S , R ′ , S ′ are points on an elliptic curve computed by the attacker. The points R ′ and S ′ are chosen such that ⟨ R ′ + α S ′ ⟩ = ⟨ R + α S ⟩ implies the i th bit α i of the key is a zero-bit. Thus, if the oracle returns true, then α i = 0 , otherwise α i = 1 .

However, implication (2) does not hold in all cases, because there exist pairs of elliptic curves E 1 , E 2 with multiple isogenies between them. Thus, if ϕ 1 and ϕ 2 are distinct cyclic isogenies between E 1 and E 2 and K 1 and K 2 are their respective kernels, we have that E 1 / K 1 is isomorphic to E 1 / K 2 because they are both isomorphic to E 2 , but K 1 and K 2 may not be equal and need not even be isomorphic. Over Q , a classical example can be found in [5, page 110], namely the pair ( E , E ) , where E is the curve defined over Q with j ( E ) = 8,000 , which is given by the affine Weierstrass equation y 2 = x 3 + 4 x 2 + 2 x . This curve E admits a rational 2-isogeny φ to itself (hence cyclic, and given explicitly in loc. cit.), and one computes j ( E / ker φ ) = 8,000 = j ( E ) , hence E and E / ker φ are in fact Q ¯ -isomorphic, but clearly ker φ ≠ { O } .

Over a finite field of characteristic p > 0 , if one starts with a supersingular elliptic curve E , then for any prime ℓ ≠ p , for any positive integer m and for any cyclic subgroup G of order ℓ m , the elliptic curve E / G will also be supersingular, because there are still no points of order p on E / G . As there are only finitely many supersingular curves over F ¯ p (see for instance [6, Theorem 4.1, pages 148–149]), there exist pairs of cyclic groups ( G 1 , G 2 ) where G 1 and G 2 are not isomorphic, such that E / G 1 is isomorphic to E / G 2 . This argument is used to prove that the endomorphism ring of supersingular elliptic curves is an order in a quaternion algebra, see [6, page 146] or [7, page 267].

Let us give now a detailed example where the GPST attack fails to recover the private key of a SIDH key exchange. The example was found through direct search with small primes and it has been experimentally validated.

Example 1

Let p = 2 5 3 3 − 1 = 863 be a prime and k be the finite field F p 2 , considered as F p ( β ) , where β satisfies the quadratic equation β 2 − β + 5 = 0 . Let E 0 be the supersingular elliptic curve with affine Weierstrass model y 2 = x 3 + ( 531 β + 538 ) x + ( 720 β + 375 ) over k . Consider the points

P A = ( 834 β + 726 , 642 β + 130 ) , Q A = ( 583 β + 276 , 180 β + 854 ) , P B = ( 254 β + 697 , 516 β + 268 ) , Q B = ( 753 β + 317 , 234 β + 532 ) .

The points P A , Q A form a basis of E 0 [ 2 5 ] , and P B , Q B form a basis of E 0 [ 3 3 ] . Let Alice’s key be of the form ( 1 , α ) , with α = 10 (written in base ten). The value α can also be expressed in bits as 1010 (written in base two). From now on, by a slight abuse of notation we refer to α as the key.

Let us now carry on the GPST attack. Assume the randomly generated values b 1 , b 2 are b 1 = 1 , b 2 = 6 (for simplicity, we assume b 1 and b 2 stay constant across iterations, but we only need b 1 = 1 , b 2 = 6 in the second round for the attack to fail). Let ϕ A be the isogeny with kernel K A = ⟨ P A + [ α ] Q A ⟩ . Then E A = E 0 / K A has affine Weierstrass model y 2 = x 3 + ( 40 β + 535 ) x + ( 720 β + 768 ) . Let us begin the attack and let ϕ B be the isogeny with kernel K B = ⟨ P B + [ 6 ] Q B ⟩ . Thus, E B = E 0 / K B has affine Weierstrass model y 2 = x 3 + 105 x + 254 . Furthermore, we have

R = ϕ B ( P A ) = ( 151 β + 257 , 594 β + 2 ) , S = ϕ B ( Q A ) = ( 98 β + 386 , 286 β + 58 ) .

Note that since the degree of ϕ B is coprime with the order of P A and Q A , the points R and S have also order 2 5 .

The first iteration of the attack starts by computing

θ 0 = ( 1 + 2 4 ) − 1 ( mod 2 5 ) = 7 , R 0 ′ = [ θ 0 ] R = ( 527 β + 129 , 700 β + 163 ) , S 0 ′ = [ θ 0 ] [ 1 + 2 4 ] S = ( 164 β + 377 , 566 β + 641 ) .

It then proceeds by querying the oracle with O ( E B , R 0 ′ , S 0 ′ , E A B ) = E B / ⟨ ϕ A ( P B ) + [ 6 ] ϕ A ( Q B ) ⟩ . The curve E A B : y 2 = x 3 + 698 x + ( 516 β + 605 ) has j -invariant 117. The curve E B / ⟨ R 0 ′ + [ α ] S 0 ′ ⟩ also has j -invariant 117, thus the oracle response is true and the first (least significant) bit of the key is a zero-bit. Hence, the attack correctly obtains the first bit of the key.

For the second round, the attacker computes

θ 1 = ( 1 + 2 3 ) − 1 ( mod 2 5 ) = 5 , R 1 ′ = [ θ 1 ] R = ( 97 β + 261 , 795 β + 545 ) , S 1 ′ = [ θ 1 ] [ 1 + 2 3 ] S = ( 718 β + 214 , 450 β + 844 ) ,

and queries the oracle on O ( E B , R 1 ′ , S 1 ′ , E A B ) . As before, the curves E A B and E B / ⟨ R 1 ′ + [ α ] S 1 ′ ⟩ both have j -invariant 117, thus the oracle responds true. Hence, this time the attacker incorrectly deduces the second bit of the key to be zero.

Brute-forcing the remaining bits does not yield any solution, since there is no key α ending with two zero-bits (00) such that E 0 / ⟨ P A + [ α ] Q A ⟩ is isomorphic to E A .

Note that each iteration of the attack depends on the previous one since the modified value R i ′ of iteration i + 1 relies on K i , whose last bit is obtained in the i th iteration. To see how the error propagates, assume the attack fails at iteration i . Thus α i , the i th bit of the key, is a one-bit but the attacker deduces it to be a zero-bit. It follows that K i = K i − 1 for the attacker since prepending zero-bits does not affect the value of K . The attacker then computes the points

R i ′ = [ θ ] R − [ θ ] [ 2 n − i − 1 K i − 1 ] S , S i ′ = [ θ ] [ 1 + 2 n − i − 1 ] S

and queries the oracle on O ( E B , R i ′ , S i ′ , E A B ) .

Thus, omitting θ since it does not affect the subgroup, we have

⟨ R i ′ + [ α ] S i ′ ⟩ = ⟨ R + [ − 2 n − i − 1 K i − 1 + α ( 1 + 2 n − i − 1 ) ] S ⟩ = ⟨ R + [ α ] S + [ − 2 n − i − 1 K i − 1 + 2 n − i − 1 ( K i − 1 + 2 i − 1 + 2 i α i + 2 i + 1 α ′ ) ] S ⟩ = ⟨ R + [ α ] S + [ 2 n − 2 + 2 n − 1 α i ] S ⟩ ≠ ⟨ R + [ α ] S ⟩ .

To see why the inequality in the last line holds, consider that if the two cyclic subgroups are the same, their generators must be scalar multiples of each other. Assume then R + [ α ] S + [ 2 n − 2 + 2 n − 1 α i ] S = [ h ] ( R + [ α ] S ) for a natural integer h . The linear independence of R and S implies that R = [ h ] R , which means h ≡ 1 mod 2 n . Thus, the equality on S implies that [ 2 n − 2 + 2 n − 1 α i ] S = O , which is impossible because α i ∈ { 0 , 1 } and we have neither 0 ≢ 2 n − 2 mod 2 n nor 0 ≢ − 2 n − 1 mod 2 n . This means that the oracle will return false (unless the two subgroups, ⟨ R + [ α ] S ⟩ and ⟨ R i ′ + [ α ] S i ′ ⟩ , give rise again to two isogenies with isomorphic codomain).

The subsequent iterations further propagate the error and the oracle will respond false to every further query (unless, again, the isogenies with different kernels have the same codomain, which is believed to be a rare occurrence). Thus, if the attack fails at the i th iteration, all the following key bits are deduced to be a one-bit. This allows the attacker to approximately identify the part of the key that has been correctly deduced and target, with a different choice of ϕ B , only the remaining part.

3 Failure case conditions

3.1 General analysis and a lemma for 1,728

In this paragraph, we investigate the specific conditions that lead to the attack failing. Example 1 in the previous section establishes that there exist cases where the attack fails. The following are sufficient conditions (when considered together) for the attack to fail at the i th iteration of the attack, when we choose 1 ≤ i < n − 3 (the attack brute-forces the last three bits of the key and thus cannot fail after n − 3 ):

There exist two distinct isogenies ϕ 1 and ϕ 2 of degree 2 n between E B and E A B .
One has R + [ α ] S = P 1 and R i ′ + [ α ] S i ′ = P 2 , where P 1 and P 2 are generators of the kernel of ϕ 1 and ϕ 2 , respectively.
The i th key bit α i is 1.

From the point of view of the attacker, determining whether condition (i) is satisfied is computationally hard since it is hard to compute isogenies between two given curves. Moreover, the points P 1 and P 2 are dependent on the key α and thus unknown to the attacker. Hence, while the attacker influences the points P 1 and P 2 by choosing ϕ B , they cannot know whether his choice of ϕ B would cause the attack to fail.

Condition (ii) ensures that the attack is taking place in the case where the points R and S give rise to the isogenies considered in the first condition. Given the points P 1 , P 2 , we have

P 1 = R + [ α ] S , P 2 = R i ′ + [ α ] S i ′ = [ θ i ] R + [ θ i ] [ α + α i 2 n − i − 1 ] S ,

thus [ θ i ] P 1 − P 2 = [ θ i ] [ 2 n − i − 1 ] [ α i ] S = [ θ i ] [ 2 n − i − 1 ] S (because of condition (iii)). If a θ i exists such that the previous equation is satisfied, then suitable points R and S also exist.

Condition (iii) is necessary because the attack fails by incorrectly deducing a zero-bit instead of a one-bit.

If ϕ 1 and ϕ 2 are such isogenies, then ϕ 1 ˆ ∘ ϕ 2 is an endomorphism of degree 2 2 n in End ( E B ) , and if it is not a classical multiplication, this gives rise to non-trivial short cycles. Thus, studying the endomorphism ring of the starting curve can reveal useful information on the conditions that lead to failures of the attack.

One curve that is often used is the curve with j -invariant 1,728. In real cases, we have that 2 n ≈ p 1 / 2 . Thus, thanks to a remark from the referee, we can show that when the curve E B has j -invariant 1,728 multiple isogenies between E B and E A B are possible when the isogeny paths only overlap in E B and E A B . We do so by showing that multiedges shorter than 2 n are not possible.

Lemma 1

Let p be a prime such that p ≡ 3 mod 4 and p + 1 4 > 2 2 e for some integer e , and let E be a supersingular curve over F p 2 . If j ( E ) = 1,728 , there is no endomorphism of norm 2 2 e in End ( E ) besides the classical multiplications.

Proof

By Lemma 2 of [8], End ( E ) is isomorphic to an order in a quaternion algebra B ( − 1 , − p ) . The order has basis 1 , i , 1 + j 2 , i 1 + j 2 , where i 2 = − 1 and j 2 = − p . Let ϕ be an endomorphism of E of norm 2 2 e , and write ϕ = w + x i + y 1 + j 2 + z i 1 + j 2 . The norm of ϕ is given by w 2 + x 2 + ( y 2 + z 2 ) p + 1 4 . Thus, y 2 + z 2 = 0 , which implies y = z = 0 and w 2 + x 2 = 2 2 e . By considering the last equation modulo 4, we have that w ≡ x ≡ 0 since the only squares modulo 4 are { 0 , 1 } . This means both sides can be divided by 4, and if the process is repeated e times, we see that either w = 2 e and x = 0 , or w = 0 and x = 2 e .□

3.2 Collisions in the CGL hash function and SIDH parameters

There is an important link between these failures of the GPST attack and the following work, which helps in understanding when these failures occur. From a cryptographic perspective, the CGL function [9] is a hash function based on isogenies between supersingular curves. It constructs a hash value by traveling the supersingular graph, choosing the next curve at each step depending on a single bit of the input. The mixing property of the supersingular graphs ensures the desired properties of hash functions. We note that having two distinct isogenies of the same degree between two supersingular curves leads to a collision in the CGL hash function.

The authors of ref. [9] showed that such collisions can be avoided by carefully choosing the base prime p . As explained in their paragraph 5.3.4, if a cycle is represented by an element x of End ( E ) of norm ℓ 2 e , the polynomial X 2 + Tr ( x ) X + ℓ 2 e is irreducible and there are only finitely many values of Tr ( x ) such that the discriminant Tr ( x ) 2 − 4 ℓ 2 e is negative. For each of these values, we obtain an imaginary quadratic field generated by the quadratic polynomial. It is thus sufficient to pick a prime p which splits in all those fields to guarantee that no cycle of length 2 e exists. This can be done for sufficiently many values of e to guarantee that no short cycle exists.

More specifically to SIDH, Ghantous [10] has analyzed the presence of multiedges in the supersingular ℓ-isogeny graph. Theorem 3.2 of ref. [10] shows that the 2-isogeny graph has no multiedges only if the base prime p ≡ 1 , 121 , 169 , 289 , 361 , 529 mod 840 . Similar modular conditions exist for the 3-isogeny graph. However, they do not apply to SIDH parameters. Ghantous [10] has also proved that the ℓ -isogeny graph has at most ℓ 2 + ℓ / 4 multiedges. Thus, there is an upper bound in the 2-isogeny graph of 4 multiedges and 9 multiedges in the 3-isogeny graph. In the case of SIDH parameters for the two lowest security levels, Onuki et al. [11] have shown that there are only two cycles in the 3-isogeny graph in SIKEp434, and there are no cycles in the other graphs in SIKEp434 and SIKEp503. Thus in these real cases, the GPST attack may never fail or fail in negligible cases.

Acknowledgements

Both authors thank Christophe Petit and Christophe Ritzenthaler for interesting feedback. The authors also thank the reviewers for the useful suggestions. The second author is a member of the project ANR-17-CE40-0012 Flair and ANR-20-CE40-0003 Jinvariant.

Conflict of interest: Authors state no conflict of interest.

References

[1] Jao D, De Feo L. Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. In: Proceedings of the 4th International Conference on Post-Quantum Cryptography, PQCrypto’11. Berlin, Heidelberg: Springer-Verlag; 2011. p. 19–34. 10.1007/978-3-642-25405-5_2Search in Google Scholar

[2] Galbraith S, Petit C, Shani B, Ti YB. On the security of supersingular isogeny cryptosystems. In: Advances in Cryptology - ASIACRYPT. Vol. 10031. Berlin, Heidelberg: Springer; 2016. p. 63–91. 10.1007/978-3-662-53887-6_3Search in Google Scholar

[3] Hofheinz D, Hövelmanns K, Kiltz E. A modular analysis of the Fujisaki-Okamoto transformation. In: Theory of Cryptography – 15th International Conference, TCC 2017, Lecture Notes in Computer Science. Vol. 10677. Springer; 2017. p. 341–71. 10.1007/978-3-319-70500-2_12Search in Google Scholar

[4] Azarderakhsh R, Jao D, Leonardi C. Post-quantum static-static key agreement using multiple protocol instances. In: Selected Areas in Cryptography - SAC 2017. Vol. 10719. Cham: Springer International Publishing; 2017. p. 45–63. 10.1007/978-3-319-72565-9_3Search in Google Scholar

[5] Silverman J. Advanced topics in the arithmetic of elliptic curves. New York: GTM Springer-Verlag; 1994. p. 151. 10.1007/978-1-4612-0851-8Search in Google Scholar

[6] Silverman J. The arithmetic of elliptic curves. Second edition, New York: GTM Springer-Verlag; 1992. p. 106. Search in Google Scholar

[7] Husemöller D. Elliptic curves. Second edition. New York: GTM Springer-Verlag; 2004. p. 111. Search in Google Scholar

[8] Kohel DR, Lauter K, Petit C, Tignol JP. On the quaternion-isogeny path problem. LMS J Comput Math. 2014:17(suppl A):418–32. 10.1112/S1461157014000151Search in Google Scholar

[9] Charles DX, Goren EZ, and Lauter KE. Cryptographic hash functions from expander graphs, J Cryptol. 2009;22(1):93–113. 10.1007/s00145-007-9002-xSearch in Google Scholar

[10] Ghantous W. Loops, multi-edges and collisions in supersingular isogeny graphs. 2021. arXiv:2101.08761. 10.3934/amc.2022038Search in Google Scholar

[11] Onuki H, Aikawa Y, Takagi T. The existence of cycles in the supersingular isogeny graphs used in SIKE, Cryptology ePrint Archive, Report 2020/439. 2020. https://eprint.iacr.org/2020/439Search in Google Scholar

Received: 2020-02-11

Accepted: 2021-08-01

Published Online: 2021-09-08

This work is licensed under the Creative Commons Attribution 4.0 International License.

On the supersingular GPST attack

Abstract

1 Introduction

1.1 Preliminaries

2 Attacking the attack

Example 1

3 Failure case conditions

3.1 General analysis and a lemma for 1,728

Lemma 1

Proof

3.2 Collisions in the CGL hash function and SIDH parameters

Acknowledgements

References

Journal and Issue

Articles in the same Issue