Efficient Key Recovery Attack on SIDH

Efficient key recovery attack on Supersingular Isogeny Diffie-Hellman (SIDH) protocol. It explores the vulnerability of the protocol and proposes a concrete solution. The attack leverages auxiliary points to solve the isogeny problem and reveals instances of the common secret key.

• Key recovery attack
• SIDH
• Supersingular Isogeny
• Diffie-Hellman
• vulnerability
• auxiliary points
• concrete solution
• common secret key

chaim Follow

Uploaded on Dec 21, 2023 | 5 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. An An efficient efficient key key recovery attack on SIDH recovery attack on SIDH Wouter Castryck, Thomas Decru A N T S A N T S X V X V University of Bristol, August 8 12, 2022

2. 1/16 1. 1. Supersingular Supersingular Isogeny Isogeny Diffie Diffie- -Hellman (SIDH) Hellman (SIDH) Jao, De Feo 2011: can we do Diffie-Hellman with subgroups and quotients? ? {abelian groups} chooses ? ? chooses ? ? Problem! Problem! This reveals ? ?, ??:? ?/? ? ? ? = ker?? ? = ker?? ? ?, ??:? ?/? ? ? ? ? common secret: ? ? + ? ( ? ?) ? ( ? ?) ??(?) ( ? ?) ? ( ? ?) ??(?)

3. 2/16 1. 1. Supersingular Supersingular Isogeny Isogeny Diffie Diffie- -Hellman (SIDH) Hellman (SIDH) Jao, De Feo 2011: can get around this by using auxiliary auxiliary points points ! ? {abelian groups} ??,??,??,?? ? chooses ? ? lets? = ??+ ??? chooses ? ? lets? = ??+ ??? Note: Note: Alice can compute ??? = ??( ??+ ???) ? ?, ????,???? as ???? + ???(??) ? ?, ????,???? (and likewise for Bob). common secret: ? ? + ? ( ? ?) ? ( ? ?) ??(?) ( ? ?) ? ( ? ?) ??(?)

