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.