Strength of MD5 in finding duplicate files

Question

Why are there a lot of duplicate file finder applications which are using MD5 Algorithm? What is the strength of MD5 in terms of searching duplicate files in hard disk or flash driver or any other storage device?

Answer 1

MD5 is ok here as usual cryptographic attacks do not apply in this scenario. The probability of accidental MD5 collision is much less than usual probability for soft error. For details read more.

---

MD5 is currently considered too weak to work as a cryptographic hash. However, for all traditional (i.e. non-cryptographic) hash uses MD5 is often perfectly fine.

MD5 has one important benefit above SHA1, SHA2, and upcoming SHA3: many platforms allow faster implementation of MD5 than other hashes. The performance in this use case varies highly according to used hash function.

The practical attacks against MD5 are mostly against collision resistance. If these are not an issue, MD5 can be fairly ok. (See earlier question Is a second pre image attack on MD5 feasible?.) For instance, where MD5 is considered fine by many is HMAC-MD5.

To get back to this question. It can be assumed that find duplicate files is not something where collision resistance is such of an issue (you likely do not have $2^{64}$ files), so chances of collision are much smaller than in many cryptographic uses where it is assumed adversary tries to find collisions.

Thus, for usual hash uses, the space of MD5 (128 bits) is large enough. The probability of collision in usual situations is small enough, it is much larger probability to for example, detect false duplicates due to random hardware failure (like soft error).

For more accurate mathematics, see earlier question What is the probability of md5 collision if I pass in 2^32 sets of string?. This is applicable in scenario where user has less than four billion files, and you may use the formula for other values. One million files gives $2^{-89}$, which I would consider very small.

---

Even more efficient for duplicate file finding than MD5 is to consider all file sizes. Files which are not the same size are not duplicates. Only files that have size which is not unique need hashing. If file duplicate program using hashing wants to be safe from MD5 hash collision, the program may want to perform byte-per-byte comparison to ensure files are unique.

Answer 2

MD5 is less CPU intensive than other cryptographic hash functions. For example, the SHA1 algorithm is more complex than MD5 meaning it is less efficient to calculate. This may be the reason MD5 is used.

Answer 3

MD5 is practically useless for verifying the identity of a file for purposes of a WAN like the internet, but it works fine for identifying duplicates or verifying files in the context of deploying MD5 within the boundaries of a LAN. The Math works as follows:

We know with MD5 we are set with the definite number of Possible Hashes being 2^64. However, the Birthday Paradox (which says that if we have 366 people that two of them must have the same birthday 100% of the time), means that the Hash begins to break down the very second we have greater than 2^64(Or 18,466,744,073,709,551,616) total unique files circulating on the internet.

We know from statistics that there are an average of 3.2 Billion people on the internet at any given time. Doing the Math, the Hash begins to break when each of those 3.2 Billion people have just 8 files each. So that means if everyone on the internet has 16 files, we have a 2:2^64 chances of a clash- where the more files the worse the odds are in favor of a clash- For every 8 additional files the odds of a clash go up by a factor of 1 if we are to employ the most conservative numeric theory.