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.) | \______________________________________________________________________________/ ==================== 1) set your odds 2) set your bet 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:
1) set your odds Please pick odds (as a power of 2 between 1 and 100): 100 2) set your bet Please pick your bet amount (between 0 and 1000): 0 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.
learning w/ free play received partial known-hash 000000065382326903b537305259e771 received partial related-hash 0000000bcb82e2578a92a183469eabd0 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