Last week a monster in Ethereum’s dark forest revealed itself to me. 16 hours prior to their reveal I had laid down cryptographic bait after hearing of its existence from tux. I expected it, but it was still surprising to refresh Etherscan and see that all my Ether was gone.

This monster was watching Ethereum for an obscure mistake deep in the process of creating a transaction: the reuse of a number while signing a transaction. I went searching for this creature, laid bait, saw it in the wild, and found unexplained tracks. To understand how this bot works, we need to begin by reviewing ECDSA and digital signatures.

(You can also read this post on Twitter)

ECDSA

Underpinning the two largest cryptocurrencies - Bitcoin and Ethereum - is the elliptic curve digital signature algorithm, or ECDSA. As the name suggests ECDSA is a scheme for producing digital signatures. These signatures are how we prove ownership of our accounts and assets. Each signature proves two things:

1. That you possess some secret called a private key. Every private key is tied to a publicly known key called a public key. Your crypto “address” is a public key.
2. That you used your private key to sign a particular message. In our case messages are transactions.

ECDSA works because of the fact that you can easily use a private key to generate a public key, but you can’t use a public key to derive a private key. You can, however, use a signature to back out a private key under some limited conditions. This gets somewhat technical, but bear with me.

To generate signatures ECDSA takes a private key d, a random number k, and the hash of a message h. It combines these with Q the public key associated with the private key d, as well as two numbers that are standardized by the ECDSA algorithm, G and n. Together these are used to compute a digital signature with the following algorithm:

r = k * G \mod n

s = \frac{h + d * r}{k} \mod n

Together r and s form a digital signature.

What's the value in a nonce?

The random number k used in ECDSA signatures is critical. It should never be revealed and should only ever be used once. That is why this random number is also called a nonce and I’ll use nonce from here on out when referring to k. If an attacker learns what nonce was used to generate a particular signature then they can recover the private key used to sign that message. With some algebra the following formula can be derived:

d=(s*k-h)*r^{-1} \mod n

Similarly, if a nonce is ever reused across two different signatures then the private key used to sign those signatures can be recovered. Again, with some algebra we can derive the nonce used from the following equation:

k=(h_1-h_2)*(s_1-s_2)^{-1}\mod n

With the nonce we then can recover the private key as above.

So how can we tell if a nonce has been reused?

Recall the formula for generating r in the ECDSA algorithm r = k * G mod n. Given that G and n are simply numbers that remain fixed the only variable that changes from signature to signature is k, the random number. As a result if k is reused across two messages then their signatures will have the same r, which is why k is never meant to be reused!

With this in mind we now know what to look for to spot when ECDSA nonces have been reused in signing Ethereum transactions: two transactions from the same account with the same r but different s values. I had heard from tux that there were bots watching for such mistakes to be made, and at a weekend hackathon I set out to see that for myself.

A quick note of reassurance: regular end users shouldn't worry much about these attack vectors. There's nothing you could do to reuse a nonce or expose that nonce to the public. It's something the developers of cryptography libraries should worry about, not you.

Creating cryptographic bait

My plan was simple: to lure this dark forest creature out I would send two transactions with the same r and leave a bit of ETH in that account as bait. If anyone was watching then they could recover the private key I used and take the ETH.

(Originally I tried to do this by crafting Bitcoin transactions by hand but I was new to Bitcoin tooling and didn’t succeed in the day hackathon I was at)

To create nonce-reuse-bait bot bait, I needed to force my transactions to be signed with the same number twice. Luckily this is not easy to do. You can’t do it with MetaMask. With some digging into the imports of ethers.js, a popular web3 library, I found what looked like the library it used for elliptic curve cryptography.

var drbg = new HmacDRBG({
      hash: this.hash,
      entropy: bkey,
      nonce: 1, // changed from "nonce"
      pers: options.pers,
      persEnc: options.persEnc || 'utf8',
    });

