[en] We report a break of the \$IKEp182 challenge using a meet-in-the-middle attack strategy improved with multiple SIKE-specific optimizations. The attack was executed on the HPC cluster of the University of Luxembourg and required less than 10 core-years and 256TiB of high-performance network storage (GPFS). Different trade-offs allow execution of the attack with similar time complexity and reduced storage requirements of only about 70TiB.
Centre de recherche :
ULHPC - University of Luxembourg: High Performance Computing
Disciplines :
Sciences informatiques
Auteur, co-auteur :
UDOVENKO, Aleksei ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > Cryptolux ; CryptoExperts
VITTO, Giuseppe ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > Cryptolux
Co-auteurs externes :
yes
Langue du document :
Anglais
Titre :
Revisiting Meet-in-the-Middle Cryptanalysis of SIDH/SIKE with Application to the $IKEp182 Challenge
Adj, G., Cervantes-Vázquez, D., Chi-Domínguez, J.J., Menezes, A., Rodríguez-Henríquez, F.: On the cost of computing isogenies between supersingular elliptic curves. In: Cid, C., Jacobson, M.J., Jr. (eds.) SAC 2018. LNCS, vol. 11349, pp. 322–343. Springer, Heidelberg (2019). https://doi.org/10.1007/978-3-030-10970-7_15
Bernstein, D.: Cost analysis of hash collisions: will quantum computers make SHARCS obsolete? In: SHARCS’09 Workshop Record (Proceedings 4th Workshop on Special-purpose Hardware for Attacking Cryptograhic Systems, Lausanne, Switserland, 9-10 September 2009), pp. 105–116 (2009)
Costello, C., Hisil, H.: A simple and compact algorithm for SIDH with arbitrary degree isogenies. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10625, pp. 303–329. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70697-9_11
Costello, C., Longa, P., Naehrig, M.: Efficient algorithms for supersingular isogeny Diffie-Hellman. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9814, pp. 572–601. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53018-4_21
Costello, C., Longa, P., Naehrig, M., Renes, J., Virdia, F.: Improved classical cryptanalysis of SIKE in practice. In: Kiayias, A., Kohlweiss, M., Wallden, P., Zikas, V. (eds.) PKC 2020. LNCS, vol. 12111, pp. 505–534. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45388-6_18
Feo, L.D., Jao, D., Plût, J.: Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. J. Math. Cryptol. 8(3), 209–247 (2014)
Galbraith, S.D.: Constructing isogenies between elliptic curves over finite fields. LMS J. Comput. Math. 2, 118–138 (1999)
Jao, D., et al.: Supersingular Isogeny Key Encapsulation. NIST Post-Quantum Cryptography Round 3 - Alternate Candidate (2020). https://sike.org/files/SIDH-spec.pdf
Jao, D., De Feo, L.: Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. In: Yang, B.-Y. (ed.) PQCrypto 2011. LNCS, vol. 7071, pp. 19–34. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25405-5_2
Longa, P., Wang, W., Szefer, J.: The cost to break SIKE: a comparative hardware-based analysis with AES and SHA-3. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12827, pp. 402–431. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84252-9_14
Microsoft Research: SIKE Cryptographic Challenge (2021). https://www.microsoft.com/en-us/msrc/sike-cryptographic-challenge
National Institute of Standards and Technology (NIST): Post-Quantum Cryptography Standardization (2016–2022). https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization
Renes, J.: Computing isogenies between Montgomery curves using the action of (0, 0). In: Lange, T., Steinwandt, R. (eds.) PQCrypto 2018. LNCS, vol. 10786, pp. 229–247. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-79063-3_11
Rostovtsev, A., Stolbunov, A.: Public-Key Cryptosystem Based On Isogenies. Cryptology ePrint Archive, Report 2006/145 (2006)
Schnorr, C.P., Shamir, A.: An optimal sorting algorithm for mesh connected computers. In: Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, pp. 255–263. STOC 1986, Association for Computing Machinery, New York, NY, USA (1986)
Schoof, R.: Nonsingular plane cubic curves over finite fields. J. Comb. Theory Ser. A 46(2), 183–211 (1987). https://www.sciencedirect.com/science//pii/0097316587900033
Silverman, J.: The Arithmetic of Elliptic Curves, vol. 106 (2009)
Stolbunov, A.: Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves. Adv. Math. Commun. 4(2), 215–235 (2010)
Tate, J.: Endomorphisms of abelian varieties over finite fields. Invent. Math. 2(2), 134–144 (1966)
The Sage Developers: SageMath, the Sage Mathematics Software System (Version 9.4) (2021). https://www.sagemath.org
The SIDH Library Developers: SIDH v3.4 (C Edition) (2021). https://github.com/microsoft/PQCrypto-SIDH
van Oorschot, P.C., Wiener, M.J.: Parallel collision search with cryptanalytic applications. J. Cryptol. 12(1), 1–28 (1999)
Varrette, S., Bouvry, P., Cartiaux, H., Georgatos, F.: Management of an academic HPC cluster: The UL experience. In: Proceedings of the 2014 International Conference on High Performance Computing & Simulation (HPCS 2014), pp. 959–967. IEEE, Bologna, Italy (2014)
