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. 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.
In this talk, we discuss recent algorithmic developments allowing to go even further, and for instance break ECDSA in practice with less than 1 bit of leakage. We also discuss how those developments relate to concrete vulnerabilities in cryptographic libraries, and what can done to protect against them.
Biography. An alumni of ENS (Paris, France), Mehdi Tibouchi obtained his Ph.D. in computer science from Univ. Paris VII and Univ. Luxembourg in 2011. He is now distinguished researcher at NTT Corporation (Tokyo, Japan) and guest associate professor at Kyoto University (Kyoto, Japan). His research interests cover various mathematical aspects of public-key cryptography and cryptanalysis.
