A New Class of ECDSA Signature Vulnerability Observed in the Wild on the Bitcoin Blockchain
"Our analysis illustrates how vulnerabilities in a custom ECDSA implementation can not only reveal private keys, but can also be used to compromise Bitcoin-pseudonymity and addresses to (online) personas."
"We report on a new class of ECDSA signature vulnerability observed in the wild on the Bitcoin blockchain that results from a signature nonce generated by concatenating half of the bits of the message hash together with half of the bits of the secret signing key."
"We give a lattice-based attack for efficiently recovering the secret key from a single signature of this form."
"We then search the entire Bitcoin blockchain for such signatures, and identify and track the activities of an apparently custom ECDSA/Bitcoin implementation that has been used to empty hundreds of compromised Bitcoin addresses for many years."
"This attack has a simple countermeasure: deterministic ECDSA nonce generation as described in, for example, RFC 6979, which is implemented in the core library for Bitcoin, Ethereum, and other cryptocurrencies."
"Our much more powerful and exact lattice attack has allowed us to identify 90,000 vulnerable signatures in the Bitcoin blockchain by exploiting this previously unnoticed vulnerable nonce pattern, where the methods of Breitner and Heninger were only able to identify 54 signatures of this form."
"This is a nice example of a cryptographic implementation mistake leading to interesting cryptanalysis: our attack easily extends to other nonce constructions from contiguous chunks of d."