Abstract
Recent applications of lattice attacks against elliptic curve cryptosystems have shown that the protection of ephemeral keys in the ECDSA is of greatest importance. This paper shows how to enhance simple power-analysis attacks on elliptic-curve point-multiplication algorithms by using Markov models. We demonstrate the attack on an addition-subtraction algorithm (fixing the sequence of elliptic-curve operations) which is similar to the one described by Morain et al. in [MO90] and apply the method to the general addition-subtraction method described in ANSI X9.62 [ANS99].
The work in this paper was partially done while the author visited COSIC, KU Leuven, Belgium, 2002.
EM attacks appear to become increasingly powerful as well, see for example [QS01]
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
ANSI. ANSI X9.62 Public Key Cryptography for the Financal Services Industry:The Elliptic Curve Digital Signatur Algorithm (ECDSA), 1999.
Michael Brown, Darrel Hankerson, Julio Lopez, and Alfred Menezes. Software Implementation of the NIST Elliptic Curves Over Prime Fields. In Progress in Cryptology — CT-RSA, volume 2020 of Lecture Notes in Computer Science, pages 250–265. Springer, 2001.
E. Brier and M. Joye. Weierstrass Elliptic Curves and Side-Channel Attacks. In Public Key Cryptography, volume 2274 of Lecture Notes in Computer Science, page 335 ff. Springer, 2002.
Certicom Research. Standards For Efficient Cryptography — SECG 2: Recommended Elliptic Curve Cryptography Domain Parameters. Version 1.0, 2000. Available from http://www.secg.org/.
J.-S. Coron. Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems. In Workshop on Cryptographic Hardware and Embedded Systems — CHES 1999, volume 1717 of Lecture Notes in Computer Science, pages 292–302. Springer, 1999.
D. M. Gordon. A survey of fast exponentiation methods. Journal of Algorithms, (27): pp. 129–146, 1998.
Geoffrey Grimmett and David Stirzaker. Probability and Random Processes. Oxford University Press, 2nd edition, 1992. ISBN: 0198536658.
M. A. Hasan. Power Analysis Attacks and Algorithmic Approaches to Their Countermeasures for Koblitz Cryptosystems. In Cryptographic Hardware and Embedded Systems — CHES 2000, volume 1965 of Lecture Notes in Computer Science, pages 93–108. Springer, 2000.
N. Howgrave-Graham and N. Smart. Lattice attacks on digital signature schemes. Designs, Codes and Cryptography, (23):283–290, August 2001.
IEEE. Standard Specifications for Public Key Cryptography, Annex A, D13, 1999.
T. Izu and T. Takagi. Fast Parallel Elliptic Curve Multiplications Resistant to Side Channel Attacks. In to appear in International Workshop on the Practice and Theory of Public Key Cryptography (PKC2002), Lecture Notes in Computer Science (LNCS). Springer, 2002.
M. Joye and J.-J. Quisquater. Hessian Elliptic Curves and Side-Channel Attacks. In Cryptographic Hardware and Embedded Systems — CHES 2001, volume 2162 of Lecture Notes in Computer Science, pages 402–410, 2001.
P. C. Kocher, J. Jaffe, and B. Jun. Differential Power Analysis. In Advances in Cryptology-CRYPTO 1999, volume 1666 of Lecture Notes in Computer Science, pages 388–397. Springer, 1999.
D. E. Knuth. The Art of Computer Programming. Seminumerical Algorithms, volume 2. Addison-Wesley, 3rd edition, 1998.
P.-Y. Liardet and N.P. Smart. Preventing SPA/DPA in ECC Systems Using the Jacobi Form. In Cryptographic Hardware and Embedded Systems — CHES 2001, volume 2162 of Lecture Notes in Computer Science, pages 391–401, 2001.
F. Morain and J. Olivos. Speeding up the computation on an elliptic curve using addition-subtraction chains. Inform. Theory Appl., (24):531–543, 1990.
B. Möller. Securing Elliptic Curve Point Multiplication against Side-Channel Attacks. In Information Security — 4th International Conference, ISC 2001, volume 2200 of Lecture Notes in Computer Science (LNCS), page 324 ff. Springer, 2001.
NIST. Recommended Elliptic Curves For Federal Government Use, 1999.
E. Oswald and M. Aigner. Randomized Addition-Subtraction Chains as a Countermeasure against Power Attacks. In Cryptographic Hardware and Embedded Systems — CHES 2001, volume 2162 of Lecture Notes in Computer Science (LNCS), pages 39–50. Springer, 2001.
G. Orlando and Ch. Paar. A high performance reconfigurable elliptic curve processor for gf(2m). In Cryptographic Hardware and Embedded Systems — CHES 2000, volume 1965 of Lecture Notes in Computer Science, pages 41–56. Springer, 2000.
K. Okeya and K. Sakurai. Power Analysis Breaks Elliptic Curve Cryptosystems even Secure against the Timing Attack. In Progress in Cryptology — INDOCRYPT 2000, volume 1977 of Lecture Notes in Computer Science (LNCS), pages 178–190. Springer, 2000.
Jean-Jacques Quisquater and David Samyde. ElectroMagnetic Analysis (EMA): Measures and Counter-Measures for Smart Cards. In Smart Card Programming and Security, E-smart 2001, volume 2140 of Lecture Notes in Computer Science, pages 200–210. Springer, 2001.
T. Römer and J.-P. Seifert. Information leakage attacks against Smart Card implementations of the Elliptic Curve Digital Signature Algorithm. In Smart Card Programming and Security (E-Smart 2001), volume 2104 of Lecture Notes in Computer Science (LNCS), page 211 ff. Springer, 2001.
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
Oswald, E. (2003). Enhancing Simple Power-Analysis Attacks on Elliptic Curve Cryptosystems. In: Kaliski, B.S., Koç, ç.K., Paar, C. (eds) Cryptographic Hardware and Embedded Systems - CHES 2002. CHES 2002. Lecture Notes in Computer Science, vol 2523. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36400-5_8
Download citation
DOI: https://doi.org/10.1007/3-540-36400-5_8
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00409-7
Online ISBN: 978-3-540-36400-9
eBook Packages: Springer Book Archive