Xxhash: Replacing MD5 as file digest

[leochou0729]

Hello,
I'd like to use xxHash3 128bit instead of MD5 in my app for file digest, so I create a demo app, which iterates over all files in my system volume on macOS. The result is a bit shocking to me.
Elapsed time in seconds: 1922
File count: 2009542
Hash collision: 1239830

Is this normal? There are too many collisions given that the result length is as long as MD5.
Thanks!

[easyaspi314]

Well xxHash is not a cryptographic. While it tries to avoid collisions, it still has possible collisions and provides no guarantee.

MD5 has collision resistance guarantees, albeit very weak ones by today's standards.

However, if you would like to share some files that you found a collision in (as well as the seed), it might be helpful to figure out why the collision is happening.

[Cyan4973]

This hash collision rate is indeed not normal.
There's something fishy.
Would you mind sharing a few samples that produce these collisions ?
Also, understanding how the hash values are generated, stored and read would likely be helpful.

[leochou0729]

Here is my code. I just count the collision numbers without saving each hash value to disk.
https://gist.github.com/leochou0729/4983fedebffef733fdfc97f4b1b6696a

[gzm55]

Here is my code. I just count the collision numbers without saving each hash value to disk.
https://gist.github.com/leochou0729/4983fedebffef733fdfc97f4b1b6696a

in this code, File count means the count of distinct paths, not the count of distinct file contents.

[leochou0729]

@gzm55 Sorry for my mistake. You're right. After changing my code to calculate hash on each file's absolute path, there is zero collision. But for file content, there are still many collisions. I need to figure out a way to filter out duplicate files.

[Cyan4973]

But for file content, there are still many collisions. I need to figure out a way to filter out duplicate files.

If there are duplicate files, then it's normal for some hash values to be repeated.
It's actually not a "collision", rather it's the checksum doing its role of finding duplicates.

Ensuring an absence of duplicate in the sample set is not required if the goal is merely to compare the dispersion qualities of xxh128 with md5.
I would rather recommend testing the same code with both md5 and xxh128. Assuming that no input is manufactured to willfully generate a collision, the chances for a _random_ collision to happen are virtually null, for both algorithms.
So they should detect exactly the same amount of duplicate.

[leochou0729]

@Cyan4973 Thanks a lot for your great suggestion. I will run both xxh128 and MD5 on the same sample set and compare the results. :)

[baryluk]

@leochou0729 The hashing shouldn't be trusted for finding duplicates. You should compare hashes first, but after finding potential-duplicates recheck using full file content (after some other checks like file size), or using way stronger and longer hash (SHA512 or BLAKE3 for example). Depending on number of duplicates in each set, doing full content comparison might be significantly faster than hashing again.

You probably know about it, but wanted to make sure.

[leochou0729]

Hi@baryluk, I have run a test on all files on my computer using xxhash128 and md5. The result is totally the same. I just use a STL map container to keep a cache in my DLP product and the hash value of file content would be the key. The file cache is used to prevent re-scanning of the same file in a short period and would be cleared after a few seconds. Is it really a problem to replace the hash function? Thanks! @Cyan4973