Elsevier

Computers & Electrical Engineering

Volume 33, Issues 5–6, September–November 2007, Pages 367-382
Computers & Electrical Engineering

Differential power and electromagnetic attacks on a FPGA implementation of elliptic curve cryptosystems

https://doi.org/10.1016/j.compeleceng.2007.05.009Get rights and content

Abstract

This paper describes the first differential power and electromagnetic analysis attacks performed on a hardware implementation of an elliptic curve cryptosystem. In the same time we also compared the metrics used in differential power and electromagnetic radiation attacks. We describe the use of the Pearson correlation coefficient, the distance of mean test and the maximum likelihood test. For each metric the number of measurements needed to get a clear idea of the right guess of the key-bit is taken as indication of the strength of the metric.

Introduction

Elliptic curve cryptography (ECC) was proposed independently by Miller [13] and Koblitz [9] in the 80’s. Since then a considerable amount of research has been performed on secure and efficient ECC implementations. The benefits of ECC, when compared with classical cryptosystems such as RSA [23], include: higher speed, lower power consumption and smaller certificates, which are especially useful for wireless applications.

There is a vast literature on differential power analysis (DPA) and differential electromagnetic radiation analysis (DEMA). This paper describes the first DPA and DEMA attack performed on a FPGA implementation of an elliptic curve cryptosystem over GF(p) [17]. The attacks in previous papers were performed on software implementations or were only simulations of attacks. With the start of differential power analysis in [10], followed by the differential electromagnetic analysis [8], [22], several metrics were used to decide for the correct hypothesis. The literature mentions metrics such as the distance of mean test [10], the correlation analysis [18] and the maximum likelihood test [3], all explained in Section 2.2. As we wanted to know which of those yields the best results, we compare them based on the number of measurements needed to obtain the correct key. The number of measurements for the key guess to stabilize is representative for the quality of the metric.

The paper is structured as follows: In Section 2, the theoretical background of elliptic curves, the power and electromagnetic radiation attacks and the different statistical methods for differential analysis are discussed. Section 3 gives an overview of the previous work in this area. This section is followed by a description of the measurement setup (Section 4). Section 5, describes differential power analysis attack and Section 6 describes differential electromagnetic analysis attack. Section 7 concludes the paper.

Section snippets

Elliptic curves over GF(p)

An elliptic curve E is expressed in terms of the simplified Weierstrass equation: y2 = x3 + ax + b, where a, b  GF(p) with 4a3 + 27b2  0 (mod p). The inverse of the point P = (x1, y1) is −P = (x1,−y1). The sum P + Q of the points P = (x1, y1) and Q = (x2, y2) (assume that P,Q,O, and P  ±Q) is the point R = (x3,y3) where: x3=λ2-x1-x2,y3=(x1-x3)λ-y1,λ=y2-y1x2-x1. For P = Q, the “doubling” formulae are: x3=λ2-2x1,y3=(x1-x3)λ-y1,λ=3x12+a2y1. The point at infinity O plays a role analogous to that of the number 0 in ordinary

Power analysis attacks

After the description of power-analysis attacks by Kocher et al. [10], the first paper dedicated to the application of these types of attacks to public-key cryptosystems was from Messerges et al. [12]. They studied the application of PA attacks on software implementations of modular exponentiations in smart cards.

Walter et al. observe in [27] that also modular subtractions can be used to determine the secret key. In [26] Walter shows, how to attack an RSA secret key without multiple

Measurement setup

The measurement setup consists of the FPGA board with a Xilinx Virtex 800 FPGA presented in [19], an Tektronix TDS714L oscilloscope, a Tektronix CT1 current probe, a handmade loop antenna, a function generator and a power supply. The total power consumption and the electromagnetic radiation of the FPGA were measured simultaneously while it executes an elliptic curve point multiplication with the key and a point on the curve.

DPA Attack on an FPGA implementation of an elliptic curve cryptosystem over GF(p)

In this section, we conduct a DPA attack on a FPGA implementation of an elliptic curve processor over GF(p) [17]. The current consumption trace of one EC point multiplication is shown in Fig. 2a.

The target for our DPA attack is the second most significant bit (MSB) of the key, kl−2, in Algorithm 1. There are two temporary point registers in the design, Q1 and Q2. These temporary points and the output point Q are updated in the following order.

  • Step 1:

    Q  P

  • Step 3:

    Q1  2Q = 2P

  • Step 4:

    Q2  Q1 + P = 3P

  • Step 5:

    QStep 6:Q1=2P,ifkl-2=0Step 8:Q2

DEMA attack on an FPGA implementation of an elliptic curve cryptosystem over GF(p)

In this section, we conduct a DEMA attack on a FPGA implementation of our elliptic curve processor over GF(p). One EM measurement of this architecture is shown in Fig. 10a. The target for our DEMA attack is the second MSB of the key, kl−2, in Algorithm 1.

Conclusions

We have implemented differential power and electromagnetic analysis attacks on an FPGA implementation of elliptic curve cryptosystems over GF(p). We use three well-known techniques for DPA and DEMA: correlation analysis, a distance of mean test and a maximum likelihood test. The following table summarizes the number of measurements needed for each analysis technique.

