Invalid Curve Attacks in a GLS Setting

详细信息    查看全文

• 关键词：Elliptic curve cryptography ; GLS method ; Cryptanalysis
• 刊名：Lecture Notes in Computer Science
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：9241
• 期：1
• 页码：41-55
• 全文大小：258 KB
• 参考文献：1.ANSI X9.63: Public Key Cryptography for the Financial Services Industry, Key Agreement and Key Transport Using Elliptic Curve Cryptography. ANSI, Washington DC (2001)
  2. Antipa, A., Brown, D.R.L., Menezes, A., Struik, R., Vanstone, S.: Validation of elliptic curve public keys. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 211-23. Springer, Heidelberg (2003) View Article
  3.Bach, E., Peralta, R.: Asymptotic semismoothness probabilities. Math. Comput. 65(216), 1701-715 (1996)MathSciNet View Article MATH
  4. Bernstein, D.J., Birkner, P., Joye, M., Lange, T., Peters, C.: Twisted Edwards curves. In: Vaudenay, S. (ed.) AFRICACRYPT 2008. LNCS, vol. 5023, pp. 389-05. Springer, Heidelberg (2008) View Article
  5.Bernstein, D.J., Lange, T.: SafeCurves: choosing safe curves for elliptic-curve cryptography. http://?safecurves.?cr.?yp.?to
  6. Bernstein, D.J., Lange, T.: Faster addition and doubling on elliptic curves. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 29-0. Springer, Heidelberg (2007) View Article
  7. Biehl, I., Meyer, B., Müller, V.: Differential fault attacks on elliptic curve cryptosystems. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 131-46. Springer, Heidelberg (2000) View Article
  8.Ciet, M., Joye, M.: Elliptic curve cryptosystems in the presence of permanent and transient faults. Des. Codes Crypt. 36(1), 33-3 (2005)MathSciNet View Article MATH
  9. Coron, J.-S., Naccache, D., Tibouchi, M.: Fault attacks against emv signatures. In: Pieprzyk, J. (ed.) CT-RSA 2010. LNCS, vol. 5985, pp. 208-20. Springer, Heidelberg (2010) View Article
  10.Dickman, K.: On the frequency of numbers containing prime factors of a certain relative magnitude. Arkiv f?r Matematik, Astronomi och Fysik 22A(10), 1-4 (1930)
  11. Farashahi, R.R., Joye, M.: Efficient arithmetic on Hessian curves. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 243-60. Springer, Heidelberg (2010) View Article
  12. Faz-Hernández, A., Longa, P., Sánchez, A.H.: Efficient and secure algorithms for GLV-based scalar multiplication and their implementation on GLV-GLS curves. In: Benaloh, J. (ed.) CT-RSA 2014. LNCS, vol. 8366, pp. 1-7. Springer, Heidelberg (2014) View Article
  13.FIPS PUB 186-: Digital Signature Standard (DSS). NIST (2009)
  14.Fouque, P.-A., Lercier, R., Réal, D., Valette, F.: Fault attack on elliptic curve montgomery ladder implementation. In: Breveglieri, L., Gueron, S., Koren, I., Naccache, D., Seifert, J.-P., (eds) FDTC, pp. 92-8 (2008)
  15. Galbraith, S.D., Lin, X., Scott, M.: Endomorphisms for faster elliptic curve cryptography on a large class of curves. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 518-35. Springer, Heidelberg (2009) View Article
  16.Galbraith, S.D., Lin, X., Scott, M.: Endomorphisms for faster elliptic curve cryptography on a large class of curves. J. Crypt. 24(3), 446-69 (2011)MathSciNet View Article MATH
  17. Gallant, R.P., Lambert, R.J., Vanstone, S.A.: Faster point multiplication on elliptic curves with efficient endomorphisms. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 190-00. Springer, Heidelberg (2001) View Article
  18.Gekeler, E.-U.: The distribution of group structures on elliptic curves over finite prime fields. Documenta Mathematica 11, 119-42 (2006)MathSciNet MATH
  19. Hisil, H., Wong, K.K.-H., Carter, G., Dawson, E.: Twisted Edwards curves revisited. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 326-43. Springer, Heidelberg (2008) View Article
  20.ISO/IEC 18033-: Information technology - Security techniques - Encryption algorithms - Part 2: Asymmetric ciphers. ISO, Geneva (2006)
  21. Joye, M., Tibouchi, M., Vergnaud, D.: Huff’s model for elliptic curves. In: Hanrot, G., Morain, F., Thomé, E. (eds.) ANTS-IX. LNCS, vol. 6197, pp. 234-50. Springer, Heidelberg (2010) View Article
  22.Karabina, K., Ustao?lu, B.: Invalid-curve attacks on (hyper)elliptic curve cryptosystems. Adv. in Math. of Comm. 4(3), 307-21 (2010)View Article MATH
  23. Kim, T., Tibouchi, M.: Bit-flip faults on elliptic curve base fields, revisited. In: Boureanu, I., Owesarski, P., Vaudenay, S. (eds.) ACNS 2014. LNCS, vol. 8479, pp. 163-80. Springer, Heidelberg (2014)
  24.Koblitz, N.: Elliptic curve cryptosystems. Math. Comp. 48, 203-09 (1987)MathSciNet View Article MATH
  25. Longa, P., Sica, F.: Four-dimensional Gallant-Lambert-Vanstone scalar multiplication. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 718-39. Springer, Heidelberg (2012) View Article
  26. Menezes, A., Ustaoglu, B.: On the importance of public-key validation in the MQV and HMQV Key agreement protocols. In: Barua, R., Lange, T. (eds.) INDOCRYPT 2006. LNCS, vol. 4329, pp. 133-47. Springer, Heidelberg (2006) View Article
  27. Miller, V.S.: Use of elliptic curves in cryptography. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 417-26. Springer, Heidelberg (198
• 作者单位：Taechan Kim (15)
  Mehdi Tibouchi (15)
  
  15. NTT Secure Platform Laboratories, Tokyo, Japan
  
• 丛书名：Advances in Information and Computer Security
• ISBN：978-3-319-22425-1
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

In recent years, most speed records for implementations of elliptic curve cryptosystems have been achieved on curves endowed with nontrivial fast endomorphisms, particularly based on the technique introduced by Galbraith, Lin and Scott (GLS). Therefore, studying the security of those curves is of prime importance. In this paper, we examine the applicability of the class of attacks introduced by Biehl?et al., known as invalid curve attacks, to cryptographic implementations based on GLS curves. In invalid curve attacks, a cryptographic device that computes a secret scalar multiplication \(P\mapsto kP\) on a certain elliptic curve \(E/{\mathbb F}_q\) receives as input an arbitrary “invalid-point \(\widetilde{P}\not \in E({\mathbb F}_q)\). Biehl?et al. observed that the device then computes the scalar multiplication by k on a different elliptic curve \(\widetilde{E}/{\mathbb F}_q\), and if that curve is weaker than E, the attacker can use the result to recover information about the secret k. The attack doesn’t readily adapt to the GLS setting, since the device computes the scalar multiplication as \(P\mapsto k_1P + k_2\psi (P)\) where \(\psi \) is the efficient endomorphism of the GLS curve E, and if it receives an arbitrary invalid point \(\widetilde{P}\) on a curve \(\widetilde{E}\ne E\), the computation of the map \(\psi \) yields a point on a completely different curve again, and the scalar multiplication outputs gibberish. We show, however, that a large family of invalid points \(\widetilde{P}\) lie on curve stable under \(\psi \), and using that observation we can modify the attack of Biehl?et al. to effectively recover the secrets \(k_1\) and \(k_2\), although the result of the computation on an invalid point doesn’t have the “correct-discrete logarithm.