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:
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 2^{100} (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:
1 2 

1


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
blocksized 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 2^{100})
of MD5(secret+x)
for any nonempty 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 2^{28} 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:
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 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:
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 ;–)