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:
- user is prompted for a 16 byte input
- input is hashed => HashUser
- 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:
- The initial random string is generated using lowercase/uppercase characters, numbers and characters like
.,"...
- 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)