Researchers recently identified vulnerabilities in cryptographic signatures for Bitcoin, Ethereum, and Ripple, that allowed attackers to calculate private keys and, consequently, steal any crypto in that wallet. In total, the researchers calculated hundreds of Bitcoin private keys and dozens of Ethereum, Ripple, SSH, and HTTPS private keys using this unique form of cryptanalytic attack.
In the paper Biased Nonce Sense: Lattice Attacks against Weak ECDSA Signatures in Cryptocurrencies, researchers utilize a method to calculate private keys by analyzing Bitcoin signatures. The researchers were also able to apply these techniques to Ethereum and Ripple.
That said, these vulnerabilities only occur in edge cases where code is not implemented by developers properly, or likely occurred because of faulty multi-signature hardware. The research emphasizes the resiliency of the cryptographic schemes used by cryptocurrencies, as well as highlights the importance of proper implementation.
Background on Research
Whenever crypto holders make a transaction, they are required to create a cryptographic signature using an elliptic curve digital signature algorithm (ECDSA). In this algorithm, the software comes up with an arbitrary number that is used just once for communication—this number is called a nonce.
It is critical that the software signs each transaction with a different nonce, otherwise hackers can (rather easily) find and calculate the signers’ private key. There is even evidence that hackers continuously monitor the blockchain for these kinds of repeated nonces, extracting money from compromised keys.
What’s less well-known is that attackers can calculate keys from signatures that use different, but similar nonces. For example, if nonces have characters that are similar at the beginning of the signature, or if the nonce has characters that are similar at the end of a signature, then some big bad terrible thing will happen.
What the Researchers Say
CryptoSlate contacted both authors of the paper: Dr. Nadia Heninger is an associate professor of computer science at the University of California. Joachim Breitner, is a senior researcher at DFINITY. According to Dr. Heninger, the vulnerability was described as follows:
“The ECDSA digital signature algorithm requires generating a random number for each signature, which is often called a “nonce” (This is different from the nonces used in cryptocurrency mining). If these random values used in the signatures are not generated properly, in some cases, an attacker can compute the private signing keys. The types of nonce vulnerabilities that we exploited were implementations that generated values that were much shorter than they should have been, or values that shared most or least significant bits.”
And, using some advance math called lattices, the two were able to crack some of these wallet addresses and find the private keys:
“For the nerds in the audience, lattice algorithms allow us to find small solutions to underconstrained systems of linear equations. There are a number of crypotanalytic techniques that use lattice algorithms as a building block.”
As stated in the paper, any non-uniformity in the generation of these signature nonces can reveal private key information. Given a sufficient number of signatures, hackers can compute private keys and gain access to a user’s wallet and drain its funds.
Do Crypto Users Need to Worry?
According to Dr. Heninger and Breitner, the vast majority of cryptocurrency users need not worry:
“The only reason this would happen is if there is some type of bug in the digital signature code.”
Furthermore, as long as developers use the proper techniques and documented methods to ensure user security, the signature scheme is considered secure:
“As far as we know, ECDSA is a secure digital signature algorithm if implemented correctly. We concluded that these were not common implementations based on the fact that we only found a few thousand vulnerable signatures out of nearly a billion Bitcoin signatures that we examined.”
Furthermore, these vulnerabilities are only “specific to distinct implementations. Furthermore, the authors speculate that the faulty implementationn could possibly be a result of a few multifactor security devices:
“The mention of multifactor security is specific to the case of the signatures we found with 64-bit nonces on the Bitcoin blockchain. Nearly all of them were part of multisig addresses, which is not the usual case on the blockchain, hence our guess of the source. There has since been some further speculation about the specific implementation.”
Now, there are ways for developers to implement ECDSA without the vulnerabilities described in the paper, even for hardware devices. According to Breitner:
“The official blockchain clients get their crypto right… since 2016, the Bitcoin client uses deterministic signatures (RFC6979) which completely removes the need for randomness in the process [eliminating the possibility of the kind of attack employed by the researchers]. If you are using non-standard libraries, or if you write your own crypto routines… you should make sure that these use RFC6979. This is even more important on embedded devices or hardware tokens where a good source of randomness might be hard to come by.”
Profitable for Attackers?
Ultimately, these kinds of attacks are not cost-effective given the amount of time, electricity, and computational power needed to conduct them—even with this new tool added to their arsenal:
“Given that attackers are already exploiting other cryptographic vulnerabilities to compromise wallets, it seems likely that this will be added to their arsenal. However, if one has to pay for the computing time to do the computation, it is probably not a cost-effective attack given the balances that we found associated with vulnerable keys.”
At the end of the day, the research reassures cryptocurrency users that the cryptography underlining Bitcoin and other digital currencies is sound. With tens of thousands of people scrutinizing the underlying code for these systems, it is a testimony that the core security schemes, if used properly, still adequately protect the user—for now.Posted In: Academia, Hacks