author | contributors | adapted_from | |
---|---|---|---|
0xB958d9FA0417E116F446D0A06D0326805Ad73Bd5 |
|
Although the challenge is only a few lines of code, solving it involves traveling back ~25 years to when the parameters of the secp256k1 curve were chosen.
<Image
src="/images/doge-secp256k1.png"
alt={A screenshot of Doge with various ECDSA related equations and graphs overlayed.
}
width={453}
height={467}
/>
Before we even get to the puzzle, we can take a closer look at the specification of secp256k1 (the curve used by Bitcoin/Ethereum). This was released by Certicom in 2000, but unfortunately, the parameter selection process wasn't super descriptive:
Parameters associated with a Koblitz curve admit especially efficient implementation. The name Koblitz curve is best-known when used to describe binary anomalous curves over
$\mathbb{F}_{2^m}$ which have$a,b\in{0,1}$ , [9]. Here it is generalized to refer also to curves over$\mathbb{F}_p$ which possess an efficiently computable endomorphism [7]. <span style={{ backgroundColor: "#092e52", color: "#7697ee" }} children="The recommended parameters associated with a Koblitz curve were chosen by repeatedly selecting parameters admitting an efficiently computable endomorphism until a prime order curve was found." />
For discussion about this, we can look at this Bitcoin Talk discussion. Despite the limited documentation, people were able to reverse engineer reasonable explanations for the parameter choices, including:
-
$p$ being chosen as a generalized Mersenne prime (helps with computing modular reductions). - The coefficients (
$a$ and$b$ ) of the curve equation being the smallest values you can choose that result in a prime order (the chosen$a$ and$b$ also allow for the GLV method optimization, which is even more possible explanation).
But despite all this reverse engineering, there was/is no good explanation for how the generator point
Well, there still isn't a great answer for this. In fact, even more questions arose when Gregory Maxwell discovered the point
This only adds to the mystery, since the "doubling" was never documented, doesn't seem necessary, and we don't know this SHA1 preimage. Regardless, the actual choice of
As you may know, the first step in ECDSA is to choose an integer
But with a toy private key, the property of
At this point, we can finally take a look at the CTF. As you can see, users submit bytecode that returns a valid msg hash + signature for a given private key. The challenge hardcodes a different s
value for everyone, and requires that the r
value has 9 leading zero bytes.
// SPDX-License-Identifier: Unlicense
pragma solidity ^0.8.17;
contract TinySig is IPuzzle {
// This is the address you get by using the private key `0x1`. For this
// challenge, make sure you do not use *your own* private key (other than to
// initiate the `solve` transaction of course). You only need to use the
// private key `0x1` for signing things.
address constant SIGNER = 0x7E5F4552091A69125d5DfCb7b8C2659029395Bdf;
/// @inheritdoc IPuzzle
function name() external pure returns (string memory) {
return "TinySig";
}
/// @inheritdoc IPuzzle
function generate(address _seed) external view returns (uint256) {
return uint256(keccak256(abi.encodePacked(_seed)));
}
/// @inheritdoc IPuzzle
function verify(uint256 _start, uint256 _solution) external returns (bool) {
address target = address(new Deployer(abi.encodePacked(_solution)));
(, bytes memory ret) = target.staticcall("");
(bytes32 h, uint8 v, bytes32 r) = abi.decode(ret, (bytes32, uint8, bytes32));
return (
r < bytes32(uint256(1 << 184)) &&
ecrecover(h, v, r, bytes32(_start)) == SIGNER
);
}
}
contract Deployer {
constructor(bytes memory code) { assembly { return (add(code, 0x20), mload(code)) } }
}
We know that choosing
To actually submit the solution, the easiest method to return h
, v
and r
in only 32 bytes of EVM code is to forward the call to another contract that has these values hardcoded. This is what the helper contract @0xkarmacoma and @eth_call deployed does.
// SPDX-License-Identifier: Unlicense
pragma solidity ^0.8.17;
contract Tinysolve {
mapping(address => bytes32) public hashes;
function setHash(bytes32 _hash) external {
hashes[msg.sender] = _hash;
}
fallback(bytes calldata) external returns (bytes memory res) {
res = abi.encode(
hashes[tx.origin],
uint8(28),
bytes32(0x00000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63)
);
}
}
For anyone interested in the secp256k1 parameter lore, I also recommend looking at this video. I think it's super cool that every single crypto transaction uses a