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:
% nc 54.197.195.247 4321
/------------------------------------------------------------------------------\
| Welcome to the betting parlor! |
| |
| We implement State of the Art cryptography to give you the fairest and most |
| exciting betting experience! |
| |
| Here's how it works: we both pick a nonce, you tell us odds, and you give us |
| some money. |
| If md5(our number + your number) % odds == 0, you win bet amount*odds. |
| UPDATE: IF YOU DIDN'T REALIZE IT, WE DO INCLUDE A NEWLINE AT THE END OF YOUR |
| NUMBER. SORRY FOR THE INCONVENIENCE. THANK YOU FOR USING PARLOR |
| Otherwise, we get your money! We're even so nice, we gave you $1000 to start.|
| |
| If you don't trust us, we will generate a new nonce, and reveal the old nonce|
| to you, so you can verify all of our results! |
| |
| (Oh, and if you win a billion dollars, we'll give you a flag.) |
\______________________________________________________________________________/
====================
1) set your odds
2) set your bet
3) play a round
4) get balance
5) reveal nonce
6) quit
====================
Let's have a look at an example session:
1
Please pick odds (as a power of 2 between 1 and 100): 8
Odds set to 2^8, good luck!
[...]
3
Okay, send us a nonce for this round!
abc123
Betting $1 at odds of 2^8
Too bad, we generated 78, not 0... better luck next time!
[...]
5
What? You think we're cheaters? Fine, the nonce has been dbe20351bfd26f40105a6a5aca4e1eb4
Who is the cheater now, huh?
Let's see if everything checks out and the server really doesn't cheat:
>>> import hashlib
>>> secret='dbe20351bfd26f40105a6a5aca4e1eb4'.decode('hex')
>>> input='abc123\n'
>>> int(hashlib.md5(secret + input).hexdigest(),16) % 2**8
78L
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:
```bash Terminal A mkfifo input while true; do cat input; done | nc 54.197.195.247 4321
```bash Terminal B
echo -n foo > input
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 2^100)
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 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:
% export secret=AAAA
% export msg="\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00(\x00\x00\x00\x00\x00\x00\x00y"
% echo -n ${secret}x | md5sum
48e1177010d5528ad343a2c302faa37e -
% echo -n ${secret}x$msg | md5sum
bcec1f2921593edf0ddab31ee61ad23f -
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:
% ./hashpump --signature 0000177010d5528ad343a2c302faa37e \
--data "x" \ # already appended to secret in the first hash
--additional "y" \ # what we want to append at the very end
--keylength 4 \ # length of the secret key - 4 in the toy example
--unknown 16 \ # unknown bits
--sig2 00001f2921593edf0ddab31ee61ad23f # target extended signature
mask: ffff0000
progress: 0x 0, 0.0000: |
success with origHash = 48e1177010d5528ad343a2c302faa37e
prefix: 0x48e1
predicted sig: bcec1f2921593edf0ddab31ee61ad23f
x\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00(\x00\x00\x00\x00\x00\x00\x00y
We see that the modified HashPump managed to complete the original hash.
From here it should be easy ;-)