Curta CTF Puzzle #6: Uncertainty Principle

Motivation

The objective of the puzzle was to require a methodology of study rather than an intricated understanding of the game, the program is rather easy to understand, but the solution may require competitors to approach it in a programatic way to capture the flag.

Since many contestors were relying on intense fuzzing or symbolic testing, I wanted to create a puzzle that would make disecting the puzzle into it's parts implausible, since any change they made to the core logic, would be modifying the gasleft() method. Hence the name of the puzzle Uncertainty Principle, and the question that arises:

How do we measure something, that the sole act of measurement changes its value?

The puzzle






























contract EventHorizon is IPuzzle {
    uint256 constant PLANK_CONSTANT = 0x111;
    uint256 constant PLANK_LENGTH = 0xF;
    uint256 constant PHISICAL_SPHERE = type(uint32).max;

    function generate(address _seed) external view returns (uint256) {
        return _gammaFn(uint256(uint160(_seed))) | PLANK_CONSTANT;
    }

    function verify(uint256 _start, uint256 _solution) external view returns (bool) {
        uint256 _axis;
        uint256 _momentum;
        uint256 _position;

        while (_start & PHISICAL_SPHERE > 0) {
            _position = _axis++ * 4;
            _momentum = _gammaFn(_solution) & PLANK_LENGTH << _position;
            for (uint256 _i; _i < _momentum >> _position; _i++) {
                continue;
            }
            _start -= _momentum;
        }

        return true;
    }

    function _gammaFn(uint256 _xyz) internal view returns (uint256) {
        return uint256(keccak256(abi.encodePacked(_xyz, gasleft())));
    }
}

The puzzle logic can be then reduced to escaping the following loop:






while (_start & 0xFFFFFFFF > 0) {
    _position = _axis++ * 4;
    _momentum = keccak256(_solution, gasleft()) & 0xF << _position;
    for (uint256 _i; _i < _momentum >> _position; _i++) {continue}
    _start -= _momentum;
}

Let's first analyze it line by line to understand the challenge:

