Disorientation Faults in CSIDH | SpringerLink
Skip to main content
Springer Nature Link
Log in

Disorientation Faults in CSIDH

  • Conference paper
  • First Online:
Advances in Cryptology – EUROCRYPT 2023 (EUROCRYPT 2023)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14008))

Abstract

We investigate a new class of fault-injection attacks against the CSIDH family of cryptographic group actions. Our disorientation attacks effectively flip the direction of some isogeny steps. We achieve this by faulting a specific subroutine, connected to the Legendre symbol or Elligator computations performed during the evaluation of the group action. These subroutines are present in almost all known CSIDH implementations. Post-processing a set of faulty samples allows us to infer constraints on the secret key. The details are implementation specific, but we show that in many cases, it is possible to recover the full secret key with only a modest number of successful fault injections and modest computational resources. We provide full details for attacking the original CSIDH proof-of-concept software as well as the CTIDH constant-time implementation. Finally, we present a set of lightweight countermeasures against the attack and discuss their security.

The full version with additional material can be found at https://ia.cr/2022/1202.

Author list in alphabetical order; see https://ams.org/profession/leaders/CultureStatement04.pdf. This work began at the online Lorentz Center workshop “Post-Quantum Cryptography for Embedded Systems” held in February 2022. This research was funded in part by the European Commission through H2020 SPARTA, the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under SFB 1119 – 236615297 and under Germany’s Excellence Strategy—EXC 2092 CASA—390781972 “Cyber Security in the Age of Large-Scale Adversaries”, the Taiwan’s Executive Yuan Data Safety and Talent Cultivation Project (AS-KPQ-109-DSTCP), the German Federal Ministry of Education and Research (BMBF) under the project QuantumRISC (ID 16KIS1039), the Academia Sinica Investigator Award AS-IA-109-M01, the Dutch Research Council (NWO) through Gravitation-grant Quantum Software Consortium – 024.003.037, and a gender balance subsidy of the Faculty of Science, Radboud University, project number 6201362. This work was done in part while Tanja Lange was visiting the Simons Institute for the Theory of Computing. Date of this document: 2023-02-23.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 12583
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 15729
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Adj, G., Chi-Domínguez, J., Rodríguez-Henríquez, F.: Karatsuba-based square-root Vélu’s formulas applied to two isogeny-based protocols. J. Cryptogr. Eng. (2022). https://doi.org/10.1007/s13389-022-00293-y, https://ia.cr/2020/1109

  2. Adj, G., Chi-Domínguez, J.J., Mateu, V., Rodríguez-Henríquez, F.: Faulty isogenies: a new kind of leakage. Cryptology ePrint Archive, Paper 2022/153 (2022). https://ia.cr/2022/153

  3. Banegas, G., et al.: CTIDH: faster constant-time CSIDH. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2021(4), 351–387 (2021). https://doi.org/10.46586/tches.v2021.i4.351-387

  4. Banegas, G., Gilchrist, V., Smith, B.: Efficient supersingularity testing over GF(p) and CSIDH key validation. Math. Cryptol. 2(1), 21–35 (2022). https://journals.flvc.org/mathcryptology/article/view/132125

  5. Bernstein, D.J., De Feo, L., Leroux, A., Smith, B.: Faster computation of isogenies of large prime degree. In: Galbraith, S.D. (ed.) Proceedings of the Fourteenth Algorithmic Number Theory Symposium, pp. 39–55. Mathematics Sciences Publishers (2020). https://doi.org/10.2140/obs.2020.4.39, https://ia.cr/2020/341

  6. Bernstein, D.J., Hamburg, M., Krasnova, A., Lange, T.: Elligator: elliptic-curve points indistinguishable from uniform random strings. In: Sadeghi, A., Gligor, V.D., Yung, M. (eds.) 2013 ACM SIGSAC Conference on Computer and Communications Security, CCS 2013, Berlin, Germany, 4–8 November 2013, pp. 967–980. ACM (2013). https://doi.org/10.1145/2508859.2516734, https://ia.cr/2013/325

  7. Bernstein, D.J., Lange, T., Martindale, C., Panny, L.: Quantum circuits for the CSIDH: optimizing quantum evaluation of isogenies. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11477, pp. 409–441. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17656-3_15, https://ia.cr/2018/1059

  8. Beullens, W., Kleinjung, T., Vercauteren, F.: CSI-FiSh: efficient isogeny based signatures through class group computations. In: Galbraith, S.D., Moriai, S. (eds.) Advances in Cryptology - ASIACRYPT 2019–25th International Conference on the Theory and Application of Cryptology and Information Security, Kobe, Japan, 8–12 December 2019, Proceedings, Part I. Lecture Notes in Computer Science, vol. 11921, pp. 227–247. Springer, Heidelberg (2019). https://doi.org/10.1007/978-3-030-34578-5_9, https://ia.cr/2019/498

  9. Bonnetain, X., Schrottenloher, A.: Quantum security analysis of CSIDH. In: Canteaut and Ishai [13], pp. 493–522. https://doi.org/10.1007/978-3-030-45724-2_17, https://ia.cr/2018/537

  10. Campos, F., Kannwischer, M.J., Meyer, M., Onuki, H., Stöttinger, M.: Trouble at the CSIDH: protecting CSIDH with dummy-operations against fault injection attacks. In: 17th Workshop on Fault Detection and Tolerance in Cryptography, FDTC 2020, Milan, Italy, 13 September 2020, pp. 57–65. IEEE (2020). https://doi.org/10.1109/FDTC51366.2020.00015, https://ia.cr/2020/1005

  11. Campos, F., Krämer, J., Müller, M.: Safe-error attacks on SIKE and CSIDH. In: Batina, L., Picek, S., Mondal, M. (eds.) SPACE 2021. LNCS, vol. 13162, pp. 104–125. Springer, Cham (2022). https://doi.org/10.1007/978-3-030-95085-9_6

    Chapter  Google Scholar 

  12. Campos, F., Meyer, M., Reijnders, K., Stöttinger, M.: Patient zero and patient six: zero-value and correlation attacks on CSIDH and SIKE. Cryptology ePrint Archive, Paper 2022/904 (2022). https://ia.cr/2022/904

  13. Canteaut, A., Ishai, Y. (eds.): LNCS, vol. 12106. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45724-2

    Book  MATH  Google Scholar 

  14. Castryck, W., Decru, T.: An efficient key recovery attack on SIDH (preliminary version). Cryptology ePrint Archive, Paper 2022/975 (2022). https://ia.cr/2022/975

  15. Castryck, W., Lange, T., Martindale, C., Panny, L., Renes, J.: CSIDH: an efficient post-quantum commutative group action. In: Peyrin, T., Galbraith, S.D. (eds.) Advances in Cryptology - ASIACRYPT 2018–24th International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, QLD, Australia, 2–6 December 2018, Proceedings, Part III. Lecture Notes in Computer Science, vol. 11274, pp. 395–427. Springer, Heidelberg (2018). https://doi.org/10.1007/978-3-030-03332-3_15, https://ia.cr/2018/383

  16. Cervantes-Vázquez, D., Chenu, M., Chi-Domínguez, J.-J., De Feo, L., Rodríguez-Henríquez, F., Smith, B.: Stronger and faster side-channel protections for CSIDH. In: Schwabe, P., Thériault, N. (eds.) LATINCRYPT 2019. LNCS, vol. 11774, pp. 173–193. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-30530-7_9, https://ia.cr/2019/837

  17. Chávez-Saab, J., Chi-Domínguez, J., Jaques, S., Rodríguez-Henríquez, F.: The SQALE of CSIDH: sublinear Vélu quantum-resistant isogeny action with low exponents. J. Cryptogr. Eng. 12(3), 349–368 (2022). https://doi.org/10.1007/s13389-021-00271-w, https://ia.cr/2020/1520

  18. Chi-Domínguez, J., Rodríguez-Henríquez, F.: Optimal strategies for CSIDH. Adv. Math. Commun. 16(2), 383–411 (2022). https://doi.org/10.3934/amc.2020116, https://ia.cr/2020/417

  19. Childs, A.M., Jao, D., Soukharev, V.: Constructing elliptic curve isogenies in quantum subexponential time. J. Math. Cryptol. 8(1), 1–29 (2014). https://doi.org/10.1515/jmc-2012-0016, https://arxiv.org/abs/1012.4019

  20. Conway, J.H., Sloane, N.J.A.: Low dimensional lattices vii: coordination sequences. Proc. Roy. Soc. Lond. Ser. A 453, 2369–2389 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  21. Couveignes, J.M.: Hard Homogeneous Spaces. IACR Cryptology ePrint Archive 2006/291 (2006). https://ia.cr/2006/291

  22. De Feo, L., Galbraith, S.D.: SeaSign: compact isogeny signatures from class group actions. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11478, pp. 759–789. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17659-4_26, https://ia.cr/2018/824

  23. De Feo, L., Meyer, M.: Threshold Schemes from Isogeny Assumptions. In: Kiayias, A., Kohlweiss, M., Wallden, P., Zikas, V. (eds.) PKC 2020. LNCS, vol. 12111, pp. 187–212. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45388-6_7, https://ia.cr/2019/1288

  24. Delfs, C., Galbraith, S.D.: Computing isogenies between supersingular elliptic curves over \(\mathbb{F} _p\). Des. Codes Cryptogr. 78(2), 425–440 (2016). https://doi.org/10.1007/s10623-014-0010-1, https://arxiv.org/abs/1310.7789

  25. Gélin, A., Wesolowski, B.: Loop-abort faults on supersingular isogeny cryptosystems. In: Lange, T., Takagi, T. (eds.) PQCrypto 2017. LNCS, vol. 10346, pp. 93–106. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-59879-6_6, https://ia.cr/2017/374

  26. Hutchinson, A., LeGrow, J., Koziel, B., Azarderakhsh, R.: Further optimizations of CSIDH: a systematic approach to efficient strategies, permutations, and bound vectors. In: Conti, M., Zhou, J., Casalicchio, E., Spognardi, A. (eds.) ACNS 2020. LNCS, vol. 12146, pp. 481–501. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-57808-4_24, https://ia.cr/2019/1121

  27. Lai, Y.-F., Galbraith, S.D., Delpech de Saint Guilhem, C.: Compact, efficient and UC-secure isogeny-based oblivious transfer. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12696, pp. 213–241. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77870-5_8, https://ia.cr/2020/1012

  28. LeGrow, J.T., Hutchinson, A.: (Short Paper) Analysis of a strong fault attack on static/ephemeral CSIDH. In: Nakanishi, T., Nojima, R. (eds.) IWSEC 2021. LNCS, vol. 12835, pp. 216–226. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-85987-9_12, https://ia.cr/2020/1006

  29. Maino, L., Martindale, C.: An attack on SIDH with arbitrary starting curve. Cryptology ePrint Archive, Paper 2022/1026 (2022). https://ia.cr/2022/1026

  30. Meyer, M., Campos, F., Reith, S.: On lions and elligators: an efficient constant-time implementation of CSIDH. In: Ding, J., Steinwandt, R. (eds.) PQCrypto 2019. LNCS, vol. 11505, pp. 307–325. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-25510-7_17, https://ia.cr/2018/1198

  31. Meyer, Michael, Reith, Steffen: A faster way to the CSIDH. In: Chakraborty, Debrup, Iwata, Tetsu (eds.) INDOCRYPT 2018. LNCS, vol. 11356, pp. 137–152. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-05378-9_8, https://ia.cr/2018/782

  32. Onuki, H., Aikawa, Y., Yamazaki, T., Takagi, T.: (Short paper) A faster constant-time algorithm of CSIDH keeping two points. In: Attrapadung, N., Yagi, T. (eds.) Advances in Information and Computer Security - 14th International Workshop on Security, IWSEC 2019, Tokyo, Japan, August 28–30, 2019, Proceedings. Lecture Notes in Computer Science, vol. 11689, pp. 23–33. Springer (2019). https://doi.org/10.1007/978-3-030-26834-3_2, https://ia.cr/2019/353

  33. Peikert, C.: He gives C-sieves on the CSIDH. In: Canteaut and Ishai [13], pp. 463–492. https://doi.org/10.1007/978-3-030-45724-2_16, https://ia.cr/2019/725

  34. Robert, D.: Breaking SIDH in polynomial time. Cryptology ePrint Archive, Paper 2022/1038 (2022). https://ia.cr/2022/1038

  35. Rostovtsev, A., Stolbunov, A.: Public-key cryptosystem based on isogenies. IACR Cryptology ePrint Archive 2006/145 (2006), https://ia.cr/2006/145

  36. Tasso, É., De Feo, L., El Mrabet, N., Pontié, S.: Resistance of isogeny-based cryptographic implementations to a fault attack. In: Bhasin, S., De Santis, F. (eds.) COSADE 2021. LNCS, vol. 12910, pp. 255–276. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-89915-8_12, https://ia.cr/2021/850

  37. Ti, Y.B.: Fault attack on supersingular isogeny cryptosystems. In: Lange, T., Takagi, T. (eds.) PQCrypto 2017. LNCS, vol. 10346, pp. 107–122. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-59879-6_7, https://ia.cr/2017/379

  38. Udovenko, A., Vitto, G.: Breaking the \$IKEp182 challenge. IACR Cryptology ePrint Archive 2021/1421 (2021). https://ia.cr/2021/1421

  39. Vélu, J.: Isogénies entre courbes elliptiques. Comptes Rendus de l’Académie des Sciences de Paris 273, 238–241 (1971). https://gallica.bnf.fr/ark:/12148/cb34416987n/date

