LadderLeak: Breaking ECDSA with Less than One Bit of Nonce Leakage

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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
Original languageEnglish
Title of host publicationProceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security
PublisherACM
Pages225-242
Number of pages18
ISBN (Electronic)978-1-4503-7089-9
DOIs
Publication statusPublished - 2 Nov 2020
EventThe 27th ACM Conference on Computer and Communications Security, 2020 - Online
Duration: 9 Nov 202013 Nov 2020
Conference number: 27
https://sigsac.org/ccs/CCS2020/index.html

Conference

ConferenceThe 27th ACM Conference on Computer and Communications Security, 2020
Abbreviated titleCCS 2020
Period9/11/2013/11/20
Internet address

Keywords

  • side-channel attack
  • cache attack
  • ECDSA
  • OpenSSL
  • Montgomery ladder
  • hidden number problem
  • Bleichenbacher’s attack
  • generalized birthday problem

Fingerprint

Dive into the research topics of 'LadderLeak: Breaking ECDSA with Less than One Bit of Nonce Leakage'. Together they form a unique fingerprint.

Cite this