7
$\begingroup$

I want to find two strings containing special words like "yes" or "no", mixed with random characters, for which the MD5 hash is equal.

An example of what I'm looking for:

First string : YES/d6g45d78h74jfhcf     MD5 : 4cf349066ce85e0c947eb1d0c94c13b1
Next string  : NO/djf986f98edf8dfv4     MD5 : 7fdefd9bd8a46db9b48a323e8e366150

As you can see the MD5 hashes are different; Is it possible to change the random characters to get equal MD5 hashes?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ here is a "meaningful" example of md5-collision: www2.mat.dtu.dk/people/S.Thomsen/wangmd5/meaningful.html $\endgroup$
    – Thorsten
    Feb 22, 2013 at 7:29
  • 6
    $\begingroup$ Look up the chosen prefix collision attacks on MD5. | The brute-force collsion attack Jon Hulka describes if far to expensive for the OP. $\endgroup$
    – CodesInChaos
    Feb 22, 2013 at 8:37
  • $\begingroup$ I removed a bunch of comments and two answers which didn't really fit this site after the migration. $\endgroup$
    – Paŭlo Ebermann
    Feb 27, 2013 at 21:10

1 Answer 1

Reset to default
12
$\begingroup$

What you want is called a chosen prefix collision. Given p1, p2 you want to find m1, m2 such that hash(p1 || m1) = hash(p2 || m2).

Generic attack

The generic attack to find this, is creating messages starting with p1 and just as many starting with p2. Thanks to the birthday problem you'll find a match after around 2n/2 messages.

For a 128 bit hash like MD5, this means you need about 264 operations. This is feasible in principle, but exceeds your budget. I guess it costs 200'000\$ if you use GPUs and 5'000\$ if you already have developed appropriate ASICs.

Exploiting MD5's weaknesses

MD5 is a broken hash function. Finding normal collisions is very cheap, but that doesn't help you. Luckily(for you) there is also a chosen prefix attack against MD5.

According to a paper from 2009 this costs around 251 compressions. Which corresponds to to about 18 GPU days on a GPU that cost 200\$ in 2009.

So I estimate that the attack costs 10-20\$.

There are two caveats:

  1. The random characters are no printable ASCII characters, but rather random bytes.

    It might be possible to modify the scheme to only emit printable ASCII, but I didn't investigate that.

  2. There will be more random characters than your example has, probably somewhere between 70 and 130.

Improve this answer
$\endgroup$

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.