mainstoreBackup - Support: sr #107563, What if two *different* files had...

 
 

sr #107563: What if two *different* files had the *same* MD5 hash?

Submitter:  None
Submitted:  Thu 30 Dec 2010 01:49:44 PM UTC
   
 
Category:  None Priority:  5 - Normal
Severity:  3 - Normal Status:  Done
Privacy:  Public Assigned to:  None
Originator Email:  -email is unavailable- Open/Closed:  Open
Operating System:  GNU/Linux
* Mandatory Fields

Add a New Comment Rich Markup
   

Tue 11 Jan 2011 10:58:30 PM UTC, comment #2: 

I do not think that these numbers are 100% correct. You calculated the probability of getting a collision for one particular file chosen in advance. But, the probability of two files having the same checksum is much higher. This is know as the birthday paradox: the probability of two people out of 23 having the same birthday is 50% and not 1:365.

However, the probability of two files having the same 128 bit checksum reaches 10^-6 when there are 2.6x10^16 files -- of the same size, in case of storeBackup. :)

Anonymous
Mon 10 Jan 2011 04:53:34 PM UTC, comment #1: 

Hi,
additionally to your description storebackup also checks the size of two files with the same md5 sums. If two files with different size have the same md5 sum, it will print a warning (possible hash collistion) and will not link them together. It's a warning, because this might happen because of changes in the file during the backup.

So for one file size, we can make the following calculation:
An md5 sum has 128 bits, this are 3.4x10^38 possiblities. So the probability of a collision is 1:3.4x10^38 for files with idential file size (see above).

Just for fun:
To win the highest rate in German lotto, there's a probability of 1:1,4x10^6. So, you should wait for winning in lotto instead of duplicate files with storebackup - even though your name is Felix ;-) .

Best Regards, Heinz-Josef

btw: There's one exception: I guarantee, that there are no hash collisions with empty files ;-)




Heinz-Josef Claes <hjclaes>
Group administrator
Thu 30 Dec 2010 01:49:44 PM UTC, original submission:  

Just some thoughts...

Of course, it is not very probable that scanning two different files would result in the exact same MD5 hash sum, but it should be possible, because the hash is (usually) shorter than the file itself and therefore can't possibly be unique.

As far as I understood your explanations of storeBackup's "inner workings", it calculates the md5 of every file at the first backup run. It assumes files with the same md5 to have identical contents (despite different file attributes, name, mtime, ...) and physically only stores them once (through hard linking). This might even result in a targetDir smaller than the sourceDir.

But what if, say, two in a few million files of my sourceDir had the same md5 although their contents are different?
storeBackup would only copy one of the two, and mistakenly only set a hard link for the other.

Ok, this might really be quite paranoid :)

But I was just wondering if, with a few million files and hashes, the probability of that happening might become noticeable?
I.e., in rare occasions, storeBackup might muddle up files with different contents because it relies on the md5 sums.

I have no clue how to calculate this probability, and if it is really relevant though.

Thanks for this great backup tool!

Gruss
Felix

Anonymous

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by hjclaes (Posted a comment)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only logged-in users can vote.

     

    Follows 1 latest change.

    Date Changed by Updated Field Previous Value => Replaced by
    2012-05-31 hjclaes StatusNone Done

    Back to the top

    Powered by Savane 3.13-4448.
    Corresponding source code