# PlaidCTF 2014 'Parlor' (Crypto 250) Writeup

Parlor was a interesting and fun challenge for me at this year’s pCTF. Here’s my writeup, I hope you’ll find it interesting.

## Challenge setup

The Plague is running a betting service to build up funds for his massive empire. Can you figure out a way to beat the house? The service is running at 54.197.195.247:4321.

At the time of writing, the server is still online, so if you’re lucky, you can still play (before or instead of reading this writeup).

The gambling game offered by the server seem quite similar to SatoshiDice:

Let’s have a look at an example session:

Let’s see if everything checks out and the server really doesn’t cheat:

This matches the number the game told us. Now that we verified the mechanism used by the server, let’s see how we can break it.

We can set `odds` to any power of 2, up to 2100 (it really is capped at 100, I tested…)

Although they call their number a Nonce, it is reused until we ask the server to reveal it. However we are not allowed to repeat our number (server’s response: “What part of NONCE don’t you understand, asshole?” followed by a disconnect). If this was allowed, it would be trivial to win by reusing a winning number often.

Luckily the server is nice enough to reveal the result of `md5(our number + your number) % odds` in case it is nonzero (78 in the example). We can also express this as bitwise and (`&`), because `MD5(m) % 2^k = MD5(m) & (2^k - 1)`. In the example, we could therefore also use `& 0xff` instead of `% 2**8`. In other words: the server computes the lower `k` bits of the hash. So essentially, the goal of the game is to guess a number so that the resulting hash has many trailing zeros.

## Avoiding newlines

Although a later update in the server banner mentioned trailing newlines (see the `'\n'` into the previous example) it is well possible to avoid the newline:

Even without a newline, the server responded well. This method also makes it simple to send binary data without writing a custom client. In retrospect, using an interactive python shell might have been nicer though.

## MD5 Collisions?

My first thought was to solve this using MD5 hash collisions, which can be generated very quickly nowadays, e.g. using HashClash.

Given two blocks A, B with the same hash value, my idea was to play `A + x` for varying x for \$1 until I find a winning x, then play `B + x` with the remaining money.

It turns out that MD5 hash collisions don’t work that way – even with a block-sized common prefix P, in general `MD5(P+A) != MD5(P+B)`.

## Length Extension Attacks

Next idea: if we knew `MD5(secret)`, we can compute `MD5(secret+x)` using a Length Extension Attack, e.g. using HashPump. Then we could locally guess different values of `x` until we get a hash `MD5(secret+x)` with many trailing zeros and empty the casino with it.

Problem: the server will not give us a full hash, but only the lowest 100 bits (we cannot set `odds` larger than 2100) of `MD5(secret+x)` for any non-empty value of x we supply. MD5 hashes are 128 bits long, so there are 28 unknown bits.

Solution: We fetch the lower bits of `MD5(secret+'x')` and `MD5(secret+'x'+L)`, where L is our length extension attack string. If we guess the missing 28 bits of `MD5(secret+'x')` correctly and use HashPump on the result, the extended MD5 hash will match the 100 bits of `MD5(secret+'x'+L)` that we acquired. So we can just try this for all possible 228 possible prefixes until we find one where it works. Then we can be reasonably sure that we found the original hash.

I patched HashPump to do this bruteforce attack for me, giving it both partial hashes and the number of missing bits as input. After fixing a few stupid bugs it worked correcty on a toy example, and, with more patience, also with the real thing.

Knowing the full hash of `MD5(secret+'x')`, I added another bruteforcing loop to HashPump, computing strings L to append so that `MD5(secret+'x'+L)` has many trailing zeros.

Playing two rounds with these strings was enough to win the required amount to receive the flag.

## Code & Example

In case you want to have a closer look or play with it yourself, I published my HashPump fork to a github repo.
Diff only: Commit b822764fa71209858c91378736d43d082c674e96

Let’s use it on a toy example:

`msg` looks like random magic, but it actually is the length extension string HashPump gives us after one run, minus the leading ‘x’ (HashPump `--data` parameter).

The hashes are what is really calculated on the server for the inputs ‘x’ and ‘x\$msg’. To simulate the game environment, we pretend not to know the first 2 bytes of these and fill in zeros for them:

We see that the modified HashPump managed to complete the original hash.

From here it should be easy ;–)