Horizontal collision correlation attack on elliptic curves

Elliptic curves based algorithms are nowadays widely spread among embedded systems. They indeed have the double advantage of providing efficient implementations with short certificates and of being relatively easy to secure against side-channel attacks. As a matter of fact, when an algorithm with constant execution flow is implemented together with randomization techniques, the obtained design usually thwarts classical side-channel attacks while keeping good performances. Recently, a new technique that makes randomization ineffective, has been successfully applied in the context of RSA implementations. This method, related to a so-called horizontal modus operandi, introduced by Walter in 2001, turns out to be very powerful since it only requires leakages on a single algorithm execution. In this paper, we combine such kind of techniques together with the collision correlation analysis, introduced at CHES 2010 by Moradi et al., to propose a new attack on elliptic curves atomic implementations (or unified formulas) with input randomization. We show how it may be applied against several state-of-the art implementations, including those of Chevallier-Mames et al., of Longa and of Giraud-Verneuil and also Bernstein and Lange for unified Edward’s formulas. Finally, we provide simulation results for several sizes of elliptic curves on different hardware architectures. These results, which turn out to be the very first horizontal attacks on elliptic curves, open new perspectives in securing such implementations. Indeed, this paper shows that two of the main existing countermeasures for elliptic curve implementations become irrelevant when going from vertical to horizontal analysis.

1. Among the unified formulas, we especially focus on the Edward’s ones in [9] introduced by Bernstein and Lange since they lead to efficient doubling and addition computations compared to the Weierstrass case [16].

2. We shall sometimes need to consider the known value as a pair of variables: in this case we will use the notation (X,Y) instead of X.

3. In contexts where the adversary is not allowed to choose the algorithm input but knows it, the first step just aims at fixing the input value for the rest of the attack.

4. Possibly, the observations acquisition phase may mix horizontal and vertical techniques. In this case, the attack will be termed Rectangle.

5. For readability reasons we do not recall the full patterns but the interested reader can find them in [17].

6. Guidelines are given in [17] to define the dummy operations in a pertinent way.

7. We also performed experiments with the correlation defined in (9) and observed that the attacks were always less efficient than with the correlation in (10), which is in line with the analysis conducted in Section 4.4

8. In this context, the SNR simply equals ω/4σ ².

9. Contrary to the attacks described in Section 4, the attack against Algorithms 2 and 3 does not try to detect two similar operations with a common operand but tries to detect when a same operand is manipulated two times. Even if this scenario is not exactly the one analyzed in this paper, we think that the corresponding attack stays efficient as it is based on the same principles.

10. For instance, if L is related to the manipulation of two shares M ₁ and M ₂ of O, then one can for instance assume that half of the V _i corresponds to M ₁ and the other half to M ₂. Moreover, (2) is a particular case of (11) where all manipulated data are assumed to be equal to O.

11. If t is odd, it can be right-padded with a zero.

Authors and Affiliations

1. ANSSI, 51, Bd de la Tour-Maubourg, 75700, Paris, France

   Aurélie Bauer, Eliane Jaulmes, Emmanuel Prouff, Jean-René Reinhard & Justine Wild

Corresponding author

Correspondence to Emmanuel Prouff.

The short version of this paper has been published in [8]

Appendix A: Extension to Higher Orders

The leakage definition given in 2 stands for contexts where instantaneous leakage about the implementation secret parameter exists. When the latter condition is not verified, the adversary must consider several intermediate values simultaneously to reveal sensitive information. In this context, side-channels are usually called multivariate by opposition with the first class of attacks that are called univariate. Except 2, the framework introduced in Section 2.1 and the formalism given in Section 2.2 continue to be valid. For completeness, we generalize the definition of the leakage coordinates in (2) to encompass contexts where several intermediate results must be observed to reveal information about a sensitive internal processing O(k,X):

where φ _i and β _i are similar as in (2) and where V _i refers to the value manipulated at time t _i . ^{Footnote 10}

When the general definition (11) is used in place of (2) to model the instantaneous leakage, a prerequisite for a multivariate SCA to be possible is that there exists at least one tuple of coordinates of L that statistically depends on O(s,X). Actually for Horizontal SCA the number of tuples must be high enough for the involved statistical tools to be effective.

Appendix B: Implementations of Modular Multiplications

