Solving more-evm-puzzles differently? | Part II

This post is the second part of a small series dedicated to motivating myself while learning how the EVM works. Go to the third part.

Ethereum Virtuelle Machine — cryptoast.fr

If you came here from the previous post, welcome back! And if you ended up in this one by chance, although there is no need to check out the previous write-up before continuing, you're probably going to be missing some context.

Now, let's get back to our next and last puzzle.

Puzzle #9

Link to puzzle's playground.

With a quick glance, we can see the SHA3 instruction appearing for the first time in this series.

Now let's chunk it up! 🍴

The code starts by storing msg.value in memory.

00. CALLVALUE // [CallValue]
02. PUSH1 0x00 // [0, CallValue]
03. MSTORE // [] MEM{CallValue}
Stores a 32 bytes representation of whatever returns CallValue, at the beginning of the memory (position 0).

Then, it places the result of applying the SHA3 instruction to the first 32 bytes in memory, in the stack.

05. PUSH1 0x20 // [20] MEM{CallValue}
07. PUSH1 0x00 // [0, 20] MEM{CallValue}
08. SHA3 // [Keccak256(CallValue)]
Gathers the first 32 bytes from memory, and applies the keccak256 hashing algorithm, pushing its result in the stack.

Shifts right 0xf8 bits (248 bits / 31 bytes), of the 256 bits (32 bytes) representation for the hash function, leaving behind a single byte.

It basically gets the first byte of the hash.

0A. PUSH1 0xF8 // [F8, Keccak256(CallValue)]
0B. SHR // [(Keccak256(CallValue) >> F8)]
Let's abreviate (Keccak256(CallValue) >> F8) as Z.

And last, it compares the result of the previous operation, Z, with 0xA8.

0D. PUSH1 0xA8 // [A8, Z]
0E. EQ // [A8 == Z ? 1: 0]

If it's equal, then we've made it! 🎊 Otherwise revert! ❌

10. PUSH1 0x16 // [16, (A8 == Z ? 1: 0)]
11. JUMPI // []
12. REVERT
13. REVERT
14. REVERT
15. REVERT
16. JUMPDEST
17. STOP

Solution

Great! We now know what to do! 👌

We have to find a hash for some yet unknown value (the one we give within msg.value in this case), by which getting only its first byte would equal 0xa8.

>>> hex(0xa8?????????????...???????????????????? >> 0xf8)
'0xa8'

Since keccak256 is a cryptographic hashing algorithm, the only way to reach our desired value would be by brute force 💪.

In pseudocode it would look like this:

i = 0;
while((keccak256(i) >> 0xF8) != 0xA8) {
    i++;
}

To make this more challenging, I decided to solve it using EVM code as well 😏.

We start by defining a counter, which analogously would represent the i variable in our code, and immediately afterwards set a jump destination where the body of the loop should begin.

01. PUSH1 0x00 // [i] -> starts as i = 0;
02. JUMPDEST // [i]

And now, if you pay attention, you will realize that the following code is pretty similar to the puzzle's logic, which makes sense.

03. DUP1 // [i, i]
05. PUSH1 0x00 // [0, i, i]
06. MSTORE // [i] MEM{i} 
08. PUSH1 0x20 // [20, i] MEM{i}
0A. PUSH1 0x00 // [0, 20, i] MEM{i}
0B. SHA3 // [keccak256(i), i]
0D. PUSH1 0xF8 // [F8, keccak256(i), i]
0E. SHR // [(keccak256(i) >> 0xF8), i]
10. PUSH1 0xA8 // [A8, (keccak256(i) >> 0xF8), i]
11. EQ // [((A8 == (keccak256(i) >> 0xF8)) ? 1: 0), i]

The only difference is that instead of reverting when the comparison fails, we increment the copy of the counter we have left on the stack by one, and repeat until it doesn't fail! 👏

13. PUSH1 0x1B // [0x1B, (A8 == (keccak256(i) >> 0xF8)) ? 1: 0), i]
14. JUMPI // [i]
16. PUSH1 0x01 // [1, i]
17. ADD // [i = (i + 1)] => [i]
19. PUSH1 0x02 // [2, i]
1A. JUMP // [i]
1B. JUMPDEST
1C. STOP

With the link to the solution in the playground, you can go and let it run until it finishes, which will lead to the stack showing your answer: 0x2F (47)

To be honest…

To be completely honest my dear reader, I did try to brute force it in javascript and python at first, but failed miserably 😢. So out of frustration, I decided to solve it in the same language it was going to be evaluated.

Since what made me fail was pretty dumb, but made me look deeper into how the instruction SHA3 works, I created a sub-section dedicated to it below.

Why the f* can't I get this to work?

Knowing the real answer, I tried to understand why I couldn't replicate my own results 🔍.

I started by running a hardhat node to be able to use ethers. The first and obvious thing I tried, was getting the keccak256 of the known answer: 0x2f.

> ethers.utils.keccak256(0x2f)
‘0xfba9715e477e68952d3f1df7a185b3708aadad50ec10cc793973864023868527’
> ethers.utils.keccak256("0x2f")
‘0xfba9715e477e68952d3f1df7a185b3708aadad50ec10cc793973864023868527’> ethers.utils.keccak256(47)
‘0xfba9715e477e68952d3f1df7a185b3708aadad50ec10cc793973864023868527’

This ☝️ is obviously wrong, the correct hash should start with 0xa8 as we already know.

So I decided to test some things out:

> (47 === 0x2f)
true
> (0x2f === 0x0000000000000000000000002f)
true
> (47 === 0x0000002f)
true

Ok, so running the keccak256 of 0x000…0002f would return the same as 0x2f. Then, what the heck is this function doing?

According to the official documentation:
ethers.utils.keccak256( aBytesLike ) ⇒ string< DataHexString< 32 > >
Returns the KECCAK256 digest aBytesLike.

Great, but, is this encoding the data somehow? Checking the source code you will find it returns a string in the following format:
'0x' + sha3.keccak_256(arrayify(data))

Here is when I find the arrayify method and everything starts to make sense.

> ethers.utils.arrayify(0x00....2f)
Uint8Array(1) [ 47 ]

It transforms the input into an array of Uint8s. The instruction SHA3 operates with 32 bytes from memory, which can be considered an array of 32 Uint8s.

Let's try sending how the value would look in memory as a string:

> ethers.utils.arrayify("0x000000000...0000000000000000002f")
Uint8Array(32) [
 0, 0, 0, 0, 0, 0, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 0, 0,
 0, 0, 0, 0, 47
]
> ethers.utils.keccak256("0x000000000...0000000000000000002f")
'0xa813484aef6fb598f9f753daf162068ff39ccea4075cb95e1a30f86995b5b7ee'

And there you go! My mistake was to assume there was some kind of expansion of some sort, in order to get to the 32 needed bytes if I was sending less, but that was not the case 👎.

By the time I realized this, it was already too late, the challenge was already solved, and decided to share it anyway 😄.

GOSSIP: Someone told me that this was a bug in a smart contract that cost a company a fortune, if you know which one I'm talking about, leave me a link in the comments below.

I will be leaving you with a few other challenges of my own in the next post if other things don't pop up in the way.

がんばれ! 🌸

Go to the third part of these series ➡️

Thanks for reading! My name is Matt, and I’m learning how to make Ethereum more secure. I will be sharing some things from time to time.
Follow me on twitter @mattaereal.