None
Parlor
PlaidCTF2014 - crypto250

Challenge Text

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.

This was a great challenge that demonstrated just how thoroughly and completely researchers have broken MD5. The challenge is to make bets at a cryptographic gambling house to win a billion dollar. That's pretty straight-forward, so let's dig into the details a little bit.

\$ 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.)               |
\______________________________________________________________________________/

====================
3) play a round
4) get balance
5) reveal nonce
6) quit
====================

As the banner states, the server combines a user's nonce with the server's "nonce" to generate an MD5 hash. The player wins if the hash is evenly divisible by the odds, otherwise the house wins the round. Since validating the initial hash took a surprisingly long time (sans UPDATE), an example is included below this example:

Please pick odds (as a power of 2 between 1 and 100): 100

3) play a round
Okay, send us a nonce for this round! 0

Betting \$0 at odds of 2^100
Too bad, we generated 304820499652505773544149344909, not 0... better luck next time!

5) reveal nonce
What? You think we're cheaters? Fine, the nonce has been cc8c012ee26c875641df76f82dfdcd53

>>> import hashlib
>>> user_nonce = '0'
>>> server_nonce = 'cc8c012ee26c875641df76f82dfdcd53'.decode('hex')
>>> print hashlib.md5(server_nonce+user_nonce+'\n').hexdigest()
b706e673d8ed9b8d11749a164c5fe28d
>>> print int(hashlib.md5(server_nonce+user_nonce+'\n').hexdigest(),16)%(2**100)
304820499652505773544149344909

A very important point was that the server's "nonce" was a reused 16-byte value (until revealed). This means that given two user nonces, A and B, their hash functions, MD5(nonce + A) and MD5(nonce + B), are vulnerable to a Length Extension Attack. The novel bit here was only revealing the last 100 (of 128) bits of the hash, but the remaining keyspace (2**28) would be small enough to brute force [i]if[/i] we had a test for correctness. The same vulnerability that allows creating a derivative signature can double as a correctness test though. That is to say that the Length Extension Attack can be used to brute force the original hash then pick nonces so as to guarantee victory at the tables.

### Step 1. Disclose Hash State

• - set the odds to 100 (maximize info)
• - pick an arbitrary nonce and play a round (winning is fine, it just means the hash was divisible by (1<<100))
• # info: data="ShySecurity" :: partialRootHash = 501213629312807019713473931121 = 0x000000065382326903b537305259e771

### Step 2. Generate Related Hash

• - create a related nonce and predicted hash value for our partial hash
• \$ ./hashpump -d "ShySecurity\n" -a "Collision" -s 000000065382326903b537305259e771 -k 16
• 58f546a50cac11c508b45e66cf954aaf
• ShySecurity\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\xd8\x00\x00\x00\x00\x00\x00\x00Collision
• - send the related nonce to the server to get a second (100-bit) partial hash
• # partialExtendedHash = 934493473876867748134406499280 = 0x0000000bcb82e2578a92a183469eabd0

### Step 3. Brute Force the Original Hash

• - iterate through the unknown 28-bits of the partialRootHash until the generatedExtendedHash matches the partialExtendedHash
• \$ ./recover "ShySecurity\n" 000000165382326903b537305259e771 "Collision" 0000000bcb82e2578a92a183469eabd0
• cb9423e65382326903b537305259e771

### Step 4. Beat The Odds

• - iterate through new suffixes to generate nonces w/ known hashes
• \$ ./hashpump -d "ShySecurity\n" -a "Collision0" -s cb9423e65382326903b537305259e771 -k 16
• f16dc40a3cf0d570500d9a8f7bb41c38
• - set odds to highest divisible power of two (8 = 2**3)
• - bet everything
• - repeat

learning w/ free play
brute forcing original hash (28 bits)
.........................................................................................................................................................................................................................................................................................................................................................
recovered original known-hash cb9423e65382326903b537305259e771

playing for money now
generated full-hash 4cea923b09ff4687f9a300d1d499a030 for '0'
setting balance 1000 odds 4
balance 16000 # 1000 * (2**4)

generated full-hash 81eed292023d8ec688b543ba304f1e25 for '1'
odds 0 # skipped
generated full-hash 4b0ea80ef738c3b38d93605d8e18b251 for '2'
odds 0 # skipped
generated full-hash 7300e2f9e719e54cb96bd64245377b34 for '3'
setting balance 16000 odds 2
balance 64000 # 16000 * (2**2)

generated full-hash 8f520ed3998d598a184424169ae37211 for '4'
odds 0 # skipped
generated full-hash c38db6f76c1bc718576cdfecb8c70f0e for '5'
setting balance 64000 odds 1
balance 128000 # 64000 * (2**1)

...

generated full-hash 99581bee021a21d95125818468e96b75 for '19'
odds 0 # skipped
generated full-hash a8e811261c4644d9640091f8a8254aaf for '1a'
odds 0 # skipped
generated full-hash ec6ced4936a0e23a274a333825892ff4 for '1b'
setting balance 524288000 odds 2
balance 2097152000

--- netcat mode enabled ---
Holy shit you have a lot of money. Here's a key: i_dunno_i_ran_out_of_clever_keys

flag: i_dunno_i_ran_out_of_clever_keys

Code on Github

- Kelson (kelson@shysecurity.com)