Guess 100 bits of md5 hash

Question

I found the following challenge on a wargames site:

A 16 byte string is randomly generated and hashed with md5 => HashRandom

Next, the following happens in an infinite loop:

1. user is prompted for a 16 byte input
2. input is hashed => HashUser
3. HashUser is compared with HashRandom and the number of matching bits is displayed

The goal is to get at least 100 matching bits.

A couple of observations:

1. The initial random string is generated using lowercase/uppercase characters, numbers and characters like .,"...
2. usually, for any user input string like AAAAAAAAAAAAAAAA I get between 50 and 70 matching bits

To get a better understanding on what happens behind the scenes, I did some reading on md5 and Wang's attack ( http://merlot.usc.edu/csac-f06/papers/Wang05a.pdf ) + other papers related to it. Based on that, here are some notes:

• My input will look like this (UI - user input - bytes I can control):

m0  - 0xUIUIUIUI
m1  - 0xUIUIUIUI
m2  - 0xUIUIUIUI
m3  - 0xUIUIUIUI
m4  - 0x00000080 - initial padding with 1 + 0's 
m5  - 0x00000000
m6  - 0x00000000
m7  - 0x00000000
m8  - 0x00000000
m9  - 0x00000000
m10 - 0x00000000
m11 - 0x00000000
m12 - 0x00000000
m13 - 0x00000000
m14 - 0x00000000
m15 - 0x00000080 - input size - 128 bits - 16 bytes

• Wang talks about a differential attack used to generate messages that collide under md5. I read that hoping it would give me some hints, however it can't really be applied for this challenge. The method described uses two 512 bit input blocks per message. It also imposes restrictions on bytes I can't control.

• The only breakthrough I had with this is the ability to control the hash function after the first round (however, this is trivial and I don't think it can help me)

• Because I can get the matching number of bits for how many strings I want, I can get an idea on how the hash of the random generated string looks like. Since I only need 100 bits, I don't need the hash to mach 100%. Basically, if I can control half of the hash (64 bits), with some luck I can get 36 other random bits to match.

• On the fourth round of the md5 algorithm, the 63rd operation (so right before the final value is calculated) involves m2 (which I control):

Q63 = Q62 + Q59 + I (Q62, Q61, Q60) + m2 + 0x2ad7d2bb) <<< 15

Q63 will also have an effect on Q64.

This might allow me to intervene on the last 64 bits of the hash function; however, any change on m2 will impact the way in which Q63 and Q64 are calculated so I'm not sure if this can help.

Any ideas or suggested reading that could point me in the right direction? (GPU + brute force is the last thing on the list - I'm hoping there's another way to do it)

Answer 1

A 3 minute running time on my laptop (running Java) already gave me a bit string where 99 bits are identical. It might be that you're overthinking this.

This sounds like a classical proof of work that you're supposed to do. As it is unlikely that there are any shortcuts I guess you'll have to break it brute-force. And as is it a gaming site, the faster GPU probably wins.

MD5 still has pre-image resistance of over $2^{123}$, with the specific attack mentioned here. You won't get far with just finding collisions as the pre-image seems to be (unknown) and given.

---

Just computing on a laptop gives, comparing with a hash of all zero's:

100 : 00000000000000000000000625b4aa69 -> 0740a0a42a0074920018000008308212

only just over 26,000,000,000 (16 billion for the US, 16 milliard for the rest of us) hashes required; the hexadecimal representation of the value as 16 byte integer is used as input.

Took some time but nothing major, unoptimized, single threaded Java code, running on a downclocked i7 laptop. On a fast machine with semi-optimized, multi-threaded code expect a 16 times improvement minimum.