while(_start & 0xFFFFFFFF > 0){
The objective of the puzzle is to make the last 8 bytes of start be 0, else you'd fall into an infinite loop.
_position = _axis++ * 4;
The position increases by 4 each time, pointing at each of the bytes of start from right to left.
_momentum = keccak256(_solution, gasleft()) & 0xF << _position;
The momentum can have a value of 1 byte in 1 position at each time. While position increases, momentum can have the following values:




0x...0000000X // being X any byte value (from 0x0 to 0xF)
0x...000000X0
0x...00000X00
...

for (uint256 _i; _i < _momentum >> _position; _i++) {continue}
Depending on the X value of momentum, enter a loop X amount of times (consuming different amounts of gas).
_start -= _momentum
Substract from start the X value of the momentum at the position.

TL/DR: The objective of the puzzle, is to provide a solution such that at each iteration, the keccak of (solution, gasleft()) will provide a momentum such that the last 8 bytes of start get substracted to 0.

Challenge: solution then acts as a key mechanism, that has to align every pin at the same time to make it work, with the difficulty that we cannot know the shape of the following pin, since we cannot know gasleft() until we reached it. And also, if one of the pins is not perfectly aligned, instead of reverting (ideal for fuzzing), the transaction will enter a neverending loop called "the blackhole". And given that the solution depends on the gas, there are 2 values to be searched by the users, as a both solution and gaslimit need to be properly set.

Solving it

As stated before, understanding the puzzle is not the hard part, but creating a methodology to solve it without touching it, can become challenging. I'm going to propose a few options on how to approach it, in order to avoid some of the most painful difficulties.

To navigate through the event horizon, one must to either have no mass, or to master the gamma function

The Theoretical Physicist approach

Given a starting point, lets say 0x......123456789abdcef, one can know in advance that it's gonna need to enter the loops with the following values:

First byte (right to left), perform 15 loops (because of line (4) as it has to null the last byte of start: 0xF)
Second byte, 14 (0xE) loops
…
Eight byte, 8 loops

Theoretically, since the EVM is very weird but also very deterministic, one could follow each PUSH, DUP, SWAP, ... and pre-calculate all of the gasleft at each of the steps, and go look for a solution that satisfies the following:

keccak(solution, gasleft(1)) & 0x0000000F = 0xF
keccak(solution, gasleft(2)) & 0x000000F0 = 0xE
keccak(solution, gasleft(3)) & 0x00000F00 = 0xD
...

Since gasleft(2) = gasleft(1) + 15 loops, and gasleft(3) = gasleft(2) + 14 loops, the solution requirement could theoretically be precalculated all at the same time. But when you look deep inside, the EVM is a very misterious machine, and performing such calculations can cause multiple headaches, tho the possible approach is interesting to point out.

The Experimental Physicist approach

One thing experimental physicists know for sure, is that their experiment doesn't represent the real world, but a controlled representation of the real world. So in a way, modifying the contract to emit the gasleft(), can bring a lot of data about how the actual contract behaves.





function _gammaFn(uint256 _xyz) internal view returns (uint256) {
    uint256 _gasLeft = gasleft();
    console.log(_gasLeft);
    return uint256(keccak256(abi.encodePacked(_xyz, _gasLeft)));
}

Finding the solution to the above puzzle is much easier than the previous one, and forces the user to understand the implications of such challenge. While solving this one, the user may encounter a few insights that may become helpful to solve the actual problem.

The methodology to solve this puzzle can be later replicated by reading the gasleft from the memory stack instead of the console.log. In the end, the user will have to iteratively do:

measure gasleft(1)
find solution so that keccak(solution, gasleft(1)) = 0x_______F
measure gasleft(2)
find solution so that (1) & keccak(solution, gasleft(2)) = 0x______E_
measure gasleft(3)
find solution so that (1) & (2) & keccak(solution, gasleft(3)) = 0x_____D__
...

When the user have created the test scenario and tools to calculate the solutions for the modified puzzle, then calculating it from the original one is only 1 debugger and 8 iterative solution calculations away. With debugging tools such as https://remix.ethereum.org/, one can access the memory slot to know what was gasleft() returning at each step, and redo the solution calculation.

The Solidity Engineer approach

Something pleasing to notice is that the start point is generated via the following formula:



function generate(address _userAddress) external view returns (uint256) {
    return keccak256(_userAddress, gasleft()) | 0x111;
}

Where the 0x111 was clearly put there to avoid a lucky address to generate a starting point with 8 trailing 0s, avoiding the whole loop in the first entrance (as massless objects aren't dragged by the blackhole). But a smart user can know that by tweaking the gasleft (number between ~100k and 30M), he can score a start point such that some of the left bytes of the 8-trailing-bytes are 0, finalizing the loop earlier (for ex. start = 0xabcdef12345|00000111 would only require 3 0x1 loops).

One can calculate that there are high chances of a precise gasleft value providing 4 (or up to 5 if lucky) leading 0s. So the first challenge would be to arrive to the start generation point with that precise gasleft.

calculate gasLeft for lucky address
simulate tx with gasLimit = gasLeft
measure from the memory slot the arriving gasleft
calculate gasDelta = desiredGasLeft - gasLeft
re-simulate tx with gasLimit = desiredGasLeft + gasDelta

Notice: because of EIP-150, and Curta contract calling the generate method, the actual gas sent is 63/64 of the gas that the execution has at the time of puzzle.generate(msg.sender), so tweaking the gasLimit may require some calculations or iterations

repeat until desiredGasLeft = gasLeft

Having set one of the unknown parameters (initialGas), one needs to define the other unknown (solution) such that the other 4 bytes are substracted. So one can know that there is a 1/65.536 possibility that a random seed would be correct. Given that the gas sent is <30M, and that the possibilities are relatively high, fuzzing becomes a good enough tool to approaching this problem.

Shadowy Super Coder approach

Is it possible to solve all within Foundry fuzzing? Without going into the deepness of the debugger? Let's give it a try:

One of the painful challenges of the puzzle is the "spooky action at distance" that both the generate and verify methods have. One needs to coordinate the execution at the same time, since changing the generate has an effect on the posterior verify call.

Fuzzing is a great tool, but is not the best to do in a E2E test, where the RPC is usually having to process the whole tx, thousands of times until reaching the desired outcome. And we want to maintain everything in a controlled scenario. So maybe the best thing to do is to fork Curta contract altogether, using vm.etch to even have it on the exact contract address, to avoid changes in gas because of the leading 0s of its address.

If one decides to fork Curta, one can also modify:

puzzle.verify(puzzle.generate(msg.sender), _solution)

Into:

console.log(puzzle.generate(msg.sender))

Notice: the puzzle.verify part is posterior to puzzle.generate so it shouldn't have any effect on the gas consumption up to that point.

And call Curta.solve{gaslimit: x}({puzzle:6, solution:0xffff...}) to fuzz x the first of the unknowns of the puzzle, requiring the return to have 0s on the left side of the last 8 bytes. Then, rollbacking Curta to the original, one can verify that the start point should be the same for the gaslimit sent (as no previous opcodes were modified), and can decide to fuzz the solution, leaving to the fuzzer test all the complexity of "measuring gasleft" at every point.

This approach might bring some implications to be considered:

since the failing outcome is an infinite loop, for fuzzing, perhaps is more convenient to have a 200k gas limit and need to perform 4 iterations (1/65k probability of scoring), than have a 30m gas limit and need to perform 3 iterations (1/4k probability of scoring)
because of the amount of the leading 0s of the solution modifies the gas spenditure, one can request solution >= 1<<255, to maintain the spenditure because of solution fixed (Notice, there's a reason why this particular solver decided to fuzz his solution with preceding bytes, instead of fuzzing from scratch).

Conclusions

Either of the mentioned methodologies can guide the player through the blackhole, without getting stuck at the event horizon. Since Curta is a race to capture the flag, there's no ideal roadmap to follow, but the one the user feels more comfortable with.

Comments

I had a great time thinking about this game, I wanted to create something which solution was Turing complete, and that would force y'all to approach it in a scientific mindset. To be honest I was planning to raise it to uint42, but figured out that 8 bytes would be challenging enough to achieve such goal, without the need of a lot of processing hours to get the right seed. I do hope you had a good time trying to coordinate the generate and verify entanglement, I was really surpised about the speed of the answers it got, and got really sorry for that one guy who sent 5M gaslimit to get stuck in the event horizon, twice.