Side-Channel Attacks on ECC

Attacking implementations of elliptic curve cryptography (ECC) with natural protection against side-channel attacks, e.g., implementations using Edwards curves, is quite challenging. This form of elliptic curves, proposed by Edwards in 2007 [15] and promoted for cryptographic applications by Bernstein and Lange [18], showed some advantages compared to elliptic curves in Weierstrass form. For instance, the fast and complete formulas for addition and doubling put these types of curves forward as more appealing for memory-constrained devices and at the same time resistant to classical simple power analysis (SPA) techniques. Recently, due to the work of Renes et al., complete formulas have been published for curves in Weierstrass form [14].

Although considered a very serious threat against ECC implementations, differential power analysis (DPA), as proposed in [1], cannot be applied directly to

ECC-based algorithms and protocols. Soon after the first DPA paper by Kocher et al., Coron showed how to attack the scalar multiplication operation by DPA techniques [31]. However, the idea does not apply to other ECC protocols where the secret is either not a scalar involved in the scalar multiplication algorithm or a scalar that is used only once, like, e.g., in ECDSA or in ephemeral Diffie-Hellman. The latter is incompatible with the requirement of DPA to collect a large number of power traces of computations on the same secret data.

When attacking ECDSA, two secrets could be of interest for the attacker. She could go for an ephemeral key or a secret scalar that becomes a part of the signature. The idea of attacking the ephemeral key is to get reveal a few key bits (from just one measurement) and then proceed with some sort of theoretical cryptanalysis to recover the remaining bits. This kind of special attacks is often used in combination with lattice techniques similar to [35, 36], in order to derive the whole private key from a few bits of multiple ephemeral keys.

The richness of the mathematical structures behind public-key systems and other algorithm-dependent features, that are special for both RSA and ECC, created opportunities for many unique side-channel attacks exploiting those features. The first work to propose new techniques was the paper of Fouque and Vallette [37]. They introduce a new attack against scalar multiplication (or modular exponentiation) that looks for identical patterns within power traces due to the same intermediate results occurring within the computation. In this way, the so-called “doubling attack” only requires two queries to the device. This work has started a new line of research on new attack techniques that reside somewhere between SPA and DPA, of which the most notable are collision [5, 37-41] and template attacks [36, 42, 43].

Collision-based attacks exploit the fact that when processing the same data, the same computations will result in the same (or very similar) patterns in the power consumption traces. However, although the idea is easily verifiable, the efficiency of most of the so far introduced collision-based attacks is shown only on simulated traces; no practical experiments on real ECC implementations have confirmed those results. To the best of our knowledge, only two practical collision-based attacks on exponentiation algorithms were published, each of which rely on very specific assumptions and deal with very special cases. Hanley et al. exploit collisions between input and output operations within the same trace [44]. On the other hand, Wenger et al. performed a hardware-specific attack on consecutive rounds of a Montgomery ladder implementation [45]. However, both attacks are very restrictive in terms of applicability to various ECC implementations as they imply some special implementation options, such as, e.g., the use of Lopez-Dahab coordinates, where field multiplications use the same key-dependent coordinate as input to two consecutive rounds. A class of attacks similar to collision-based attacks is sometimes also called horizontal attacks and they were first defined for modular exponentiation by Clavier et al. [46]. Their attack is inspired by Walter’s work [38] and it requires a unique power trace, in this way rendering classical randomization countermeasures. In another work [47], the authors have introduced a general framework enabling to model both horizontal and classical attacks (the latter are called vertical attacks in this work) in a simple way.

Their follow-up paper [41 ] introduced horizontal attacks for ECC but the results were obtained from simulations only and no real measurements were used.

We observe that the trend of attacks is shifting more toward this type of collision and horizontal attacks as known randomization-based countermeasures are effective in protecting ECC against SPA and DPA attacks. Therefore, in the remainder of this chapter we focus on collision-based/inspired attacks and we give a detailed example of one such attack i.e. the Online Template Attack (OTA).

< Prev   CONTENTS   Source   Next >