Validation of Elliptic Curve Public Keys

  • Adrian Antipa
  • Daniel Brown
  • Alfred Menezes
  • René Struik
  • Scott Vanstone
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2567)


We present practical and realistic attacks on some standardized elliptic curve key establishment and public-key encryption protocols that are effective if the receiver of an elliptic curve point does not check that the point lies on the appropriate elliptic curve. The attacks combine ideas from the small subgroup attack of Lim and Lee, and the differential fault attack of Biehl, Meyer and Müller. Although the ideas behind the attacks are quite elementary, and there are simple countermeasures known, the attacks can have drastic consequences if these countermeasures are not taken by implementors of the protocols. We illustrate the effectiveness of such attacks on a key agreement protocol recently proposed for the IEEE 802.15 Wireless Personal Area Network (WPAN) standard.


Elliptic Curve Elliptic Curf Domain Parameter Wireless Personal Area Network Fault Attack 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


  1. [1]
    M. Abdalla, M. Bellare and P. Rogaway, “The oracle Diffie-Hellman assumptions and an analysis of DHIES”, Topics in Cryptology—CT-RSA 2001, Lecture Notes in Computer Science, vol. 2020 (2001), 143–158. 213, 218CrossRefGoogle Scholar
  2. [2]
    C. Adams and S. Farrell, Internet X.509 Public Key Infrastructure: Certificate Management Protocols, RFC 2510, March 1999. Available from 218
  3. [3]
    ANSI X9.62, Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA), American National Standards Institute, 1999. 214Google Scholar
  4. [4]
    ANSI X9.63, Public Key Cryptography for the Financial Services Industry: Key Agreement and Key Transport using Elliptic Curve Cryptography, American National Standards Institute, 2001. 213, 214Google Scholar
  5. [5]
    D. Bailey, A. Singer and W. Whyte, “IEEE P802-15 TG3 NTRU full security text proposal”, submission to the IEEE P802.15 Working Group for Wireless Personal Area Networks (WPANs), April 22, 2002. Available from TG3-NTRU-Full-Security-Text-Proposal.pdf. 221
  6. [6]
    M. Bellare and P. Rogaway, “Minimizing the use of random oracles in authenticated encryption schemes”, Information and Communications Security, Lecture Notes in Computer Science, vol. 1334 (1997), 1–16. 213CrossRefGoogle Scholar
  7. [7]
    I. Biehl, B. Meyer and V. Müller, “Differential fault analysis on elliptic curve cryptosystems”, Advances in Cryptology—CRYPTO 2000, Lecture Notes in Computer Science, vol. 1880 (2000), 131–146. 215, 216CrossRefGoogle Scholar
  8. [8]
    S. Blake-Wilson, D. Brown and P. Lambert, Use of Elliptic Curve Cryptography (ECC) Algorithms in Cryptographic Message Syntax (CMS), RFC 3278, April 2002. Available from 213
  9. [9]
    D. Boneh, R. DeMillo and R. Lipton, “On the importance of checking cryptographic protocols for faults”, Advances in Cryptology—EUROCRYPT’ 97, Lecture Notes in Computer Science, vol. 1233 (1997), 37–51. 215Google Scholar
  10. [10]
    FIPS 186-2, Digital Signature Standard (DSS), Federal Information Processing Standards Publication 186-2, National Institute of Standards and Technology, 2000. 212, 214, 215, 219Google Scholar
  11. [11]
    V. Gupta, S. Blake-Wilson, B. Moeller and C. Hawk, ECC Cipher Suites for TLS, IETF Internet-Draft, August 2002. Available from 213
  12. [12]
    IEEE Std 1363-2000, IEEE Standard Specifications for Public-Key Cryptography, 2000. 213, 214, 216Google Scholar
  13. [13]
    IEEE P1363a, Draft Standard Specifications for Public-Key Cryptography — Amendment 1: Additional Techniques, working draft 10.5, April 26 2002. Available from 213
  14. [14]
    ISO/IEC 15946-2, Information Technology — Security Techniques — Cryptographic Techniques Based on Elliptic Curves — Part 2: Digital Signatures, draft, February 2001. 214Google Scholar
  15. [15]
    ISO/IEC 15946-3, Information Technology — Security Techniques — Cryptographic Techniques Based on Elliptic Curves — Part 3: Key Establishment, draft, February 2001. 213, 214Google Scholar
  16. [16]
    D. Johnson, Contribution to ANSI X9F1 working group, 1997. 211Google Scholar
  17. [17]
    D. Johnson, “Key validation”, Contribution to IEEE P1363 working group, 1997. 211Google Scholar
  18. [18]
    L. Law, A. Menezes, M. Qu, J. Solinas and S. Vanstone, “An efficient protocol for authenticated key agreement”, Designs, Codes and Cryptography, to appear. 214Google Scholar
  19. [19]
    H. Lenstra, “Factoring integers with elliptic curves”, Annals of Mathematics, 126 (1987), 649–673. 219CrossRefMathSciNetGoogle Scholar
  20. [20]
    C. Lim and P. Lee, “A key recovery attack on discrete log-based schemes using a prime order subgroup”, Advances in Cryptology—CRYPTO’ 97, Lecture Notes in Computer Science, vol. 1294 (1997), 249–263. 211, 215CrossRefGoogle Scholar
  21. [21]
    A. Menezes, Elliptic Curve Public Key Cryptosystems, Kluwer Academic Publishers, 1993. 220Google Scholar
  22. [22]
    M. Myers, C. Adams, D. Solo and D. Kemp, Internet X.509 Certificate Request Message Format, RFC 2511, March 1999. Available from 218
  23. [23]
    J. Solinas, “Efficient arithmetic on Koblitz curves”, Designs, Codes and Cryptography, 19 (2000), 195–249. 222zbMATHCrossRefMathSciNetGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2003

Authors and Affiliations

  • Adrian Antipa
    • 1
  • Daniel Brown
    • 1
  • Alfred Menezes
    • 2
  • René Struik
    • 1
  • Scott Vanstone
    • 2
  1. 1.Certicom ResearchCanada
  2. 2.Dept. of Combinatorics and OptimizationUniversity of WaterlooCanada

Personalised recommendations