2
$\begingroup$

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)

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ I was hoping for a more elegant solution to this. Oh well, at least now I know some of the internals of md5 $\endgroup$
    – Timo89
    Dec 11, 2016 at 17:42
  • 1
    $\begingroup$ I understand. But unless you can somehow control the initial input to the hash you can only attack using pre-image attacks, not collision attacks. $\endgroup$
    – Maarten Bodewes
    Dec 11, 2016 at 18:23
  • $\begingroup$ You compared with a hash of all zeros. This simplifies the problem. Using a "normal" hash value as a target, I'm at 1.7 billion hashes and only got one 98 bit match. $\endgroup$
    – Timo89
    Dec 14, 2016 at 19:40
  • 1
    $\begingroup$ The hash output is indistinguishable from random; it doesn't matter if you compare with all zeros or any other number. Nor does it say much how many 98 or 99's you get. You could get none and then 100 with still a relatively high probability. $\endgroup$
    – Maarten Bodewes
    Dec 14, 2016 at 20:21
  • $\begingroup$ You're right. My bad. I have some catching up to do on probability theory. $\endgroup$
    – Timo89
    Dec 14, 2016 at 21:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.