Re^5: Assistance with file compare

You made two errors.

32 hexadecimal digits is 16³² numbers. MD5 hashes are 128 bits in size. 16 hex digits are used to represent the hash since 16³² is equal to 2¹²⁸.

The chances of a collision cannot be ascertained since you haven't shown that every hash is equally likely to be generated.

Comment on Re^5: Assistance with file compare

Replies are listed 'Best First'.
Re^6: Assistance with file compare by keszler (Priest) on Oct 29, 2009 at 01:53 UTC
Yikes - I must have had a math-dyslexic moment. You are of course correct: 3.4e+38 possible results from the MD5 hash. My "theoretically" was my too-concise attempt at your "[not proven to be] equally likely to be generated". I do have a related anecdote: I worked on a site where users uploaded video clips, supposedly original content that they personally recorded. Some of them attempted to cheat by changing the filename and uploading dupes in all but name to increase their stats. One counter-measure I implemented was storing MD5 hashes for each clip. Generating hashes for the existing clips - over 250,000 of them - took many days. Newly uploaded clips, of course, had theirs generated on the fly. Within days of implementing the hash check, a user complained that his clip was tagged as duplicate, but he swore he'd never uploaded it before. Turned out he was correct. It was not a hash collision; he was trying to upload a clip that someone else had previously put into the system. (IIRC, neither of them were the actual owner...) In the months that followed, as tens of thousands more file were uploaded, every occurrence of duplicate hashes turned out to be duplicate files. Granted, less than 500,000 versus 3.4e+38 is far from a definitive test, but I think it's safe to say that the chances of a hash collision are vanishingly remote.	[reply]

Replies are listed 'Best First'.

Re^6: Assistance with file compare
by keszler (Priest) on Oct 29, 2009 at 01:53 UTC

I do have a related anecdote: I worked on a site where users uploaded video clips, supposedly original content that they personally recorded. Some of them attempted to cheat by changing the filename and uploading dupes in all but name to increase their stats.

One counter-measure I implemented was storing MD5 hashes for each clip. Generating hashes for the existing clips - over 250,000 of them - took many days. Newly uploaded clips, of course, had theirs generated on the fly.

Within days of implementing the hash check, a user complained that his clip was tagged as duplicate, but he swore he'd never uploaded it before. Turned out he was correct. It was not a hash collision; he was trying to upload a clip that someone else had previously put into the system. (IIRC, neither of them were the actual owner...)

In the months that followed, as tens of thousands more file were uploaded, every occurrence of duplicate hashes turned out to be duplicate files.

Granted, less than 500,000 versus 3.4e+38 is far from a definitive test, but I think it's safe to say that the chances of a hash collision are vanishingly remote.

[reply]