From Table 1, we conclude that correlation analysis reveals the right key bit by using two times fewer measurements than the

Acknowledgements

This work is supported by Institute for the Promotion of Innovation through Science and Technology in Flanders and FWO G.0475.05 Projects.

Elke De Mulder was in 1981 in Belgium. From 1999 to 2004 she studied at the “Katholieke Universiteit Leuven” where she got her degree in July 2004 with the thesis “Electromagnetic Analysis (EMA) of a FPGA implementation of an elliptic curve cryptosystem”. Currently she is a Ph.D. student at COSIC. The topic of her research is countermeasures against electromagnetic analysis (EMA). Her research is funded by the IWT-Flanders.

References (27)

  • D. Agrawal et al.

    Advances in side-channel cryptanalysis

    RSA Lab Cryptobytes

    (2003)
  • D. Agrawal et al.

    The EM side-channel(s): attacks and assessment methodologies

  • D. Agrawal et al.

    Multi-channel attacks

  • I. Blake et al.

    Elliptic curves in cryptography

    (1999)
  • Carlier V, Chabanne H, Dottax E, Pelletier H. Electromagnetic side channels of an FPGA implementation of AES,...
  • G.M. Clarke et al.

    A basic course in statistics

    (1998)
  • J.-S. Coron

    Resistance against differential power analysis for elliptic curve cryptosystems

  • K. Gandolfi et al.

    Electromagnetic analysis: concrete results

  • N. Koblitz

    Elliptic curve cryptosystem

    Math Comp

    (1987)
  • P. Kocher et al.

    Differential power analysis

  • Mangard S. Exploiting radiated emissions – EM attacks on cryptographic ICs. In: Proceedings of Austrochip, Linz,...
  • T.S. Messerges et al.

    Power analysis attacks of modular exponentiation in smartcards

  • V. Miller

    Uses of elliptic curves in cryptography

  • Cited by (49)

    View all citing articles on Scopus

    Elke De Mulder was in 1981 in Belgium. From 1999 to 2004 she studied at the “Katholieke Universiteit Leuven” where she got her degree in July 2004 with the thesis “Electromagnetic Analysis (EMA) of a FPGA implementation of an elliptic curve cryptosystem”. Currently she is a Ph.D. student at COSIC. The topic of her research is countermeasures against electromagnetic analysis (EMA). Her research is funded by the IWT-Flanders.

    S. Berna Örs received the Electronics and Communication Engineering Degree in 1995 and the M.Sc. Degree in Electronics and Communication Engineering in 1995 from the Istanbul Technical University, in Istanbul, Turkey. She received the Ph.D. Degree in applied sciences from the Katholieke Universiteit Leuven, in Leuven, Belgium in 2005. She is currently assistant professor at Istanbul Technical University. Her interests include circuits, processor architectures and embedded systems in application domains such as security, cryptography, digital signal processing and wireless applications.

    Bart Preneel received the Electrical Engineering degree and the Doctorate in Applied Sciences from the Katholieke Universiteit Leuven (Belgium). He is currently professor (hoogleraar) at the Katholieke Universiteit Leuven and visiting professor at the T.U. Graz in Austria. He was visiting professor at several universities in Europe (Ghent, Belgium, Bergen, Norway and Bochum, Germany). During the academic year 1993–1994, he was a research fellow of the EECS Department of the University of California at Berkeley. His main research interests are cryptography, network security, and wireless communications. He has authored and co-authored more than 180 scientific publications and is an inventor of two patents. He is vice president of the International Association for Cryptologic Research (IACR) and a member of the Editorial Board of the Journal of Cryptology, the IEEE Transactions on Informations and Security, and the ACM Transactions on Information Security. He is also a Member of the Accreditation Board of the Computer and Communications Security Reviews (ANBAR, UK). He has participated to more than 15 research projects sponsored by the European Commission, for four of these as project manager. He is currently project manager of the European Network of Excellene ECRYPT. In 2003, he has received the European Information Security Award in the area of academic research, and he received an honorary Certified Information Security Manager (CISM) designation by the Information Systems Audit and Control Association (ISACA). Since 1989, he is a Belgian expert in working group ISO/IEC JTC1/SC27/WG2 (Security Techniques and Mechanisms), where he has edited five international standards.

    Ingrid Verbauwhede received the Electrical Engineering Degree in 1984 and the Ph.D. Degree in applied sciences from the K.U. Leuven, in Leuven, Belgium in 1991. She was a lecturer and visiting research engineer at UC Berkeley from 1992 to 1994. From 1994 to 1998 she was a principal engineer first with TCSI and then with Atmel in Berkeley, CA. She joined UCLA in 1998 as an associate professor and the K.U. Leuven in 2003. Her interests include circuits, processor architectures and design methodologies for realtime, embedded systems in application domains such as security, cryptography, digital signal processing and wireless applications. Prof. Verbauwhede was the general chair of the IEEE International Symposium on Low Power Electronic Devices (ISLPED) in 2003. She is or was a member of several program committees, including DAC, ISSCC, DATE, CHES, ICASSP, SIPS, ASAP. She is the design community chair on the 42nd and 43th DAC executive community. She is a senior member of IEEE.

    View full text