4. 3/16 1. 1. Supersingular Supersingular Isogeny Isogeny Diffie Diffie- -Hellman (SIDH) Hellman (SIDH) choose prime ? = 2?3? 1 Jao, De Feo 2011: concrete proposal (simplified); ? ?2= ?3+ ? {supersingular ell.curves over ??2} ? 2?= ??,??, ? 3?= ??,?? chooses ? ? chooses ? ? lets? = ??+ ??? ?[3?] computes ?? ? ?/? as a composition of 3-isogenies lets? = ??+ ??? ?[2?] computes ?? ? ?/? as a composition of 2-isogenies ? ?, ????,???? ensures ensures that that torsion torsion is is defined defined over over ??2 ? ?, ????,???? common secret: ?- -invariant ? ?) ? ? ? ?) ??(?) invariant of ? + ? ( ? ?) ? ( ? ?) ??(?) ( (

5. 4/16 1. 1. Supersingular Supersingular Isogeny Isogeny Diffie Diffie- -Hellman (SIDH) Hellman (SIDH) Alice s isogeny ??:? in the supersingular supersingular 2- -isogeny ? ? can be viewed as a secret walk isogeny graph graph over ??. Ramanujan graph, so: rapid mixing (Pizer 1990) Key recovery Key recovery amounts to: Finding an instance of ?? (or equiv. ?) when being given ?, ? ?, ????, ??(??)

6. 4/16 1. 1. Supersingular Supersingular Isogeny Isogeny Diffie Diffie- -Hellman (SIDH) Hellman (SIDH) Bob s isogeny ??:? in the supersingular supersingular 3- -isogeny ? ? can be viewed as a secret walk isogeny graph graph over ??. Ramanujan graph, so: rapid mixing (Pizer 1990) Key recovery Key recovery amounts to: Finding an instance of ?? (or equiv. ?) when being given ?, ? ?, ????, ??(??) auxiliary points make for an atypical isogeny problem

7. 5/16 1. 1. Supersingular Supersingular Isogeny Isogeny Diffie Diffie- -Hellman (SIDH) Hellman (SIDH) Quick timeline: 1994 Shor: factoring 1997 Couveignes: isogeny-based key exchange from class group actions on ordinary elliptic curves (rejected and circulated among some experts), 2006 Rostovtsev-Stolbunov: rediscover and improve this construction and suggest suggest post post- -quantum quantum security security, 2006 Charles-Goren-Lauter: hash function from supersingular 2010 Childs-Jao-Soukharev: sub-exponential time quantum attack on Couveignes-Rostovtsev-Stolbunov with sub-exponential runtime, 2011 Jao-De Feo: respond with SIDH SIDH, 2016: SIDH-based system SIKE submitted to NIST standardization process, 2020: NIST selects SIKE as an alternate round-3 candidate, 2022: NIST announces winners and moves SIKE factoring and and discrete logs are easy discrete logs are easy for quantum computers, supersingular isogeny isogeny graphs graphs, an extra 4 extra 4th th round moves SIKE to to an round.

8. 6/16 1. 1. Supersingular Supersingular Isogeny Isogeny Diffie Diffie- -Hellman (SIDH) Hellman (SIDH) Main previous previous attacks: attacks: Claw-finding in the supersingular isogeny graph: ?(? 1 4) classical and ?(? 1 6) quantum Petit 2017, de Quehen et al. 2021: torsion-point attacks for unbalanced 2?,3? New attack: New attack: heuristic polynomial time, modulo precomputable integer factorization. We will focus on the easiest and most efficient case: recovery of Bob s secret 3?-isogeny, using auxiliary 2?-torsion point information.

9. 7/16 2. 2. Recovering Recovering Bob s Bob s secret secret key key: : idea idea Recall: given ?, ? ? ?,????,??(??), find ??. ? allows us to consider subgroup ??,???? , ??,???? ? ? ?? ?? ) (??,?? ) (??,?? ? ? This subgroup is isomorphic to 2?? 2??. ? ? What happens if we quotient it out via an isogeny? We want to do this within the category of principally principally polarized polarized abelian abelian surfaces surfaces e.g., imagine we can find ? such that ?23? 1 mod 2?, then the modified subgroup ??,??? for the construction construction of a certain cryptographic functionality from isogenies, so destruction destruction was never the intention! (Proof:?2? ??,?? ?2? ??? Historical note: seeds for this approach lie in a two-year old idea due to Thomas , ??,??? is maximally isotropic called a (2?,2?)-subgroup ?23?= 1.) ,??? = ?2? ??,?? ?2? ??,??

10. 8/16 2. 2. Recovering Recovering Bob s Bob s secret secret key key: : idea idea Resulting (2?,2?)-isogeny decomposes into ?(2,2)-isogenies. Typical case: (2,2) (2,2) (2,2) ? ? ?1 ?? However, in very exceptional situations (heuristic probability is ?( 1 ?)): (2,2) (2,2) (2,2) ? ? ? ? subgroup is called reducible reducible ?1

11. 9/16 2. 2. Recovering Recovering Bob s Bob s secret secret key key: : idea idea Characterization of reducible subgroups (Kani 1997): Definition: Definition: An isogeny isogeny diamond ? ? ? isogeny, ?1,?2 ker?, deg ? = #?1 #?2, ? = #?1+ #?2, ?1 ?2= {0}. diamond configuration configuration of order of order ? is a triplet ?,?1,?2 with Theorem Theorem (slightly informal) An (?,?)-subgroup of ? ? is reducible iff it comes from an isogeny diamond configuration of order ?. basically means: ?,?? ? , ?,?? ? for ? ? = ?,? and appropriate ? ?

12. 10/16 2. 2. Recovering Recovering Bob s Bob s secret secret key key: : idea idea Back to Bob s secret isogeny isogeny diamond of order diamond of order 2?: Force it into an isogeny degree 3? ?? it is (?? ?,ker ?,? ? ) ? ?? ?? ? ?? ?? = ??(??) = ??(??) ? degree ? = 2? 3? (assume positive) ? ??= ?(??) ??= ?(??) , ??,?? By Kani s theorem, the subgroup ??,?? ? ? is reducible ,?? were not not the images of ??,?? under a degree-3? isogeny, then not result in a reducible subgroup! Key Key idea with overwhelming probability this does not idea: : if ??

13. 11/16 2. 2. Recovering Recovering Bob s Bob s secret secret key key: : idea idea Leads to the following candidate-method for unveiling Bob s secret walk: secret 3-isogenies composing to ?? ?4 ?? ?3 ?1 ?2 ?? 1 ?? 1 ? ?? ?? ?1 ?2 ?3 ? ?? ?? = ??(??) = ??(??) ? ?1 ? ?1 ?1 ?1 isogeny ? ?= ?1 ?= ?1 ?(??) ?(??) if guess is correct, then: ?1 this isogeny maps ?1 so: buil build d auxiliary auxiliary isogeny of the subgroup of degree 2? 3? 1 ? connected to ? via isogeny of degree 3? 1 ? ?? isogeny ? and ??,?? ? ??= ?(?1 ??= ?(?1 and ?1 and check check reducibility reducibility , ??,?? ? ? . ? ?? ?) ?)

14. 11/16 2. 2. Recovering Recovering Bob s Bob s secret secret key key: : idea idea Leads to the following candidate-method for unveiling Bob s secret walk: secret 3-isogenies composing to ?? ?4 ?? ?3 ?1 ?2 ?? 1 ?? 1 ? ?? ?? ?1 ?2 ?3 ? ?? ?? = ??(??) = ??(??) ? ?2 ? ?2 ?2 ?2 isogeny ? ?= ?2 ?= ?2 ?(?1(??)) ?(?1(??)) of degree 2? 3? 2 ? ??= ?(?2 ??= ?(?2 ?) ?)

15. 11/16 2. 2. Recovering Recovering Bob s Bob s secret secret key key: : idea idea Leads to the following candidate-method for unveiling Bob s secret walk: secret 3-isogenies composing to ?? ?4 ?? ?3 ?1 ?2 ?? 1 ?? 1 ? ?? ?? ?1 ?2 ?3 ? ?? ?? = ??(??) = ??(??) ? ?3 ? ?2 ?3 ?3 isogeny ? ?= ?3 ?= ?3 ?(?2(?1(??))) ?(?2(?1??)) of degree 2? 3? 3 ? ??= ?(?3 ??= ?(?3 ?) ?) and so on

16. 12/16 3. 3. Constructing Constructing the the auxiliary auxiliary isogeny isogeny ? At iteration ?: want to construct an isogeny ?? 1 ? ? ? ?? ? = ? + ?[?] ? ? ? degree ? = 2? 3? ? 3? ? = isogeny ? with ker ? = ?(ker?) ? We know: ?. a path ? ? ?? that ? ?2= ?3+ ? comes equipped with ? ? ? ?,? ( ?,??) Hope: ? = 2? 3? ?= ?2+ ?2= (? + ??)(? ??) for certain integers ?,?.

17. 12/16 3. 3. Constructing Constructing the the auxiliary auxiliary isogeny isogeny ? Hope: ? = 2? 3? ?= ?2+ ?2= (? + ??)(? ??) for certain integers ?,?. Cost of deciding existence of ?,? and finding them: factoring factoring ?, Euclid s algorithm over ?[?] (special case of Cornacchia) Note: only only depends depends on system parameters on system parameters, not on concrete SIDH instance. If ? does not admit decomposition: create reducing ? (2?-torsion info implies 2? ?-torsion info), increasing ? ? (extend Bob s secret walk if wanted). create more more leeway leeway by In practice: need to guess first degree-3? component so that 2?> 3? ?, from that point onwards: can guess one degree-3 component at a time.

18. 13/16 3. 3. Constructing Constructing the What about other starting curves than ? ?2= ?3+ ? ? the auxiliary auxiliary isogeny isogeny ? Known Known endomorphism endomorphism ring: ring: SIKE uses ? ?2= ?3+ 6?2+ ? which carries automorphism 2?: same works more general: approach works if End(?) contains small-norm endomorphism totally general: rely on the KLPT algorithm (Kohel et al. 2014) Unknown Unknown endomorphism endomorphism ring: ring: auxiliary isogeny can always be constructed if ? = 2? 3? ? is smooth create more leeway by considering ? = ?2? ?+ ? 3? ? guess action on ?-torsion extend Bob s walk rely on smaller torsion info ? : leads to to ?( Fresh Fresh insight insight by by De De Feo Feo, , Wesolowski Wesolowski: leads ?) attack! attack!

19. 14/16 4. 4. Checking Checking reducibility reducibility ? ? (2,2) (2,2) (2,2) division by 0 during Richelot ? ? ? ?? ?? 1 ?1 gluing formulae due to Howe, Lepr vost, Poonen 2000 (2,2) ?? Richelot isogenies (classical and very efficient)

20. 15/16 5. 5. Implementation Implementation We have implemented the attack in Magma and it recovers Bob s key for SIKE level 1 in about 1 hour, SIKE level 2 in about 2 hours, SIKE level 3 in about 8 hours, SIKE level 5 in about 21 hours. Improved by a quite a factor in an ongoing SageMath effort by Pope et al. Generalization Generalization to to other No theoretical obstructions. Attacking Alice s key requires computing chains of (3,3)-isogenies: more cumbersome to implement but formulae are available For arbitrary smooth torsion: required tools seem available (see twitter thread by Damien Robert) other torsion torsion? ?

21. 16/16 5. An 5. An improvement improvement As communicated to us by Christophe Petit and Benjamin Wesolowski (see also Maino and Martindale, SageMath implementation by Pope et al.): possible to save many (2,2)-isogenies by completing the diagram ?? Now consider the factorization: ? ? ? ? ?? ?? ? ? ? ? ? ? ? ?? ? ? ? ?? degree ? = 2? 3? kernel can be verified to be 3??, ?? ? ? ? ? 2? so can simply evaluate ??!

22. Questions Questions? ? Thanks for listening!