(Don't try this at home!)

I set the nonce equal to 1! Then I made a new private key and loaded it up with 0.04 ETH and wrote a simple script that transferred ETH to myself.

const ethers = require("ethers")
  
async function main(){
    const privateKey = "not-leaking-it-this-way"
    
    let wallet = new ethers.Wallet(privateKey)
    console.log("Using wallet:", wallet.address)
    
    const provider = new ethers.providers.JsonRpcProvider("rpc-endpoint")
    let signer = wallet.connect(provider)
    
    const tx = await signer.sendTransaction({
        to: wallet.address,
        value: ethers.utils.parseEther("0").toString(),
        gasLimit: 45000,
    })

    console.log(tx)
}
  
main()

I ran this twice in quick succession sending two transactions that immediately landed on-chain. Since my nonce was set to 1 these two transactions should have the same r, but different s values. A quick script confirmed this:

robert@mbp nonce-reuse-bait % node get_r_s.js
  Transaction 1
  r: 0x340709f674d030dda4aa8794bffb578030870bdfe583e7f41aea136a7ca1ed94
  s: 0x3e5b92d8c5a2a033c9e5eb53ff2946681b28ab82fa5b17d0a9c48d139e78fe2c
  
  Transaction 2
  r: 0x340709f674d030dda4aa8794bffb578030870bdfe583e7f41aea136a7ca1ed94
  s: 0x2c17cf960d1af7602f875afc56d01eddcc67bb03e962877444ed8d4c1287ab7a

Now that these transactions had been included on-chain the private key behind this account was now compromised to anyone who was watching. My bait had been laid.

A glimpse of the deep

I had immediately refreshed the Etherscan page for the compromised account as soon as the second transaction had been included. Nothing had happened; the money was still sitting there. Through the next few hours I refreshed again, growing more puzzled and wondering if I made a mistake as time passed. Still nothing happened and I went to sleep.

The next morning I refreshed and found my balance had been drained! After 16 hours a single transaction to an unknown account had taken the 0.04 ETH I left in the account.

The monster had reared its head; it was watching Ethereum for transactions with the same r, recovering their private keys, and taking their money. I was puzzled that it had taken so long for my money to be taken. After all this it was definitely possible to programmatically extract value this way. Why wouldn’t someone watching extract this value immediately? One answer could be that they were waiting to see if I moved more value into my account. Regardless I smiled at the success of my experiment and thought to myself that I would probably never think it was cool that my private key had been leaked again.

What’s more on a first glance it looked like this bot had taken other people’s money as well.

This account had a steady stream of ETH being sent to it from a number of different accounts. Only once did it send ETH, and that was to pay for gas fees for three ERC20 transfers. In total there was about $3,700 in this account.

To look for other instances of ECDSA nonce reuse attacks I wrote a script to quickly check whether an account’s transactions included an r value more than once. I plugged in the second address that had sent the attacker ETH and found that the account had reused the same r in more than 1 transaction.

robert@mbp nonce-reuse-bait % node get-tx-history.js
  
  Same r found!
  r: 0xf0d7b10f398357f7d140ff2be1bea9165d32238360ad0f82911235868be7c6e1
  hash: 0xb5d2454d7380bfa7ac75ec76f15eecb56e60941429153081fe799fb53a7ff901
  r: 0xf0d7b10f398357f7d140ff2be1bea9165d32238360ad0f82911235868be7c6e1
  hash: 0x9e459be7fa9950835a3c2594d3440c684fed05fa8e12e8088cc7776c4afb364c
  
  
  Same r found!
  r: 0x41d43fd626c24e449ac54257eeff271edb438bbabbc9bee3d60a5bd78dc39d6d
  hash: 0x670f66ff71882ae35436cd399adf57805745177b465fdb44a60b31b7c32e4d16
  r: 0x41d43fd626c24e449ac54257eeff271edb438bbabbc9bee3d60a5bd78dc39d6d
  hash: 0x374180005946ef3b1906ee1677f85fa62eb5a834aa0241b4c9c74174bca26a07

This strengthened my conviction that this bot was watching Ethereum for ECDSA nonce reuse. Interestingly this user had two separate instances of reusing a nonce in two different transactions. Again, this creature of the dark forest had moved surprisingly slowly when their victim made a mistake. It took a few hours for the victim’s money to be taken.

After this I looked at the next two addresses sending the attacker ETH. To my surprise I found that these accounts sent the attacker all their ETH, but had never reused an ECDSA nonce! After investigation I discovered that 20 different accounts had sent a transaction to the attacker’s address, but only 9 were accounts which previously reused a nonce.

What about the other 11? How did the attacker get their money? I’m not sure. One answer could be that this creature is using other strategies for recovering private keys, such as checking for accounts that use common words, phrases, or numbers as their private keys. There are also more complicated ways to exploit poor nonce generation. But still, this is speculation, and none of the tracks I investigated seemed to give any definitive answers.

A creature of the dark forest may have revealed itself. But what it is or where it will strike next remains a mystery.

---

Thank you to tux for the original idea and telling me a story about your own adventures with this bot. Also, thanks to niftynei for reviewing this blog post prior to publishing.