Joachim Breitner's Homepage

Nadia Heninger and I just have put the preprint version of our paper “Biased Nonce Sense: Lattice Attacks against Weak ECDSA Signatures in Cryptocurrencies”, to be presented at Financial Crypto 2019, online. In this work, we see how many private keys used on the Bitcoin, Ethereum and Ripple blockchain, as well as in HTTPS and SSH, were used in an unsafe way and hence can be compromised. The resulting numbers are not large – 300 Bitcoin keys, with a balance of around $54 – but it shows (again and again) that it can be tricky to get crypto right, and that if you don’t get it right, you can lose your money.

Brief summary

When you create a cryptographic signatures using ECDSA (the elliptic curve digital signature algorithm), you need to come up with the nonce, a 256 bit random number. It is really important to use a different nonce every time, otherwise it is easy for someone else to take your signatures (which might be stored for everyone to read on the Bitcoin blockchain) and calculate your private key using relatively simple math, and with your private key they can spend all your Bitcoins. In fact, there is evidence that people out there continuously monitor the blockchains for signatures with such repeated nonces and immediately extract the money from compromised keys.

Less well known, but still nothing new to the crypto (as in cryptography) community is the that an attacker can calculate the key from signature that use different, but similar nonces: For example if they are close by each other (only the low bits differ), or if they differ by exactly a large power of two (only the high bits differ). This uses a fancy and powerful technique based on lattices. Our main contribution here is to bridge crypto (as in cryptography) and crypto (as in cryptocurrency) and see if such vulnerabilities actually exist out there.

And indeed, there are some. Not many (which is good), but they do exist, and clearly due to more than one source. Unfortunately, it is really hard to find out who made these signatures, and with which code, so we can only guess about the causes of these bugs. A large number of affected signatures are related to multisig transactions, so we believe that maybe hardware tokens could be the cause here.

Observing programming bugs

Even though we could not identify the concrete implementations that caused these problems, we could still observe some interesting details about them. The most curious is certainly this one:

One set of signatures, which incidentally were created by an attacker who emptied out accounts of compromised keys (e.g. those that are created with a weak password, or otherwise leaked onto the internet), was using nonces that shared the low 128 bits, and hence revealed the (already compromised) private key of the account he emptied out. Curiously, these low 128 bits are precisely the upper 128 bits of the private key.

So it very much looks like the attacker hacked up a program that monitors the blockchain and empties out accounts, and probably did so using a memory unsafe language like C, and got the size of the buffers for nonce and key wrong, so maybe they did properly filled the nonce with good random data, but when they wrote the secret key, the memory locations overlapped and they overrode parts of their randomness with the very non-random secret key. Oh well.

Do I need to worry?

Probably not. The official blockchain clients get their crypto right (at least this part), and use properly random nonces, so as a user you don’t have to worry. In fact, since 2016, the Bitcoin client uses deterministic signatures (RFC6979) which completely removes the need for randomness in the process.

If you are using non-standard libraries, or if you write your own crypto routines (which you should only ever do if you have a really really good reason for it) 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.

Discrete logarithm in secp256k1 with lookup table

In the course of this work I wanted to find out if small nonces ( < 2⁶⁴) were used even when the key created only one of these – the lattice-based attacks need at least two signatures to work. So I created code that calculates the discrete log in the secp256k1 curve up to an exponent of ( < 2⁶⁴). This is made feasible using a lookup table for smaller exponents ( < 2³⁹ in our case – just large enough to still fit into 2.2TB of RAM).

This exercise turned out to be not very useful; we did not find any additional keys, but I had fun writing up the program, implemented in C and working very close to the raw data, juggling big binary files mmap’ed into memory, and implementing custom lookup indices and such. In the hope that this might be useful to someone, I share the code at https://github.com/nomeata/secp265k1-lookup-table.