Recent Developments in Side-Channel Analysis on Elliptic Curve Cryptography Implementations

Louiza Papachristodoulou, Lejla Batina and Nele Mentens

Introduction

The emerging need for secure communications in embedded systems is constantly threatened by sophisticated side-channel analysis (SCA) attacks. SCA attacks exploit various types of physical leakage of secret information from cryptographic devices. The physical leakage originates also from the power consumption [1], the electromagnetic radiation [2, 3], and the timing behavior [4] of the device. We focus on attacks exploiting power consumption leakage, namely power analysis attacks. These attacks are based on the principle that a switching event of a signal inside a device causes a current to be drawn from the power supply or to be drained to the ground, which is illustrated in Fig. 3.1 on the basis of a CMOS inverter. When the input switches from a logical 1 to a logical 0 or vice versa, the output makes the opposite transition, respectively charging or discharging the output capacitor. When the input remains constant, there is no switching current and no switching power consumption. This physical behavior is exploited by power analysis attacks to extract data that are processed internally in the device.

Within this area of power analysis of cryptographic implementations, there are various methods of analysis, such as Simple Power Analysis (SPA), Differential Power Analysis (DPA), and Collision Analysis (CA). SPA uses a single power trace or several traces, i.e., the instantaneous power consumption of a single run of an algorithm over a certain period of time. DPA uses statistical methods to extract

L. Papachristodoulou • L. Batina

Digital Security Group, Radboud University, P.O. Box 9010, 6500 Nijmegen,

GL, The Netherlands e-mail:
This email address is being protected from spam bots, you need Javascript enabled to view it

L. Batina

e-mail:
This email address is being protected from spam bots, you need Javascript enabled to view it
N. Mentens (B)

KU Leuven, ESAT/COSIC & IMinds, Kasteelpark Arenberg 10, 3001 Leuven, Belgium e-mail:
This email address is being protected from spam bots, you need Javascript enabled to view it

Fig. 3.1 Switching current at the output of a CMOS invertor

information from multiple traces [1]. CA exploits the leakage of two portions of traces when the same intermediate values are used [5].

Naive implementations of public-key cryptosystems are usually susceptible to SPA attacks because of, e.g., the use of conditional branches. In the RSA cryptosystem, these branches are present in the modular exponentiation algorithm when it is executed using an iteration of modular squarings and modular multiplications. The analogy of modular exponentiation in RSA is point multiplication in elliptic curve cryptosystems. Naive implementations use the double-and-add method consisting of consecutive point doublings and point additions, where a point addition is only executed when the corresponding key bit equals 1. This way, a single power trace reveals a logical 1 in the key through the presence of a point addition. One type of countermeasures balance the computation such that the power traces always look similar regardless of the processed key bits. Other countermeasures randomize the computation such that an attacker is not able to correlate the power traces with the processed data.

This chapter starts with an overview of elliptic curves used in cryptography in Sect.3.2. Since the power analysis attacks we discuss, focus on the scalar multiplication algorithm, Sect. 3.3 presents different options for this algorithm. Section3.4 elaborates on power analysis attacks on elliptic curve cryptosystems, while Sect. 3.5 gives an overview of countermeasures at the algorithmic level.