New Powerful Attacks On ECDSA In Bitcoin Systems

There is a wave of new powerful cryptographic attacks on bitcoin systems.

canstock10713649

There are several types of attacks:

  1. Attacks which use poor random number events.
    • It has already happened hundreds of times in the bitcoin blockchain since 2012.
    • Now there is a recent massive outbreak of such events. Here is a recent example from 1 Nov 2014. And here is an example from 29 Nov 2014.
  2. More advanced new attacks in which randoms are not identical but related (see our paper).
  3. Further attacks in which the private keys are related (also studied in the same paper).
  4. Attacks which use vulnerabilities of popular key management solutions such as BIP032.
  5. And there are new deadly COMBINATION attacks.
    They combine all the above vulnerabilities and lead to several new families of attacks which allow to recover a lot more keys than each of the above vulnerabilities alone.

Impact

Which systems are concerned? We don’t know exactly but in our opinion, most existing bitcoin storage and management systems are concerned:

  • bitcoin exchanges,
  • cold storage systems,
  • payment and wallets software systems,
  • electronic commerce solutions,
  • business key management solutions, etc.

We should also add that we don’t know if there exists a truly robust bitcoin key management standard which would be secure against powerful combination attacks such as described in our paper. More or less all bitcoin systems which do some systematic key management solutions and achieve some sort of separation between keys which allow to spend funds and those which allow only to receive money or monitor transactions, are vulnerable to large scale attacks where all the bitcoins in the whole system can potentially be stolen. The current bitcoin key management standard BIP032 is such that in theory it can be secure, but it will break apart as soon a number of pretty insignificant events or incidents in operation happens in some remote corners of various systems.
Some of our attacks also work across different systems which share no common setup, code or keys. Yet under certain circumstances all bitcoins within the remit of ALL systems can be stolen. Interestingly such vulnerabilities and resulting attacks/thefts cannot be detected by examining just one system. Events in several systems must be examined in combination in order to see if they can be exploited.

Mitigation Points

There is a well-known solution to this problem, it is the RFC6979 by Thomas Pornin.

However on the flip side no current bitcoin system which does not apply RFC6979 can really feel secure against attacks such as described in our paper. They should both upgrade their software and systems and also move all their bitcoins to new addresses.

We wonder why bitcoin developers and bitcoin foundation have been as usual so negligent about security so that this patch has NOT YET BEEN applied in bitcoin core software for like 18 months since January 2013. The fix was already applied by many companies such as Trezor, but not yet by bitcoin core client. Why?
Blockchain.info also uses a ridiculous method of asking the web browser to generate random numbers which opens avenues for attacks (added: few weeks after we wrote this words 100,000 USD were stolen from Blockchain.info).

The impact of our attacks could also be mitigated by multisig, however as usual there will be secure and insecure ways of using multisig. Ironically a large percentage of bad random events in the recent outbreak come from multisig applications. There is a very small percentage of multisig events in the blockchain, like less than 1%, and among these events there is an large proportion of vulnerable signatures with bad random events.

 

Added in 2015: there are now better ways to do key management than BIP032 in bitcoin, see this paper.

 

One Comment

  1. It is well known that ECDSA is very vulnerable to weak RNGs to generate the secret nonce, and we’ve wanted to use deterministic signing (RFC6979) in Bitcoin Core for a long time. However, Bitcoin Core currently relies on OpenSSL for ECDSA operations, and changing this is very nontrivial due to consensus risk. OpenSSL recently incorporated an option with similar effect (not exactly RFC6979, but at least using private key and message data in the construction of the nonce), which is however not yet available in a release (last I checked).

    Also, every known case of a weak nonce in the blockchain was created by other software as far as I know, because OpenSSL has (despite many other problems) a pretty good RNG, so changing it in Bitcoin Core wouldn’t have mattered.

    Nonetheless, we need to follow best practices and give the right example, so when possible, we will use deterministic nonces. This will likely be soon, as we may be switching the signing code from OpenSSL to libsecp256k1 (which allows passing in the nonce explicitly).

Leave a Reply to Pieter Wuille Cancel reply

Your email address will not be published.