In Section 4.3, we argued that an adversary may deal with Assumption 1 by using collisions attack. For such a purpose, we focussed on the classical Long Integer Multiplication (LIM) and we showed that horizontal collisions attacks can be applied to distinguish when two multiplications are performed with at least one common operand. Obviously, in practice, there are several other techniques to implement the modular multiplication U⋅V mod p between two t ω-bit long integers. Let us argue here briefly that our attack still applies efficiently in some of these other cases.

Among all existing modular multiplication techniques, two main methods can be highlighted: those which perform long multiplications [1, 13, 24] followed by a global reduction [5, 36] and those where multiplication and reduction are interleaved [14, 46]. The sequence of operations related to those implementations always contain the products U[i]⋅V[j] that were targeted in our attack. Hence, by applying the same approach as described in Section 4.3, it stays possible to distinguish the two following cases: “Case (1)” when the device processes two multiplications with independent operands and “Case (2)” when the device computes the multiplication of two related operands that jointly depend on a secret bit s. We recall hereafter some classical modular multiplication techniques.

Schoolbook Multiplication.

This technique, also called Long Integer Multiplication (LIM), is a digit-by-digit multiplication algorithm where the products U[i]⋅V[j] are executed in the row order. An alternative approach has been introduced by Comba in [24]: it uses the same principle as the LIM but the products are taken in the column order.

Karatsuba-Ofman.

This technique is very popular and is considered as one of the most efficient way to multiply two integers. If t=2n, then U and V can be expressed as follows^{Footnote 11}:

where U _H ,V _H (resp. U _L , V _L ) represent the n most significant ω-bit words of U and V (resp. the n least significant ω-bit words). The core idea of Karatsuba-Ofman multiplication is to process UV as follows:

and

It may be checked that the processing of (13) and (14) may be done with 3 multiplications (instead of 4 with the LIM). By applying the idea recursively, the overall complexity is roughly reduced from t ² to \(t^{\log _{2}(3)}\). When such a multiplication algorithm is used, only the t final elementary multiplications U[i]V[i], with i∈[1,t] can be involved in a collision attack such as described in Section 4.3. This strongly decreases the efficiency of our attack.

Booth’s Multiplication.

The idea here is to rewrite the representation of the operands (for example by using a signed representation) in order to increase the number of zeroes in the latter. The advantage of this method is that it allows a faster multiplication. The multiplication is then performed as the LIM.

Montgomery’s Multiplication.

The principle of this method is to perform the modular multiplication using modular reductions easier to compute, by introducing an integer R, called the radix. R is defined such that R=2^tω>p. Every element \(x \in \mathbb {F}_{p}\) is then represented by X=x R m o d p. This is called the Montgomery representation of x. Assume two elements are given in their Montgomery representation U and V. To compute the Montgomery representation Z of their product, we first compute the standard multi-precision multiplication of U and V which is a number of size at most p ². By applying Montgomery reduction to this result, we obtain Z. Thus, to multiply two elements in Montgomery representation, we only need to perform a single multi-precision multiplication followed by a Montgomery reduction. No division is needed.

In practice, this operation can be made more efficient by interleaving the multiplication and reduction steps. In our case, we will still be able to identify the elementary multiplications needed for the attack.

Appendix C: Projective Coordinates

In Weierstrass (3), points on elliptic curves are described in affine representation, namely using their (x,y)-coordinates. While it seems to be the simplest way to describe points over (E), addition and doubling formulas using affine coordinates require to compute the inverse of an element in \(\mathbb {F}_{p}\), which is a very costly operation. This drawback led embedded systems developers to use other kinds of representations, such as for instance the projective coordinates that enable to perform point operations without requiring any field inversion. Moreover this type of representation avoids the need to resort to special treatment for the point at infinity. This is an advantage compared to the affine coordinates, since it prevents side-channel attacks that exploits the difference of representation between \(\mathcal {O}\) and non-zero points.

To make it clear a point P=(x,y) can be expressed in projective coordinates by a triplet (X:Y:Z) such that X=x Z and Y=y Z. Following this definition, point (X:Y:Z) is the same as point (λ X:λ Y:λ Z) for λ≠0.

Obviously other types of point representations share the same properties listed above with the projective coordinates. Jacobian coordinates or even the Edwards’ ones are examples of such representations. They require a small number of elementary operations in order to add or double points on (E).

Reprints and permissions