Lattice-free half-half attack on Bitcoin and Ethereum

Public blockchains have a long history of attacks regarding their ECDSA signatures. Since all transactions are publicly available, it makes a perfect experimental field for cryptography attacks. A lattice attack has been recently published under the name “The curious case of the half-half Bitcoin ECDSA nonces” and experimented against Bitcoin. As a Swiss team loving the half and half cheese fondue, we had to investigate such attack. We discovered that our previous attack, “Polynonce“, is also applicable to this way of generating ECDSA nonces. We explain how in this post and show the results we obtained compared to the paper.

Previous attacks

To sign a message, ECDSA uses a value called a nonce. The nonce has to be randomly generated and unique for each message to be signed. For the Bitcoin and Ethereum secp256k1 curve, typical nonce values look like:

0x23fcec8739ec6612ac802e0b5529ec7dc34bed8e994e8019c66d30d961801cc8
0xdc2b71ec23803bdeda72fc10c6a7033a6b23d01c9f6560647c2c4cd91262adc1
0xc628cace75fcfa8c0a0cd18639b7af14e1194d9fffe999ee139b898b701c46e0
0x45b431b3bb8ed7e84209d99f529bc59555fa33c896d22a88b3301e08d3478694

ECDSA has a well-known and well-studied common pitfall, namely, nonce reuse. As its name suggests, if a nonce is ever reused for different signatures, the private key can be recovered from those signatures; then obviously, the first attack applied to blockchains was the nonce reuse attack. As soon as two different messages have been signed with the same nonce, the private key is compromised. This problem is usually solved by generating deterministic nonces following RFC 6979.

However, ECDSA nonces are so critical that even bias in their generation leads to private key recovery. Thus, more clever attacks were later applied to public blockchains involving lattice attacks. Those attacks allowed recovery of nonces that are shorter than expected, with lengths 64, 110, 128, and 160 bits. For example, nonces generated like the following are vulnerable to lattice attacks:

0x0000000000000000000000000000000010c361aa85f453d667fbb7d320576ea9
0x00000000000000000000000000000000a95d25b18bb61df61f328e0a91c9d53e
0x00000000000000000000000006afcace4e73a45bb0d98b3d25e7ba49b8b4cbbe
0x00000000000000000000000088b58851f592bc1782378fbc162c42b91ef52d16

The smaller the nonce is, the smaller is the dimension of the lattice used for the attack, and the smaller is the number of signatures needed to have a successful attack. According to the “Bias nonce sense” paper, two signatures with 128-bit nonces and a 3-dimensional lattice give a 75% probability of success (key recovery). From three signatures with 170-bit nonces and a 4-dimensional lattice, we get a 95% probability of success, and so on. A variant of the attack also applies to the discovery of nonces with shared prefixes and suffixes. For example, nonces generated like the following are also vulnerable to the previous attacks as well as common-suffix constructions:

0xc25f1a2a398cf22f20c08eda2457930114792ddbafe16f1866c3a9ce28aeaa15
0xc25f1a2a398cf22f20c08eda24579301263f58f69740fb6d928ae40fe38ebfd0

Polynonce

Another way of attacking ECDSA is by assuming an algebraic relation between the nonces. This approach was proposed by our team with the Polynonce attack. It assumes a polynomial relation between consecutive nonces $k_n$ and $k_{n+1}$ for unknown coefficients $a_i$ of the form:

$k_{n+1} = a_1 k_n + a_0$

$k_{n+1} = a_2 k_n^2 + a_1 k_n + a_0$

Then the Polynonce attack is able to recover the private key algebraically with a 100% success probability but it needs 4 signatures in the linear case, 5 for the quadratic case and so on. The attack mainly relies on solving polynomial equations and thus is very fast compared to lattice attacks. For more details, this attack will be presented at the upcoming DEFCON conference.

Single signature

All the previous attacks work with at least two different signatures from the same private key. However, some wallets like Ledger sign transactions with a single private key and then change it. This would explain why nowadays a lot of bitcoin public addresses are used only once. Here is a log scale plot of the dump of bitcoin (until block 752759 on September 5, 2022) limited to P2PKH transactions:

This shows that 92% of the public keys that are used for P2PKH transactions are only used once. This feature was mainly introduced to protect privacy but indirectly it also protect against the previous attacks. For Ethereum, the landscape is a bit different. We have analyzed 1759432087 signatures from 151429561 unique keys and we have made the linear scale plot:

This is quite different: 42% of public key are used for a single signature, 22% for two, 13% for three and so on. Thus, it seems that the usage of privacy preserving method is less deployed or applicable to Ethereum.

Half-half nonces

Recently, a new attack presents results when the nonces are generated from the upper half of the message hash concatenated with the upper part of the private key. Meaning that the nonce $k$ can be written as:

$k = h_{msb} || d_{msb}$

