More EVM Puzzles - Part 4

June 7, 2022 by patrickd

This concludes the series on Dalton Sweeney (opens in a new tab)'s "10 more EVM puzzles" (opens in a new tab) collection. If you're looking for the start, take a look at Part 1.

Puzzle #8

00      34        CALLVALUE
01      15        ISZERO
02      19        NOT
03      6007      PUSH1 07
05      57        JUMPI
06      FD        REVERT
07      5B        JUMPDEST
08      36        CALLDATASIZE
09      6000      PUSH1 00
0B      6000      PUSH1 00
0D      37        CALLDATACOPY
0E      36        CALLDATASIZE
0F      6000      PUSH1 00
11      6000      PUSH1 00
13      F0        CREATE
14      47        SELFBALANCE
15      6000      PUSH1 00
17      6000      PUSH1 00
19      6000      PUSH1 00
1B      6000      PUSH1 00
1D      47        SELFBALANCE
1E      86        DUP7
1F      5A        GAS
20      F1        CALL
21      6001      PUSH1 01
23      14        EQ
24      6028      PUSH1 28
26      57        JUMPI
27      FD        REVERT
28      5B        JUMPDEST
29      47        SELFBALANCE
2A      14        EQ
2B      602F      PUSH1 2F
2D      57        JUMPI
2E      FD        REVERT
2F      5B        JUMPDEST
30      00        STOP

? Enter the calldata: 0x

Puzzle solved!

Yes, that's right, I solved it immediately without reading by simply pressing enter on accident. What the heck just happened here?

00      34        CALLVALUE        [0]
01      15        ISZERO           [1]
02      19        NOT              [0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe]
03      6007      PUSH1 07         [0x07, 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe]
05      57        JUMPI            []
06      FD        REVERT
07      5B        JUMPDEST         []

Right at the start it checks whether the call value sent is zero, which is strange since we were never given a chance to specify it.. Anyway, the result of this check is then inverted with NOT. Note that inverting a number 1 of type uint256 flips all of its bits, that means it doesn't turn into 0 but into the biggest number possible minus one. Since JUMPI jumps for any value different from 0, it would've jumped no matter which value we'd have sent since any non-zero value would have resulted in 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff after the inversion. So it seems we can just completely ignore this part...

08      36        CALLDATASIZE     [0]
09      6000      PUSH1 00         [0, 0]
0B      6000      PUSH1 00         [0, 0, 0] (destOffset, offset, size)
0D      37        CALLDATACOPY     []
0E      36        CALLDATASIZE     [0]
0F      6000      PUSH1 00         [0, 0]
11      6000      PUSH1 00         [0, 0, 0] (value, offset, size)
13      F0        CREATE           [ADDRESS]
14      47        SELFBALANCE      [0, ADDRESS]
15      6000      PUSH1 00         [0, 0, ADDRESS]
17      6000      PUSH1 00         [0, 0, 0, ADDRESS]
19      6000      PUSH1 00         [0, 0, 0, 0, ADDRESS]
1B      6000      PUSH1 00         [0, 0, 0, 0, 0, ADDRESS]
1D      47        SELFBALANCE      [0, 0, 0, 0, 0, 0, ADDRESS]
1E      86        DUP7             [ADDRESS, 0, 0, 0, 0, 0, 0, ADDRESS]
1F      5A        GAS              [GAS, ADDRESS, 0, 0, 0, 0, 0, 0, ADDRESS] (gas, address, value, argsOffset, argsSize, retOffset, retSize)
20      F1        CALL             [SUCCESS, 0, ADDRESS]
21      6001      PUSH1 01         [1, SUCCESS, 0, ADDRESS]
23      14        EQ               [1, 0, ADDRESS]
24      6028      PUSH1 28         [0x28, 1, 0, ADDRESS]
26      57        JUMPI            [0, ADDRESS]
27      FD        REVERT
28      5B        JUMPDEST         [0, ADDRESS]

We sent no calldata but it'll still attempt copying it to memory here. Then it'll deploy that empty calldata as initialization bytecode which doesn't return anything, so basically we're successfully deploying an empty contract. This contract is then immediately called. The puzzle obtains its own account balance using the SELFBALANCE opcode which is used for the first time here, and it would send all of this balance during the call if it had any. As things stand, this is a call made against an address that contains empty bytecode and the call succeeds. You shouldn't be surprised by that, after all we already know that we don't have to write STOP at the end of a contract. So an empty contract is just like a contract that has a single STOP instruction.

Furthermore, we can even send invalid calldata that'll result in the CREATE opcode to fail and return the zero-address. Calls made to the zero-address will also succeed without reverting since it too has empty bytecode, like any uninitialized address. It's actually harder to fail this puzzle than to win it since we'd have to make the call fail by deploying runtime bytecode that'll revert.

29      47        SELFBALANCE      [0, 0, ADDRESS]
2A      14        EQ               [1, ADDRESS]
2B      602F      PUSH1 2F         [0x2F, 1, ADDRESS]
2D      57        JUMPI            [ADDRESS]
2E      FD        REVERT
2F      5B        JUMPDEST         [ADDRESS]
30      00        STOP             [ADDRESS]

Finally, it checks whether the SELFBALANCE after the successful call is the same as the balance was before the call.

