# Khal Hash (crypto)

**Khal Hash** was a cryptography challenge from FCSC 2022, of *hard* difficulty.

The goal of the challenge was basically to perform a **preimage attack** on Python's

function, with some additional constraints. More particularly, we had to find a **hash****tuple** of ASCII bytes ($< 128$) that hashes to `2077196538114990005`

.

## Python's hash function

Python's hash function is a builtin that can compute a 64-bit hash value for many types of object (but not every single one of them — dicts, for instance, are unhashable). Their main purpose is to enable quick look-up of values in data structures such as dicts or sets. They are by no means meant to be cryptographically secure.

For *tuples* specifically, the source code of the hash computation algorithm can be found here:

Knowing that Python integers hash to themselves, we can rewrite the algorithm for integer tuples this way in Python:

We need to find a tuple of arbitrary length, with elements that are integers between 0 and 127 inclusive, that hashes to `2077196538114990005`

.

I tried naively throwing z3 at this problem, by fixing the length of the tuple and increasing it when z3 determined the constraints were not satisfiable. This obviously did not work, otherwise the challenge would have been too easy.

Indeed, we can sense that in order to trigger a collision with the target value, we would need at least around 9 bytes in our tuple (this makes 63 bits of entropy), perhaps 10 bytes.

Brute-forcing around $2^{64}$ input values is way out of the question on a regular modern computer. Is there some kind of flaw that could allow us to construct an input that hashes to the target value?

With only the first and third lines in the for loop, it would have been easy as the function would become linear. Unfortunately, the bit rotation step breaks this linearity and makes it really hard to follow how tweaking the input impacts the output.

## Meet me in the middle

When looking up "python hash collision" on Google, I stumbled upon this blog post: Efficiently generating Python hash collisions.

It highlights how in Python 3.2 and below, the `hash`

function was vulnerable to a MITM (Meet-in-the-Middle) attack. I realized even though the algorithm has changed since, we can still perform such an attack because the operations that are carried out are all **reversible**.

Naturally, you could go through the algorithm the opposite direction, knowing the target hash and the bytes that compose the input in the reverse order: you would then recover all the intermediate `acc`

values and eventually get back the `_PyHASH_XXPRIME_5`

constant.

The attack becomes clear now: the search space can drop from $2^{64}$ to $2^{32}$ by brute-forcing half the input length forward, half the input length backward, and leverage the birthday paradox theorem.

With only around $2^{32}$ inputs, we would have a decent chance of finding an intermediate `acc`

value that has also been computed with around $2^{32}$ inputs in the *backwards* version of the algorithm.

Once we found a common intermediate `acc`

value, we only have to concatenate the two found paths to get our solution to the preimage problem.

There's just one drawback with this method: it brings significant **space complexity**. Indeed, we need to store all the intermediate `acc`

values to be able to look up if the one we computed backwards has already been computed forward.

Ideally, we want this LUT (look-up table) to tell us if we have already seen an intermediate value in $O(1)$, therefore it should be indexed with the intermediate `acc`

value (e.g. `LUT[acc] = path_half`

). This requires $2^{64} \times \text{sizeof}(\text{path\_half})$ bytes, which is out of the question.

We need to find some kind of compromise between space complexity and time complexity to find a real candidate: because reducing space complexity will inevitably bring collisions here, we will find many candidates for a common intermediate `acc`

value, and we will have to check each time whether it is an actual one or not.

## Implementing the attack

For my solution, I tried to make the most of the RAM available on my computer. I chose to index my look-up table with 31 bit integers, each element in the table being a 4-byte path. This takes up **8 GB** of RAM.

Therefore, intermediate hash values would need to be reduced to 31 bits, which I did with a simple mask:

The `intermediate_forward`

function takes a prefix path of bytes and its size (here, 4). It returns the intermediate `acc`

value for this path.

I also implemented an `intermediate_backward`

function:

My exploit first fills the LUT with all the $2^{28}$ possible intermediate values for 4-byte prefix paths. Then, it brute-forces 6-byte suffix paths until finding a matching entry in the LUT, and ensures that this entry is a valid one by concatenating the two paths and computing the final hash.

After 30 minutes to 1 hour, I finally get a valid candidate:

Let's try it out in Python:

It works! Now we send it to the remote, and get back the flag.

PS: I am deeply sorry to that person I kicked out of the top 3 crypto senior ranking by solving this challenge, who had already submitted their write-ups. 😭

### Full solution code

Last updated