More Web Proxy on the site http://driver.im/

Article

Validation of Elliptic Curve Public Keys

Authors:

Daniel R. L. Brown,

Alfred Menezes,

Scott A. VanstoneAuthors Info & Claims

PKC '03: Proceedings of the 6th International Workshop on Theory and Practice in Public Key Cryptography: Public Key Cryptography

Pages 211 - 223

Published: 06 January 2003 Publication History

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.

References

[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.

[2]

C. ADAMS AND S. FARRELL, Internet X.509 Public Key Infrastructure: Certificate Management Protocols , RFC 2510, March 1999. Available from http://www.ietf.org.

[3]

ANSI X9.62, Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA) , American National Standards Institute, 1999.

[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.

[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 http://grouper.ieee.org/groups/802/15/pub/2002/May02/ 02210r0P802-15_TG3-NTRU-Full-Security-Text-Proposal.pdf.

[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.

[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.

[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 http://www.ietf.org.

[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.

[10]

FIPS 186-2, Digital Signature Standard (DSS) , Federal Information Processing Standards Publication 186-2, National Institute of Standards and Technology, 2000.

[11]

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.

[12]

IEEE Std 1363-2000, IEEE Standard Specifications for Public-Key Cryptography , 2000.

[13]

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.

[14]

ISO/IEC 15946-2, Information Technology -- Security Techniques -- Cryptographic Techniques Based on Elliptic Curves -- Part 2: Digital Signatures , draft, February 2001.

[15]

ISO/IEC 15946-3, Information Technology -- Security Techniques -- Cryptographic Techniques Based on Elliptic Curves -- Part 3: Key Establishment , draft, February 2001.

[16]

D. JOHNSON, Contribution to ANSI X9F1 working group, 1997.

[17]

D. JOHNSON, "Key validation", Contribution to IEEE P1363 working group, 1997.

[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.

[19]

H. LENSTRA, "Factoring integers with elliptic curves", Annals of Mathematics , 126 (1987), 649-673.

[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.

[21]

A. MENEZES, Elliptic Curve Public Key Cryptosystems , Kluwer Academic Publishers, 1993.

[22]

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.

[23]

J. SOLINAS, "Efficient arithmetic on Koblitz curves", Designs, Codes and Cryptography , 19 (2000), 195-249.

Cited By

Teruya TEmura KHong Seo JWatanabe Y(2018)A Note on Subgroup Security in Pairing-Based CryptographyProceedings of the 5th ACM on ASIA Public-Key Cryptography Workshop10.1145/3197507.3197514(35-43)Online publication date: 23-May-2018
https://dl.acm.org/doi/10.1145/3197507.3197514
Neves STibouchi M(2016)Degenerate Curve AttacksProceedings, Part II, of the 19th IACR International Conference on Public-Key Cryptography --- PKC 2016 - Volume 961510.1007/978-3-662-49387-8_2(19-35)Online publication date: 6-Mar-2016
https://dl.acm.org/doi/10.1007/978-3-662-49387-8_2
Kim TTibouchi M(2015)Invalid Curve Attacks in a GLS SettingProceedings of the 10th International Workshop on Advances in Information and Computer Security - Volume 924110.1007/978-3-319-22425-1_3(41-55)Online publication date: 26-Aug-2015
https://dl.acm.org/doi/10.1007/978-3-319-22425-1_3
Show More Cited By

Validation of Elliptic Curve Public Keys

Recommendations

Supersingular Elliptic Curve Isogeny Graphs
A Weil Descent Attack against Elliptic Curve Cryptosystems over Quartic Extension Fields

This paper proposes a Weil descent attack against elliptic curve cryptosystems over quartic extension fields. The scenario of the attack is as follows: First, one reduces a DLP on a Weierstrass form over the quartic extention of a finite field k to a ...
An Elliptic Curve Trapdoor System

We propose an elliptic curve trapdoor system which is of interest in key escrow applications. In this system, a pair (E_s, E_pb) of elliptic curves over F₂¹⁶¹ is constructed with the following properties: (i) the Gaudry-Hess-Smart Weil descent attack ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

PKC '03: Proceedings of the 6th International Workshop on Theory and Practice in Public Key Cryptography: Public Key Cryptography

January 2003

366 pages

ISBN:354000324X

Editor:
Yvo Desmedt

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 06 January 2003

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Teruya TEmura KHong Seo JWatanabe Y(2018)A Note on Subgroup Security in Pairing-Based CryptographyProceedings of the 5th ACM on ASIA Public-Key Cryptography Workshop10.1145/3197507.3197514(35-43)Online publication date: 23-May-2018
https://dl.acm.org/doi/10.1145/3197507.3197514
Neves STibouchi M(2016)Degenerate Curve AttacksProceedings, Part II, of the 19th IACR International Conference on Public-Key Cryptography --- PKC 2016 - Volume 961510.1007/978-3-662-49387-8_2(19-35)Online publication date: 6-Mar-2016
https://dl.acm.org/doi/10.1007/978-3-662-49387-8_2
Kim TTibouchi M(2015)Invalid Curve Attacks in a GLS SettingProceedings of the 10th International Workshop on Advances in Information and Computer Security - Volume 924110.1007/978-3-319-22425-1_3(41-55)Online publication date: 26-Aug-2015
https://dl.acm.org/doi/10.1007/978-3-319-22425-1_3
Fujioka ASuzuki K(2011)Designing efficient authenticated key exchange resilient to leakage of ephemeral secret keysProceedings of the 11th international conference on Topics in cryptology: CT-RSA 201110.5555/1964621.1964636(121-141)Online publication date: 14-Feb-2011
https://dl.acm.org/doi/10.5555/1964621.1964636
Zhao JGu D(2010)Provably secure authenticated key exchange protocol under the CDH assumptionJournal of Systems and Software10.1016/j.jss.2010.07.01083:11(2297-2304)Online publication date: 1-Nov-2010
https://dl.acm.org/doi/10.1016/j.jss.2010.07.010
Menezes AUstaoglu B(2006)On the importance of public-key validation in the MQV and HMQV key agreement protocolsProceedings of the 7th international conference on Cryptology in India10.1007/11941378_11(133-147)Online publication date: 11-Dec-2006
https://dl.acm.org/doi/10.1007/11941378_11
Bernstein D(2006)Curve25519Proceedings of the 9th international conference on Theory and Practice of Public-Key Cryptography10.1007/11745853_14(207-228)Online publication date: 24-Apr-2006
https://dl.acm.org/doi/10.1007/11745853_14

View Options

View options

Media

Figures

Other

Tables

View Table of Contents