Degenerate Curve Attacks

详细信息    查看全文

• 关键词：Elliptic curve cryptography ; Edwards curves ; Implementation issues ; Fault attacks ; Countermeasures
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9615
• 期：1
• 页码：19-35
• 全文大小：327 KB
• 参考文献：1.Antipa, A., Brown, D.R.L., Menezes, A., Struik, R., Vanstone, S.A.: Validation of elliptic curve public keys. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 211–223. Springer, Heidelberg (2002)CrossRef
  2.Aranha, D.F., Barreto, P., Pereira, G., Ricardini, J.E.: A note on high-security general-purpose elliptic curves. Cryptology ePrint Archive, Report 2013/647 (2013). http://​eprint.​iacr.​org/​
  3.Baek, Y.-J., Vasyltsov, I.: How to prevent DPA and fault attack in a unified way for ECC scalar multiplication – ring extension method. In: Dawson, E., Wong, D.S. (eds.) ISPEC 2007. LNCS, vol. 4464, pp. 225–237. Springer, Heidelberg (2007). http://​dx.​doi.​org/​10.​1007/​978-3-540-72163-5_​18 CrossRef
  4.Bernstein, D.J.: Curve25519: new Diffie-Hellman speed records. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (eds.) PKC 2006. LNCS, vol. 3958, pp. 207–228. Springer, Heidelberg (2006)CrossRef
  5.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–405. Springer, Heidelberg (2008)CrossRef
  6.Bernstein, D.J., Chuengsatiansup, C., Kohel, D., Lange, T.: Twisted Hessian curves. In: Lauter, K., Rodríguez-Henríquez, F. (eds.) LatinCrypt 2015. LNCS, vol. 9230, pp. 269–294. Springer, Heidelberg (2015)CrossRef
  7.Bernstein, D.J., Lange, T.: Faster addition and doubling on elliptic curves. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 29–50. Springer, Heidelberg (2007)CrossRef
  8.Bernstein, D.J., Lange, T.: Explicit-formulas database (2015). https://​hyperelliptic.​org/​EFD/​ . Accessed 1 May 2015
  9.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–146. Springer, Heidelberg (2000)CrossRef
  10.Billet, O., Joye, M.: The Jacobi model of an elliptic curve and side-channel analysis. In: Fossorier, M.P.C., Høholdt, T., Poli, A. (eds.) AAECC 2003. LNCS, vol. 2643, pp. 34–42. Springer, Heidelberg (2003). https://​eprint.​iacr.​org/​2002/​125 CrossRef
  11.Blömer, J., Otto, M., Seifert, J.-P.: Sign change fault attacks on elliptic curve cryptosystems. In: Breveglieri, L., Koren, I., Naccache, D., Seifert, J.-P. (eds.) FDTC 2006. LNCS, vol. 4236, pp. 36–52. Springer, Heidelberg (2006). http://​dx.​doi.​org/​10.​1007/​11889700_​4 CrossRef
  12.Boneh, D., DeMillo, R.A., Lipton, R.J.: On the importance of checking cryptographic protocols for faults. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 37–51. Springer, Heidelberg (1997)
  13.Boneh, D., DeMillo, R.A., Lipton, R.J.: On the importance of eliminating errors in cryptographic computations. J. Cryptol. 14(2), 101–119 (2001)CrossRef MathSciNet MATH
  14.Chudnovsky, D.V., Chudnovsky, G.V.: Sequences of numbers generated by addition in formal groups and new primality and factorization tests. Adv. Appl. Math. 7(4), 385–434 (1986). http://​dx.​org/​10.​1016/​0196-8858(86)90023-0 CrossRef MathSciNet MATH
  15.Ciet, M., Joye, M.: Elliptic curve cryptosystems in the presence of permanent and transient faults. Des. Codes Crypt. 36(1), 33–43 (2005). http://​dx.​org/​10.​1007/​s10623-003-1160-8 CrossRef MathSciNet MATH
  16.Coppersmith, D., Odlyzko, A.M., Schroeppel, R.: Discrete logarithms in \(GF(p)\) . Algorithmica 1(1), 1–15 (1986). http://​dx.​org/​10.​1007/​BF01840433 CrossRef MathSciNet MATH
  17.Desboves, A.: Résolution, en nombres entries et sous la forme la plus générale, de l’équation cubique, homogène, à trois inconnues. Nouvelles annales de mathématiques, journal des candidats aux écoles polytechnique et normale 5(3), 545–579 (1886). http://​www.​numdam.​org/​item?​id=​NAM_​1886_​3_​5_​_​545_​0
  18.Edwards, H.M.: A normal form for elliptic curves. Bull. Am. Math. Soc. 44(3), 393–422 (2007). http://​dx.​org/​10.​1090/​S0273-0979-07-01153-6 CrossRef MATH
  19.ElGamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inf. Theory 31, 469–472 (1985)CrossRef MathSciNet MATH
  20.Fouque, P., 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. (eds.) 2008 Fifth International Workshop on Fault Diagnosis and Tolerance in Cryptography, FDTC 2008, Washington, DC, USA, 10 August 2008, pp. 92–98. IEEE Computer Society (2008). http://​dx.​org/​10.​1109/​FDTC.​2008.​15
  21.Gordon, D.M.: Discrete logarithms in \(GF(p)\) using the number field sieve. SIAM J. Discret. Math. 6(1), 124–138 (1993). http://​dx.​org/​10.​1137/​0406010 CrossRef MATH
  22.Hamburg, M.: Ed448-Goldilocks. In: Workshop on Elliptic Curve Cryptography Standards (2015)
  23.Harris, B., et al.: The Pareto frontiers of sleeveless primes. The Curves mailing list, October 2014. https://​moderncrypto.​org/​mail-archive/​curves/​2014/​000324.​html
  24.Hesse, O.: Über die Elimination der Variabeln aus drei algebraischen Gleichungen vom zweiten Grade mit zwei Variabeln. Journal für die reine und angewandte Mathematik 28, 68–96 (1844). http://​resolver.​sub.​uni-goettingen.​de/​purl?​GDZPPN002144069 CrossRef MathSciNet MATH
  25.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–343. Springer, Heidelberg (2008)CrossRef
  26.Hisil, H., Wong, K.K., Carter, G., Dawson, E.: An exploration of affine group laws for elliptic curves. J. Math. Cryptol. 5(1), 1–50 (2011). http://​dx.​org/​10.​1515/​jmc.​2011.​005 CrossRef MathSciNet MATH
  27.Huff, G.B.: Diophantine problems in geometry and elliptic ternary forms. Duke Math. J. 15(2), 443–453 (1948)CrossRef MathSciNet MATH
  28.Husemöller, D.: Elliptic Curves, Graduate Texts in Mathematics, vol. 111, 2nd edn. Springer, New York (2004)
  29.Jager, T., Schwenk, J., Somorovsky, J.: Practical invalid curve attacks on TLS-ECDH. In: Pernul, G., Y A Ryan, P., Weippl, E. (eds.) ESORICS. LNCS, vol. 9326, pp. 407–425. Springer, Heidelberg (2015). doi:10.​1007/​978-3-319-24174-6_​21 CrossRef
  30.Joye, M.: Fault-resistant calculcations on elliptic curves, June 2013. http://​www.​google.​com/​patents/​US8457303 , US Patent 8,457,303
  31.Joye, M.: On the security of a unified countermeasure. In: Breveglieri, L., Gueron, S., Koren, I., Naccache, D., Seifert, J. (eds.) 2008 Fifth International Workshop on Fault Diagnosis and Tolerance in Cryptography, FDTC 2008, Washington, DC, USA, 10 August 2008, pp. 87–91. IEEE Computer Society (2008). http://​dx.​org/​10.​1109/​FDTC.​2008.​8
  32.Joye, M.: Elliptic curve cryptosystems in the presence of faults. In: Fischer, W., Schmidt, J. (eds.) 2013 Workshop on Fault Diagnosis and Tolerance in Cryptography, Los Alamitos, CA, USA, 20 August 2013, p. 73. IEEE Computer Society (2013). http://​conferenze.​dei.​polimi.​it/​FDTC13/​shared/​FDTC-2013-keynote-2.​pdf
  33.Joye, M., Quisquater, J.-J.: Hessian elliptic curves and side-channel attacks. In: Koç, Ç.K., Naccache, D., Paar, C. (eds.) CHES 2001. LNCS, vol. 2162, pp. 402–410. Springer, Heidelberg (2001)CrossRef
  34.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–250. Springer, Heidelberg (2010). http://​dx.​doi.​org/​10.​1007/​978-3-642-14518-6_​20 CrossRef
  35.Karabina, K., Ustaoğlu, B.: Invalid-curve attacks on (hyper)elliptic curve cryptosystems. Adv. Math. Commun. 4(3), 307–321 (2010). http://​cryptolounge.​net/​pdf/​KarUst10.​pdf CrossRef MathSciNet MATH
  36.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–180. Springer, Heidelberg (2014)
  37.Kim, T., Tibouchi, M.: Invalid curve attacks in a GLS setting. In: Tanaka, K., Suga, Y. (eds.) IWSEC 2015. LNCS, vol. 9241, pp. 41–55. Springer, Heidelberg (2015)CrossRef
  38.Koblitz, N.: Elliptic curve cryptosystems. Math. Comput. 48, 203–209 (1987). http://​dx.​org/​10.​1090/​S0025-5718-1987-0866109-5 CrossRef MathSciNet MATH
  39.Lenstra Jr., H.W.: Factoring integers with elliptic curves. Ann. Math. 126(3), 649–673 (1987). http://​www.​jstor.​org/​stable/​1971363
  40.Liardet, P., Smart, N.P.: Preventing SPA/DPA in ECC systems using the Jacobi form. In: Koç, Ç.K., Naccache, D., Paar, C. (eds.) CHES 2001. LNCS, vol. 2162, pp. 391–401. Springer, Heidelberg (2001)CrossRef
  41.Lim, C.H., Lee, P.J.: A key recovery attack on discrete log-based schemes using a prime order subgroup. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 249–263. Springer, Heidelberg (1997)CrossRef
  42.Lochter, M., Merkle, J., Schmidt, J.M., Schütze, T.: Requirements for standard elliptic curves. Cryptology ePrint Archive, Report 2014/832 (2014). http://​eprint.​iacr.​org/​2014/​832
  43.Menezes, A.: Another look at HMQV. J. Math. Cryptol. 1, 47–64 (2007). http://​dx.​org/​10.​1515/​JMC.​2007.​004 CrossRef MathSciNet MATH
  44.Miller, V.S.: Use of elliptic curves in cryptography. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 417–426. Springer, Heidelberg (1986)
  45.Montgomery, P.L.: Speeding the Pollard and elliptic curve methods of factorization. Math. Comput. 48(177), 243–264 (1987). http://​www.​ams.​org/​journals/​mcom/​1987-48-177/​S0025-5718-1987-0866113-7/​ CrossRef MATH
  46.Mumford, D.: On the equations defining Abelian varieties. I. Inventiones Math. 1(4), 287–354 (1966). http://​dash.​harvard.​edu/​handle/​1/​3597241 CrossRef MathSciNet MATH
  47.Pohlig, S.C., Hellman, M.E.: An improved algorithm for computing logarithms over GF\((p)\) and its crytographic significance. IEEE Trans. Inf. Theory 24, 106–110 (1978)CrossRef MathSciNet MATH
  48.Rauzy, P., Moreau, M., Guilley, S., Najm, Z.: Using modular extension to provably protect ECC against fault attacks. Cryptology ePrint Archive, Report 2015/882 (2015). http://​eprint.​iacr.​org/​2015/​882
  49.Rubin, K., Silverberg, A.: Compression in finite fields and torus-based cryptography. SIAM J. Comput. 37(5), 1401–1428 (2008)CrossRef MathSciNet MATH
  50.Shamir, A.: How to check modular exponentiation, May 1997. (presented at the rump session of EUROCRYPT 1997)
  51.Shanks, D.: Class number, a theory of factorization, and genera. In: Lewis, D.J. (ed.) 1969 Number Theory Institute. Proceedings of Symposia in Pure Mathematics, vol. 20, pp. 415–440. American Mathematical Society, Providence, Rhode Island (1971)CrossRef
  52.Silverman, J.H.: The Arithmetic of Elliptic Curves, Graduate Texts in Mathematics, vol. 106, 2nd edn. Springer, New York (2009). http://​www.​math.​brown.​edu/​jhs/​AECHome.​html CrossRef
  53.Smart, N.P.: The Hessian form of an elliptic curve. In: Koç, Ç.K., Naccache, D., Paar, C. (eds.) CHES 2001. LNCS, vol. 2162, pp. 118–125. Springer, Heidelberg (2001)CrossRef
  54.Straus, E.G.: Addition chains of vectors (problem 5125). Am. Math. Monthly 71(7), 806–808 (1964). http://​www.​jstor.​org/​stable/​2310929 MathSciNet
  
• 作者单位：Samuel Neves (17)
  Mehdi Tibouchi (18)
  
  17. CISUC, Department of Informatics Engineering, University of Coimbra, Coimbra, Portugal
  18. Okamoto Research Laboratory, NTT Secure Platform Laboratories, Musashino-shi, Japan
  
• 丛书名：Public-Key Cryptography ᾿PKC 2016
• ISBN：978-3-662-49387-8
• 刊物类别：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

文摘

Invalid curve attacks are a well-known class of attacks against implementations of elliptic curve cryptosystems, in which an adversary tricks the cryptographic device into carrying out scalar multiplication not on the expected secure curve, but on some other, weaker elliptic curve of his choosing. In their original form, however, these attacks only affect elliptic curve implementations using addition and doubling formulas that are independent of at least one of the curve parameters. This property is typically satisfied for elliptic curves in Weierstrass form but not for newer models that have gained increasing popularity in recent years, like Edwards and twisted Edwards curves. It has therefore been suggested (e.g. in the original paper on invalid curve attacks) that such alternate models could protect against those attacks.