Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

migrated from stackoverflow.com Feb 26 '13 at 19:48

This question came from our site for professional and enthusiast programmers.

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

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.