Combined small subgroups and side-channel attack on elliptic curves with cofactor divisible by 2m

• Autorzy: Wroński Michał

Identyfikatory

DOI

10.24425/ijet.2019.126302

• Języki publikacji: EN

Abstrakty

EN

Nowadays, alternative models of elliptic curves like Montgomery, Edwards, twisted Edwards, Hessian, twisted Hessian, Huff's curves and many others are very popular and many people use them in cryptosystems which are based on elliptic curve cryptography. Most of these models allow to use fast and complete arithmetic which is especially convenient in fast implementations that are side-channel attacks resistant. Montgomery, Edwards and twisted Edwards curves have always order of group of rational points divisible by 4. Huff's curves have always order of rational points divisible by 8. Moreover, sometimes to get fast and efficient implementations one can choose elliptic curve with even bigger cofactor, for example 16. Of course the bigger cofactor is, the smaller is the security of cryptosystem which uses such elliptic curve. In this article will be checked what influence on the security has form of cofactor of elliptic curve and will be showed that in some situations elliptic curves with cofactor divisible by 2m are vulnerable for combined small subgroups and side-channel attacks.

Słowa kluczowe

EN

small subgroups attack; side-channel attack; alternative models of elliptic curves

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: International Journal of Electronics and Telecommunications
• Rocznik: 2019
• Tom: Vol. 65, No. 2
• Strony: 203--209
• Opis fizyczny: Bibliogr. 14 poz., wykr.

Twórcy

autor

Wroński Michał

• Institute of Mathematics and Cryptology, Faculty of Cybernetics, Military University of Technology, Warsaw, Poland

Bibliografia

• [1] J. Fan, B. Gierlichs, and F. Vercauteren, “To infinity and beyond: Combined attack on ecc using points of low order,” in Cryptographic Hardware and Embedded Systems – CHES 2011, B. Preneel and T. Takagi, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011, pp. 143–159.
• [2] D. Genkin, L. Valenta, and Y. Yarom, “May the fourth be with you: A microarchitectural side channel attack on several real-world applications of curve25519,” in Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, ser. CCS ’17. New York, NY, USA: ACM, 2017, pp. 845–858. [Online]. Available: http://doi.acm.org/10.1145/3133956.3134029
• [3] M. Peter, “Speeding the pollard and elliptic curve methods of factorization,” Mathematics of Computation, vol. 48, pp. 243–264, 1987.
• [4] E. Harold, “A normal form for elliptic curves,” Bulletin of the American Mathematical Society, vol. 44, no. 3, pp. 393–422, April 2007.
• [5] D. J. Bernstein and T. Lange, “Faster addition and doubling on elliptic curves,” in Advances in Cryptology – ASIACRYPT 2007, K. Kurosawa, Ed. Berlin, Heidelberg: Springer Berlin Heidelberg, 2007, pp. 29–50.
• [6] D. J. Bernstein, P. Birkner, M. Joye, T. Lange, and C. Peters, “Twisted edwards curves,” in Proceedings of the Cryptology in Africa 1st International Conference on Progress in Cryptology, ser. AFRICACRYPT’08. Berlin, Heidelberg: Springer-Verlag, 2008, pp. 389–405. [Online]. Available: http://dl.acm.org/citation.cfm?id= 1788634.1788672
• [7] M. Joye, M. Tibouchi, and D. Vergnaud, “Huff’s model for elliptic curves,” in Algorithmic Number Theory, G. Hanrot, F. Morain, and E. Thome, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010, pp. 234–250.
• [8] S. Pohlig and M. Hellman, “An improved algorithm for computing logarithms over and its cryptographic significance,” IEEE Trans. Inf. Theor., vol. 24, no. 1, pp. 106–110, September 1978. [Online]. Available: https://doi.org/10.1109/TIT.1978.1055817
• [9] I. Biehl, B. Meyer, and V. Muller, “Differential fault attacks on elliptic curve cryptosystems,” in Advances in Cryptology — CRYPTO 2000, M. Bellare, Ed. Berlin, Heidelberg: Springer Berlin Heidelberg, 2000, pp. 131–146.
• [10] M. Ciet and M. Joye, “Elliptic curve cryptosystems in the presence of permanent and transient faults,” Designs, Codes and Cryptography, vol. 36, no. 1, pp. 33–43, Jul 2005. [Online]. Available: https://doi.org/10.1007/s10623-003-1160-8
• [11] S. Neves and M. Tibouchi, “Degenerate curve attacks: extending invalid curve attacks to edwards curves and other models,” IET Information Security, vol. 12, no. 3, pp. 217–225, 2018. [Online]. Available: https://doi.org/10.1049/iet-ifs.2017.0075
• [12] C. H. Lim and P. J. Lee, “A key recovery attack on discrete log-based schemes using a prime order subgroup.” Springer-Verlag, 1997, pp. 249–263.
• [13] Z. R., “Methods for avoiding the small-subgroup attacks on the diffiehellman key agreement method for s/mime,” RFC 2785, March 2000.
• [14] D. J. Bernstein, “Curve 25519: New diffie-hellman speed records,” in Public Key Cryptography - PKC 2006, M. Yung, Y. Dodis, A. Kiayias, and T. Malkin, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006, pp. 207–228.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).