Real life collision when only using truncated hash

Question

For MD5 two different inputs are known that produce the same 128 bit hash value. However, these inputs are artificially created for this specific purpose.

For normal, real life inputs I believe no such collision is known?

When you only consider the first n bits of the hash however certainly such collisions are known for small n.

My question: what is the largest n bits truncation for which an accidental collision is known?

(of course answers need not be limited to MD5 but can also be about others hashes)

Answer 1

Accidental collisions are interesting for certain applications, and one would expect accidental collisions to occur less frequently in a system than malicious collisions.

So, if you are not worried about malicious collisions, only accidental, it is easy to compute how many digests you would need to compute before seeing an accidental collision. If the output of the hash (either truncated or not) is $n$ bits long, you would expect to see an accidental collision once there are about $2^{n/2}$ digests in your database.

As for what is publicly known for accidental collisions, I haven't come across any data. Probably because accidental collisions are not very interesting. We know exactly how many digests to compute before expecting to see one, so why waste the electricity to experimentally validate what we already know mathematically?

Looking at some numbers for SHA-1 on a GPU, if you can perform $1,746,000,000\approx 2^{30}$ sha-1 operations per second, and we would expect a collision after $2^{80}$ operations, it would take $2^{50}$ seconds (or about $35702051$ years) to see an accidental collision (ignoring future increases in computation power).

On the other hand, the same website lists MD5 at about $5,570,000,000\approx 2^{32}$ MD5 computations per second. A collision would be expected after about $2^{64}$ computations. That equates to $2^{32}$ seconds (or about 136 years).

You can follow the math then to see how long for various truncated versions of both MD5 and SHA1.

Answer 2

Yes, there have been real life inputs with collisions working on the full length of MD5. There is a pair of X.509 certificates that share an MD5 hash. There is also a pair of PostScript documents that are an MD5 collision. There are also two binary strings a mere 6 bits different that are a collision. The whole length of MD5 has been broken.

Attacks that use what you call "artificial" input are valid real life attacks. A key here is is that the data we hash often has structure that allows for bogus information to be modified or added without changing the final "human consumed" data in the file. For example, you can take a PNG image file and append data to it without affecting the image data. This allows an attacker to manipulate that extra information intelligently and find an ad hoc value that produces a collision. He don't need to accidentally trip over one, he can specifically craft it.

This attack natural lends itself to application on hashes that use the Merkel-Damgard construction, which the currently popular ones (MD5 and the entire SHA family) do. The MD construction basically works by maintaining an internal state and using the hash's compression function to combine the input with the state block by block. To attack it, first hash the original data then take the internal state after the last input block and use it as the initial state for creating a block that is a collision. If you can generate an ad-hoc collision, you may be able to extend the way you generate that collision to work with the initial state that you got from hashing the original document. (This also work on creating header data with collisions, then extending it by appending identical documents. The collision would be maintained, but the documents would have different headers.)

The bottom line is that we don't need collisions to be what you call "accidental". Specifically crafted, ad-hoc collisions are valid security breaches and have the potential to be extended to collisions on real life data. This is not always the case, but it is not uncommon.