Abstract
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.
Chapter PDF
Similar content being viewed by others
Keywords
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.
References
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, 218
C. Adams and S. Farrell, Internet X.509 Public Key Infrastructure: Certificate Management Protocols, RFC 2510, March 1999. Available from http://www.ietf.org. 218
ANSI X9.62, Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA), American National Standards Institute, 1999. 214
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, 214
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 http://grouper.ieee.org/groups/802/15/pub/2002/May02/02210r0P802-15 TG3-NTRU-Full-Security-Text-Proposal.pdf. 221
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. 213
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, 216
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 http://www.ietf.org. 213
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. 215
FIPS 186-2, Digital Signature Standard (DSS), Federal Information Processing Standards Publication 186-2, National Institute of Standards and Technology, 2000. 212, 214, 215, 219
V. Gupta, S. Blake-Wilson, B. Moeller and C. Hawk, ECC Cipher Suites for TLS, IETF Internet-Draft, August 2002. Available from http://www.ietf.org. 213
IEEE Std 1363-2000, IEEE Standard Specifications for Public-Key Cryptography, 2000. 213, 214, 216
IEEE P1363a, Draft Standard Specifications for Public-Key Cryptography — Amendment 1: Additional Techniques, working draft 10.5, April 26 2002. Available from http://grouper.ieee.org/groups/1363/tradPK/P1363a/draft.html. 213
ISO/IEC 15946-2, Information Technology — Security Techniques — Cryptographic Techniques Based on Elliptic Curves — Part 2: Digital Signatures, draft, February 2001. 214
ISO/IEC 15946-3, Information Technology — Security Techniques — Cryptographic Techniques Based on Elliptic Curves — Part 3: Key Establishment, draft, February 2001. 213, 214
D. Johnson, Contribution to ANSI X9F1 working group, 1997. 211
D. Johnson, “Key validation”, Contribution to IEEE P1363 working group, 1997. 211
L. Law, A. Menezes, M. Qu, J. Solinas and S. Vanstone, “An efficient protocol for authenticated key agreement”, Designs, Codes and Cryptography, to appear. 214
H. Lenstra, “Factoring integers with elliptic curves”, Annals of Mathematics, 126 (1987), 649–673. 219
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, 215
A. Menezes, Elliptic Curve Public Key Cryptosystems, Kluwer Academic Publishers, 1993. 220
M. Myers, C. Adams, D. Solo and D. Kemp, Internet X.509 Certificate Request Message Format, RFC 2511, March 1999. Available from http://www.ietf.org. 218
J. Solinas, “Efficient arithmetic on Koblitz curves”, Designs, Codes and Cryptography, 19 (2000), 195–249. 222
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Antipa, A., Brown, D., Menezes, A., Struik, R., Vanstone, S. (2003). Validation of Elliptic Curve Public Keys. In: Desmedt, Y.G. (eds) Public Key Cryptography — PKC 2003. PKC 2003. Lecture Notes in Computer Science, vol 2567. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36288-6_16
Download citation
DOI: https://doi.org/10.1007/3-540-36288-6_16
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00324-3
Online ISBN: 978-3-540-36288-3
eBook Packages: Springer Book Archive