So what was actually supposed to happen here? I think the first part was supposed to ensure that value must have been sent to the puzzle. Then all of this value would have been sent to the contract created using the specified calldata. This contract would have needed to send all of this value back to the puzzle contract to pass the final check. But it wouldn't have been able to do that via the CALL opcode since that would execute the puzzle code again which would send it away to another contract it created. Instead, the contract we created via calldata would've had to use the SELFDESTRUCT opcode to inject the value back into the puzzle during the call.

The key takeaway here is that although uint256 are used as booleans by the EVM (0 is false, non-0 is true) doesn't mean that inverting it via NOT opcode will result in flipping the boolean, rather than that it'll flip every single byte in the uint256, and that is something that can be easily missed!

Puzzle #9

00      34        CALLVALUE
01      6000      PUSH1 00
03      52        MSTORE
04      6020      PUSH1 20
06      6000      PUSH1 00
08      20        SHA3
09      60F8      PUSH1 F8
0B      1C        SHR
0C      60A8      PUSH1 A8
0E      14        EQ
0F      6016      PUSH1 16
11      57        JUMPI
12      FD        REVERT
13      FD        REVERT
14      FD        REVERT
15      FD        REVERT
16      5B        JUMPDEST
17      00        STOP

? Enter the value to send:

Right away, we're storing the CALLVALUE we send to offset 0x0 in memory. Then 2 new opcodes are introduced:

You've probably heard about SHA3 before. It's a one-way hashing algorithm, the EVM makes this algorithm available to us via this instruction and passes it the data to hash via memory. Two items will be consumed from stack: The "offset" specifying where it should begin hashing the data and the "size" telling it when to stop. The resulting 256 bit long hash will be pushed as a new item onto the stack. Here, we'll always be hashing the first memory slot, which are the first 32 bytes (0x20).

The SHR opcode stands for SHift Right, and that's exactly what it does on the bit level. It too consumes two items from the stack: The number of times to shift right and the value that should be shifted. For example, if the first item would be a 2 and the second a 17 (00010001), the result would be 4 (00000100). In case of this puzzle, we're always shifting 248 (0xF8) times and the value being shifted is the SHA-3 hash that was calculated just before.

In case of the stack, we're shifting a value with 256 bits though: 256 - 248 is 8, and that means that everything except the first byte (most-left, or highest order) of the hash is shifted into nothingness. Finally the usual comparison and jump: Only if this byte is equal to 0xA8 the puzzle is solved!

In summary: We need to find an integer value to send whose hash starts with 0xA8.

Since hashing algorithms are one-way functions, there's no way to say which values will produce it without guessing. Luckily it's only about the first byte, and that should be pretty easy to stumble upon even when just continuously increasing the value by one.

So what's the laziest way to do this? A shellscript! Don't judge me, it works and it only took me a couple minutes:

rm solutions/solution_9.json
while [ $? == 1 ]
     printf "$COUNTER\nn\n" | npx hardhat play
     rm solutions/solution_9.json

Granted, it's not performant what so ever, but I didn't expect it to be a high number anyway, and it wasn't. It was 47, which is 0xa813484aef6fb598f9f753daf162068ff39ccea4075cb95e1a30f86995b5b7ee and 0x00000000000000000000000000000000000000000000000000000000000000a8 after being shifted right.

? Enter the value to send: 47

Puzzle solved!

Puzzle #10

00      6020                                                                    PUSH1 20
02      6000                                                                    PUSH1 00
04      6000                                                                    PUSH1 00
06      37                                                                      CALLDATACOPY
07      6000                                                                    PUSH1 00
09      51                                                                      MLOAD
0A      7FF0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0      PUSH32 F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0
2B      16                                                                      AND
2C      6020                                                                    PUSH1 20
2E      6020                                                                    PUSH1 20
30      6000                                                                    PUSH1 00
32      37                                                                      CALLDATACOPY
33      6000                                                                    PUSH1 00
35      51                                                                      MLOAD
36      17                                                                      OR
58      14                                                                      EQ
59      605D                                                                    PUSH1 5D
5B      57                                                                      JUMPI
5C      FD                                                                      REVERT
5D      5B                                                                      JUMPDEST
5E      00                                                                      STOP

? Enter the calldata:

Right at the beginning, the first 32 bytes (0x20) from calldata are copied to the first memory slot, where it's immediately read from again using MLOAD. Afterwards, a bitwise AND is applied to it with 0xF0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0. This means that only the upper 4 bits of each byte from the first 32 bytes we sent as calldata are still there. The lower 4 bits have been "masked" out and the result is left on the top of the stack.

The next 32 bytes from calldata are now copied to memory overwriting the first ones. This word of bytes is again loaded onto stack like before with MLOAD and then ORed with the result of the AND operation. The JUMPI condition to solve the puzzle is that the result of these operations ends up being equal to 0xABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB.

If we call the first word from calldata A and the second word B, the following is the "formula" we have to solve here:


If we send zeros for A the result of the AND operation will be a zero-word too. That way we can discard A completely and just send the end result as B:

0x0000000000000000000000000000000000000000000000000000000000000000 | B = 0xABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB

Putting the words together as a single calldata, this is indeed a solution:

? Enter the calldata: 0x0000000000000000000000000000000000000000000000000000000000000000ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB

Puzzle solved!

But bit-masking is an interesting thing to understand: If we had sent 0xAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA as A, it would've ended up as 0xA0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0 after the AND operation masked out the lower bits. Then we could've sent 0x0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B as B which, ORed with A, would've produced the desired result too:


Puzzle solved!