# Real life collision when only using truncated hash

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)

-

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.

-
Don't neglect the memory requirements for the birthday paradox though, you would need an insane amount of storage to store all that ($2^{64} \times 128$ is a lot of bits). –  Thomas May 17 '12 at 8:06