Paper 2020/615

LadderLeak: Breaking ECDSA With Less Than One Bit Of Nonce Leakage

Diego F. Aranha, Felipe Rodrigues Novaes, Akira Takahashi, Mehdi Tibouchi, and Yuval Yarom

Abstract

Although it is one of the most popular signature schemes today, ECDSA presents a number of implementation pitfalls, in particular due to the very sensitive nature of the random value (known as the nonce) generated as part of the signing algorithm. It is known that any small amount of nonce exposure or nonce bias can in principle lead to a full key recovery: the key recovery is then a particular instance of Boneh and Venkatesan's hidden number problem (HNP). That observation has been practically exploited in many attacks in the literature, taking advantage of implementation defects or side-channel vulnerabilities in various concrete ECDSA implementations. However, most of the attacks so far have relied on at least 2 bits of nonce bias (except for the special case of curves at the $80$-bit security level, for which attacks against $1$-bit biases are known, albeit with a very high number of required signatures). In this paper, we uncover LadderLeak, a novel class of side-channel vulnerabilities in implementations of the Montgomery ladder used in ECDSA scalar multiplication. The vulnerability is in particular present in several recent versions of OpenSSL. However, it leaks less than $1$ bit of information about the nonce, in the sense that it reveals the most significant bit of the nonce, but with probability $<1$. Exploiting such a mild leakage would be intractable using techniques present in the literature so far. However, we present a number of theoretical improvements of the Fourier analysis approach to solving the HNP (an approach originally due to Bleichenbacher), and this lets us practically break LadderLeak-vulnerable ECDSA implementations instantiated over the sect163r1 and NIST P-192 elliptic curves. In so doing, we achieve several significant computational records in practical attacks against the HNP.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. ACM CCS 2020
DOI
10.1145/3372297.3417268
Keywords
side-channel attackcache attackECDSAOpenSSLMontgomery Ladderhidden number problemBleichenbacher's attackgeneralized birthday problem
Contact author(s)
dfaranha @ eng au dk
ra135663 @ students ic unicamp br
takahashi @ cs au dk
takahashi akira 58s @ kyoto-u jp
mehdi tibouchi br @ hco ntt co jp
mehdi tibouchi @ normalesup org
yval @ cs adelaide edu au
History
2020-08-22: revised
2020-05-25: received
See all versions
Short URL
https://ia.cr/2020/615
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/615,
      author = {Diego F.  Aranha and Felipe Rodrigues Novaes and Akira Takahashi and Mehdi Tibouchi and Yuval Yarom},
      title = {LadderLeak: Breaking ECDSA With Less Than One Bit Of Nonce Leakage},
      howpublished = {Cryptology ePrint Archive, Paper 2020/615},
      year = {2020},
      doi = {10.1145/3372297.3417268},
      note = {\url{https://eprint.iacr.org/2020/615}},
      url = {https://eprint.iacr.org/2020/615}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.