This post explains how I beat the capture-the-flag crypto challenge “Web3” during ImaginaryCTF.
Description
Is this a cryptocurrency or a cryptography challenge? Yes.
Please try to find the private key of an Ethereum account
0x891cf17281bF2a57b25620b144A4E71B395603D4, and the private key is in the format ofb"ictf{??????}".rjust(32, b"\x00").hex(). This account has made some transactions on Sepolia Testnet, btw.You don’t need a lot of computational resources for this challenge. Intended solution works in less than 10 mins, single threaded.
Indeed, we can locate one transaction signed by the Ethereum account in question.
Solution
Spoiler
Since we know all but 6 bytes of the private key, we should look at its relationship to the public key in this setting. Ethereum public keys are points on the `secp256k1` elliptic curve. Like all discrete logarithm groups, `secp256k1` only provides security proportional to the square root of the cardinality of the key space. In our case instead of using a simple bruteforce attack on 6 bytes which would be a 48-bit bruteforcing problem, we can use discrete-log methods that are roughly equivalent to a 24-bit bruteforce.It should be noted that a curve point cannot be extracted from the problem statement directly because the Ethereum address is a cryptographic hash of a curve point. For this challenge, we need to recover the public key from the transaction signature. This can be done fairly easily with Ethereum tooling.
My first go-to to compute a discrete logarithm was SageMath.
It barely worked, requiring an hour of computation and all of my RAM.
While Sage is a great tool, it is not very suited for this computation.
Thus, I rewrote the solution using the coincurve library which provides fast secp256k1 operations.
Finally, before computing the discrete logarithm, we need to tweak the public key a little bit to remove the known parts of the flag by subtracting them. This can be done using the matching homomorphic operations on the curve points.
Putting it all together, we get this script.
Note that the web3.py library is currently incompatible with Python 3.11 and later.