Download references

Author information

Authors and Affiliations

  1. Inria and Laboratoire d’Informatique de l’Ecole polytechnique, Institut Polytechnique de Paris, Palaiseau, France

    Gustavo Banegas

  2. University of Regensburg, Regensburg, Germany

    Juliane Krämer & Michael Meyer

  3. Eindhoven University of Technology, Eindhoven, The Netherlands

    Tanja Lange

  4. Academia Sinica, Taipei, Taiwan

    Tanja Lange & Lorenz Panny

  5. Radboud University, Nijmegen, The Netherlands

    Krijn Reijnders & Monika Trimoska

  6. University of Amsterdam and QuSoft, Amsterdam, The Netherlands

    Jana Sotáková

Authors
  1. Gustavo Banegas
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Juliane Krämer
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Tanja Lange
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Michael Meyer
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Lorenz Panny
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Krijn Reijnders
    View author publications

    You can also search for this author in PubMed Google Scholar

  7. Jana Sotáková
    View author publications

    You can also search for this author in PubMed Google Scholar

  8. Monika Trimoska
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Gustavo Banegas , Juliane Krämer , Tanja Lange , Michael Meyer , Lorenz Panny , Krijn Reijnders , Jana Sotáková or Monika Trimoska .

Editor information

Editors and Affiliations

  1. Bar-Ilan University, Ramat Gan, Israel

    Carmit Hazay

  2. Simula UiB, Bergen, Norway

    Martijn Stam

Rights and permissions

Reprints and permissions

Copyright information

© 2023 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Banegas, G. et al. (2023). Disorientation Faults in CSIDH. In: Hazay, C., Stam, M. (eds) Advances in Cryptology – EUROCRYPT 2023. EUROCRYPT 2023. Lecture Notes in Computer Science, vol 14008. Springer, Cham. https://doi.org/10.1007/978-3-031-30589-4_11

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-30589-4_11

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-30588-7

  • Online ISBN: 978-3-031-30589-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation