Paper 2019/023

Biased Nonce Sense: Lattice Attacks against Weak ECDSA Signatures in Cryptocurrencies

Joachim Breitner and Nadia Heninger

Abstract

In this paper, we compute hundreds of Bitcoin private keys and dozens of Ethereum, Ripple, SSH, and HTTPS private keys by carrying out cryptanalytic attacks against digital signatures contained in public blockchains and Internet-wide scans. The ECDSA signature algorithm requires the generation of a per-message secret nonce. If this nonce is not generated uniformly at random, an attacker can potentially exploit this bias to compute the long-term signing key. We use a lattice-based algorithm for solving the hidden number problem to efficiently compute private ECDSA keys that were used with biased signature nonces due to multiple apparent implementation vulnerabilities.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Financial Cryptography and Data Security 2019
Keywords
Hidden number problemECDSALatticesBitcoinCrypto
Contact author(s)
nadiah @ cs ucsd edu
History
2019-04-30: revised
2019-01-09: received
See all versions
Short URL
https://ia.cr/2019/023
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/023,
      author = {Joachim Breitner and Nadia Heninger},
      title = {Biased Nonce Sense: Lattice Attacks against Weak ECDSA Signatures in Cryptocurrencies},
      howpublished = {Cryptology ePrint Archive, Paper 2019/023},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/023}},
      url = {https://eprint.iacr.org/2019/023}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.