Lattice Attacks against Elliptic-Curve Signatures with Blinded Scalar Multiplication

Dahmun Goudarzi 1, 2, 3 Matthieu Rivain 1 Damien Vergnaud 2, 3
2 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
DI-ENS - Département d'informatique de l'École normale supérieure, CNRS - Centre National de la Recherche Scientifique : UMR 8548, Inria de Paris
Abstract : Elliptic curve cryptography is today the prevailing approach to get efficient public-key cryptosystems and digital signatures. Most of elliptic curve signature schemes use a \emph{nonce} in the computation of each signature and the knowledge of this nonce is sufficient to fully recover the secret key of the scheme. Even a few bits of the nonce over several signatures allow a complete break of the scheme by lattice-based attacks. Several works have investigated how to efficiently apply such attacks when partial information on the nonce can be recovered through side-channel attacks. However, these attacks usually target unprotected implementation and/or make ideal assumptions on the recovered information, and it is not clear how they would perform in a scenario where common countermeasures are included and where only noisy information leaks via side channels. In this paper, we close this gap by applying such attack techniques against elliptic-curve signature implementations based on a blinded scalar multiplication. Specifically, we extend the famous Howgrave-Graham and Smart lattice attack when the nonces are blinded by the addition of a random multiple of the elliptic-curve group order or by a random Euclidean splitting. We then assume that noisy information on the blinded nonce can be obtained through a template attack targeting the underlying scalar multiplication and we show how to characterize the obtained likelihood scores under a realistic leakage assumption. To deal with this scenario, we introduce a filtering method which given a set of signatures and associated likelihood scores maximizes the success probability of the lattice attack. Our approach is backed up with attack simulation results for several signal-to-noise ratio of the exploited leakage.
Type de document :
Communication dans un congrès
Roberto Avanzi; Howard Heys. Selected Areas in Cryptography - SAC 2016, Aug 2016, St. John’s, Canada. Springer, Selected Areas in Cryptography - SAC 2016. 〈http://www.engr.mun.ca/~sac2016/〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01379249
Contributeur : Damien Vergnaud <>
Soumis le : mardi 11 octobre 2016 - 12:07:49
Dernière modification le : jeudi 26 avril 2018 - 10:29:10

Identifiants

  • HAL Id : hal-01379249, version 1

Collections

Citation

Dahmun Goudarzi, Matthieu Rivain, Damien Vergnaud. Lattice Attacks against Elliptic-Curve Signatures with Blinded Scalar Multiplication. Roberto Avanzi; Howard Heys. Selected Areas in Cryptography - SAC 2016, Aug 2016, St. John’s, Canada. Springer, Selected Areas in Cryptography - SAC 2016. 〈http://www.engr.mun.ca/~sac2016/〉. 〈hal-01379249〉

Partager

Métriques

Consultations de la notice

256