The novelty of such attack is that it allows recovery the secret key $d$ from a single signature. Similarly to previous lattice attacks, the expression for $k$ can be injected in the ECDSA formula, rearranged to form an instance of the Hidden Number Problem. Then this instance is solved with the BKZ algorithm. This technique is very powerful, as a single signature is sufficient and allows the attack to be applied on transactions issued by private keys used only once. The optimized version of the attack is able to recover a private key with a 99.99% success rate in 0.48 seconds. This is quite powerful but it took the authors 49 cpu-years to run the attack on the Bitcoin blockchain.

Polynonce applied to half-half nonces

While reading the new half-half attack, we figured out that Polynonce can also be adapted to recover such private key when used with half-half nonces. From an ECDSA signature $(r,s)$ , a message hash $h$ and a private key $d$ we have the following relation for the nonce:

$k = s^{-1}(h + rd) \mod q$

If we have two nonces $k_0$ and $k_1$ generated with the previous half-half formula, if we take the difference we get:

$k_0 - k_1 = s_0^{-1}h_0 - s_1^{-1}h_1 + \left(s_0^{-1}h_0 - s_1^{-1}h_1 \right)d = h_{0,msb} - h_{1,msb}$

We have found a linear equation on $d$ with all other values known. It gives a very fast way of solving the equation and recovering the private key $d$ . However, with Polynonce, two nonces and thus two signatures from the same private key are required. We have lost a big advantage w.r.t the previous attack. Nevertheless, since this attack variant is very fast, it may be applied first on public keys having multiple signatures and then the lattice attack can be applied on the remaining signatures.

Since the nonce difference in our equation depends only on $h_{0,msb} - h_{1,msb}$ , it allows us to recover all the nonces which were generated with the formula $k_i = h_{i,msb} || c$ where $c$ is a (secret) constant. It is a bit more generic, but a slight complication happens for Bitcoin. From an ECDSA signature $(r,s)$ the different signature $(r,-s)$ is also valid for the same message. As Bitcoin rejects the signature which has the largest $s$ value to avoid signature forgery, this has the drawback that we have to compute with both $-k$ and $k$ . Thus in our attack we have to guess the sign of each nonce.

This construction should have been also discovered by the previous lattice attacks on shared suffixes but only with 75% chance of success.

Results

We have run the analysis on the Bitcoin blockchain dump that we have used in our previous analysis (up to block 752’759 on September 5, 2022). We analysed 34 million public keys with at least 2 signatures. It took 10m23s on a 16-core AMD with 2.7 GHz clock.

We were able to find and recover 110 unique private keys. For example the transactions f3151fc1b29c117f1e4b67045b2d2901e7c289f596c242d7de123243fb623981 and f7bf1edf9d9cefa8421322c53bb00ecf118f99489171da72a9c11cf8d02b65f8 from the address 18zg6FG5pu8Bpq73L54AYvB8phTw3qCCR7 use the half-half method to generate nonces. Our script was able to recover the private key of that address:

0x3d6a2f408fe58dabce126718a06a655a4b49625572ab2eb1e9b6e094f11e1832

If we then recompute the nonces for such transactions we obtain:

0xf11a1456d7b0d9d13671f348928a84263d6a2f408fe58dabce126718a06a655a
0x49847dd298858c4ec1c059c11b22b3443d6a2f408fe58dabce126718a06a655a

We clearly see the least significant half of the nonce is equal the most significant half of the private key. However, as explained above, we are able to recover other interesting cases; for the same address we have found two nonces:

0x28c0a0b7399997a379ba83642e210a837d44ada61f63128ff1bff7742fcbdbe7
0x69ee6c0c3f1f477df4ff8b9f272809247d44ada61f63128ff1bff7742fcbdbe7

In this case the private key is not involved, as we rather find another unknown constant. We were also able to confirm the previous findings that some keys using such nonces were small keys: $d = {1, 2, 4, 7, 11, 24, 75, 77, 87, 128, 144, 549, 897}$ . Thus keys are easily recovered by bruteforcing, similarly to what has been done on the website https://privatekeys.pw. We did not find accounts with a non-zero balance as for the previous attack and we think that those accounts are monitored by bots and are emptied each time the balance changes.

Since this attack is quite fast, we have also run it on variations of the half-half nonce generation: $k = h_{lsb} || d_{msb}$ , $k = d_{msb} || h_{msb}$ and $k = d_{msb} || h_{lsb}$ but we did not find additional results.

We have also run the same attack on our Ethereum data set that we gathered during previous attacks. The attack took 49m11 on the same machine. No private keys were recovered with this attack.

It is interesting to see how creative the nonce generation constructions have been made in the past and we wonder if any other exotic constructions exist in the wild. Even though, those new attacks did not recover new private keys it does not mean that other weak nonce generation algorithms have been used for previous transactions and could be recovered by similar methods. If such problems are discovered the best way to protect the funds is to to transfer them at a new address which was not used for transaction before and leave the vulnerable addresses empty. The script of our attack and the results we obtained are available on the Github repository of the Polynonce attack.

Acknowledgments

Special thanks to my colleagues Marco Macchetti and Nils Amiet, for the original attack, ideas and for contributing to this blog post with fruitful discussions.