Solidity CTF: Mirror Madness
I recently launched a CTF with prizes totaling 1.75 Ether coordinated from this mainnet contract: https://etherscan.io/address/0x7cd03C9f1D2dc95358B1992e9afc857aeaab45D5 . Of that total only 0.75 Ether was claimed.
Today we are going to do a detailed walkthrough of how to solve this CTF, we will cover an investigation strategy and then an edge case of elliptic curve signature generation. Starting out, the contract contains four state objects: a signer address, an owner address, a boolean called paused, and an array of winner addresses. Its initial state contains 0.25 Ether and the code doesn’t contain a clear way getting more Ether than that.
As for the functions, there are two that would help us reach our goals of breaking the smart contract: one called withdraw which will send the caller of the contract the funds it contains if the bool paused is false, and one called win which adds a requested address to the winners mapping. These give us two clear goals: find a way to set paused to false and find a way to send a message from the owner address.
A cursory check of the addresses provided for owner and sender shows that these are not contract accounts. Since they are not smart contracts a priori it seems impossible to send any messages from them, but they do contain the additional 1.5 ether so there must be some way to unlock them. With no clear path here we turn back to the smart contract.
As of the start of the CTF there were three transactions listed on etherscan. The first is contract creation which won’t give us more information. The second reverted, perhaps it was an accidental transaction. The third is a call to lock which succeeded and told us that (r,s) is a valid signature of the hash of “Pause”. If we could get the private key of signer from this transaction all of ethereum would be broken so lets take a closer look at the reverted transaction.
We can move over to remix and initialize the contract with the signer and owner addresses from the contract. After doing so we can try the unlock transaction with the same data as was submitted to the contract and debug it to see what is causing the revert to happen. Going through the remix debugger we notice something weird, the revert is occurring after the signature validation. It is reverting because the contract isn’t locked and required(paused) doesn’t get paused. However what this means is that if we call lock with the signature then call unlock with the same data the second unlock will work. This is called a signature replay and if we replay the signature to unlock then call withdraw we can claim the first 0.25 ether!
However this is slightly odd, how did someone manage to call unlock instead of lock? If we examine the transactions we notice something weird, that the r and s values that are submitted with the first unlock transaction are the same as the r and s. That’s odd… When you call unlock it checks that either ecrecover(hash2, r, s, 27) or ecrecover(hash2, r, s, 28) are equal to the address. But this means that (r,s) signs both hash1 and hash2. Which should be impossible, by strict probability this has a 1/(2²⁵⁶ — 432420386565659656852420866394968145599)⁴ chance of happening.
Given how small the chance of this happening is the best assumption is there must be some algorithm which allows you to compute a duplicate signature of two different hashes. So there are two options either (1) We try to derive the algorithm our self (2) We research to find the algorithm is described. If we try approach 2 and are lucky we will find this paper https://www.di.ens.fr/david.pointcheval/Documents/Papers/2002_cryptoA.pdf
Here we are going to take approach (1) so that the algorithm becomes more clear. If our main goal is to find matching signatures, we start with r, hash1, and hash2 values then try to derive the private key and s value from them. So we pick a random k and calculate r = f((k * g)), then if we assume we have a d_a private key we can calculate s = k^-1 (h_1 + d_a * r). To calculate the d_a we observe that the elliptic curve points r and -r have the same x coordinate and we try to preform signature verification of hash2 using the r and s we have derived.
Indeed if we calculate x = -(hash1 + hash2)/2r mod n is the private key of the signing address from the contract. So then we can transfer the 0.5 eth in that account to our account! But what about the final 1 ether and the winner mapping?
The answer to this is a simple but unintuitive step from the previous one. Our algorithm calls for a random k but what is its actual value? To get the value we calculate k = s^-1 (hash1 + xr). If we check if this private key has any ether associated with it then we will find out that it has a balance of 1 ether and that it is the owner address. Using this we can pay ourselves and call the win function to add our real address to the winners mapping.
This challenge has taught us a few things:
- Failed transaction can contain valuable information, such as signatures which can be replayed
- There is an edge case in the ECDSA which allows the generation of signatures with identical (r,s).
- Many important facts about ECDSA are buried deep in papers or small forums.
