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

Presented at Black Hat Europe 2020 Virtual, Dec. 9, 2020, 12:30 p.m. (40 minutes)

Although one of the most popular signature schemes, ECDSA presents a number of implementation pitfalls, in particular due to the very sensitive nature of the random value (known as the nonce) generated during the signing algorithm. It is known that any small amount of nonce exposure or bias can in principle lead to a full key recovery by solving the hidden number problem (HNP). This has been practically exploited in many attacks in the literature, taking advantage of implementation defects or side-channel vulnerabilities. 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 talk, we uncover LadderLeak, a novel class of side-channel vulnerabilities in implementations of the Montgomery ladder used in ECDSA scalar multiplication. The vulnerability is 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 less than 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 to solving the HNP (an approach originally due to Bleichenbacher), and this lets us practically break LadderLeak-vulnerable ECDSA implementations over the sect163r1 and NIST P-192 elliptic curves. In doing so, we achieve several significant computational records in practical attacks against the HNP.


Presenters:

  • Akira Takahashi - PhD Student, Aarhus University
    Akira Takahashi is currently a PhD student at Cryptography and Security Group, Aarhus University, Denmark. He was an intern in the Cryptography Research Laboratory at NTT Corporation, Japan and has also worked as a software developer at Richie Oy, Finland. His research interests cover implementation attacks on public key cryptographic algorithms and construction of efficient two-/multi-party computation protocols. He has given talks about his research projects in different top-tier conferences, including Eurocrypt [1], Euro S&P, and CHES [2]. [1] https://www.youtube.com/watch?v=b6RgEu2ekAs [2] https://www.youtube.com/watch?v=SL1gt53n8-I
  • Diego De Freitas Aranha - Associate Professor of Computer Science, Aarhus University
    Diego F. Aranha is an Associate Professor of Computer Science at Aarhus University, Denmark. His professional experience is in Cryptography and Computer Security, with a special interest in the efficient implementation of cryptographic algorithms and security analysis of real-world systems. He received the Google Latin America Research Award for research on privacy twice, and the MIT TechReview's Innovators Under 35 Brazil Award for his work in electronic voting. He has given talks about his research in more than 100 occasions in 10 different countries, including Black Hat Asia and DEF CON Voting Village.

Links:

Similar Presentations: