Cryptology ePrint Archive: Report 2019/321

Horizontal Collision Correlation Attack on Elliptic Curves

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

Abstract: Elliptic curves based algorithms are nowadays widely spread among embedded systems. They indeed have the double advantage of providing efficient implementations with short certi cates 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 uni fied 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 uni ed 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 rst 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.

Category / Keywords: implementation / side-channel analysis, elliptic curves implementations, ECDSA, horizontal attacks, collision attacks.

Original Publication (with minor differences): Cryptography and Communications, Volume 7

Date: received 22 Mar 2019

Contact author: e prouff at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20190329:125750 (All versions of this report)

Short URL: ia.cr/2019/321


[ Cryptology ePrint archive ]