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.
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 188.8.131.52: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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
Let’s have a look at an example session:
1 2 3 4 5 6 7 8 9 10 11 12 13
Let’s see if everything checks out and the server really doesn’t cheat:
1 2 3 4 5
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 (
MD5(m) % 2^k = MD5(m) & (2^k - 1).
In the example, we could therefore also use
& 0xff instead of
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.
Although a later update in the server banner mentioned trailing newlines
'\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.
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)
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
where L is our length extension attack string. If we guess the missing 28 bits
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
has many trailing zeros.
Playing two rounds with these strings was enough to win the required amount to receive the flag.
Code & Example
Let’s use it on a toy example:
1 2 3 4 5 6
msg looks like random magic, but it actually is the length extension string
HashPump gives us after one run, minus the leading ‘x’ (HashPump
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:
1 2 3 4 5 6 7 8 9 10 11 12
We see that the modified HashPump managed to complete the original hash.
From here it should be easy ;–)