Advertisement

Exceptional Procedure Attack on Elliptic Curve Cryptosystems

  • Tetsuya Izu
  • Tsuyoshi Takagi
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2567)

Abstract

The scalar multiplication of elliptic curve based cryptosystems (ECC) is computed by repeatedly calling the addition formula that calculatest he elliptic curve addition of two points. The addition formula involves several exceptional procedures so that implementers have to carefully consider their treatments. In this paper we study the exceptional procedure attack, which reveals the secret scalar using the error arisen from the exceptional procedures. Recently new forms of elliptic curvesan d addition formulas for ECC have been proposed, namely the Montgomery form, the Jacobi form, the Hessian form, and the Brier-Joye addition formula. They aim at improving security or efficiency of the underlying scalar multiplications. We analyze the effectiveness of the exceptional procedure attack to some addition formulas. We conclude that the exceptional procedure attack is infeasible against the curves whose order are prime, i.e., the recommended curves by several standards. However, the exceptional procedure attack on the Brier-Joye addition formula is feasible, because it yields non-standard exceptional points. We propose an attack that revealsa few bitso f the secret scalar, provided that this multiplier is constant and fixed. By the experiment over the standard elliptic curves, we have found many non-standard exceptional points even though the standard addition formula over the curves has no exceptional point. When a new addition formula isde veloped, we should be cautious about the proposed attack.

Keywords

Elliptic curve cryptosystem (ECC) scalar multiplication exceptional procedure attack exceptional point side channel attack 

References

  1. [ANSI]
    ANSI X9.62, Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA), draft, 1998. 225, 230, 235Google Scholar
  2. [BMM00]
    I. Biehl, B. Meyer, and V. Müller, “Differential Fault Attackson Elliptic Curve Cryptosystems”, CRYPTO 2000, LNCS 1880, pp.131–146, Springer-Verlag, 2000. 225, 230CrossRefGoogle Scholar
  3. [BiJ02]
    O. Billet and M. Joye, “The Jacobi Model of an Elliptic Curve and Side-Channel Analysis”, Cryptology ePrint Archive, Report 2002/125, 2002. 225Google Scholar
  4. [BDL97]
    D. Boneh, R. DeMillo, and R. Lipton, “On the Importance of Checking Cryptographic Protocolsfor Faults”, Eurocrypt’97, LNCS 1233, pp.37–51, Springer-Verlag, 1997. 225, 230Google Scholar
  5. [BrJ02]
    E. Brier and M. Joye, “Weierstraβ Elliptic Curves and Side-Channel Attacks”, PKC 2002, LNCS 2274, pp.335–345, Springer-Verlag, 2002. 225, 230, 231, 232Google Scholar
  6. [BSS99]
    I. Blake, G. Seroussi, and N. Smart, Elliptic Curves in Cryptography, Cambridge University Press, 1999. 233Google Scholar
  7. [CMO98]
    H. Cohen, A. Miyaji and T. Ono, “Efficient Elliptic Curve Exponentiation using Mixed Coordinates”, Asiacrypt’98, LNCS 1514, Springer-Verlag, pp.51–65, 1998. 227Google Scholar
  8. [IEEE]
    IEEE P1363, Standard Specificationsfor Public-Key Cryptography, 2000. Available from http://groupe.ieee.org/groups/1363/ 225, 230, 235
  9. [IT02]
    T. Izu and T. Takagi, “On the Security of Brier-Joye’sAddi tion Formula for Weierstrass-form Elliptic Curves”, Technical Report, No. TI-3/02, Technische Universität Darmstadt, 2002.Google Scholar
  10. [JQ01]
    M. Joye and J. Quisqiater, “Hessian Elliptic Curves and Side-Channel Attacks”, CHES 2001, LNCS 2162, pp.412–420, Springer-Verlag, 2001. 225Google Scholar
  11. [KJJ99]
    C. Kocher, J. Jaffe, and B. Jun, “Differential Power Analysis”, Crypto’99, LNCS 1666, pp.388–397, Springer-Verlag, 1999. 225, 231Google Scholar
  12. [LMQSV98]
    L. Law, A. Menezes, M. Qu, J. Solinas, and S. Vanstone, “An Efficient Protocol for Authenticated Key Agreement”, Technical report CORR 98-05, University of Waterloo, 1998. 225, 231Google Scholar
  13. [LS01]
    P. Liardet and N. Smart, “Preventing SPA/DPA in ECC System using the Jacobi Form”, CHES 2001, LNCS 2162, pp.401–411, Springer-Verlag, 2001. 225Google Scholar
  14. [OKS00]
    K. Okeya, H. Kurumatani, and K. Sakurai, “Elliptic Curveswit h the Montgomery Form and their cryptographic Applications”, PKC 2000, LNCS 1751, pp.446–465, Springer-Verlag, 2000. 225Google Scholar
  15. [SEC]
    Standardsfor Efficient Cryptography Group (SECG), Speciffication of Standardsfor Efficient Cryptography. Available from http://www.secg.org225, 230, 234, 235, 236
  16. [Sil86]
    J. Silverman, The Arithmetic of Elliptic Curves, GMT 106, Springer-Verlag, 1986. 230Google Scholar
  17. [Sma01]
    N. Smart, “The Hessian Form of an Elliptic Curve”, CHES 2001, LNCS 2162, pp.118–125, Springer-Verlag, 2001. 225Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2003

Authors and Affiliations

  • Tetsuya Izu
    • 1
  • Tsuyoshi Takagi
    • 2
  1. 1.FUJITSU LABORATORIES LtdNakahara-kuJapan
  2. 2.Fachbereich InformatikTechnische Universität DarmstadtDarmstadtGermany

Personalised recommendations