Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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).
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.
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:
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.
There will be more random characters than your example has, probably somewhere between 70 and 130.
