binary file compare...

[Grant Edwards]

On 2009-04-16, Adam Olsen <rhamph at gmail.com> wrote:

>>>>> The chance of *accidentally* producing a collision, although
>>>>> technically possible, is so extraordinarily rare that it's
>>>>> completely overshadowed by the risk of a hardware or software
>>>>> failure producing an incorrect result.
>>>>
>>>> Not when you're using them to compare lots of files.
>>
>>>> Trust me. Been there, done that, got the t-shirt.

I must admit, that is a bit hard to believe.

>> Okay, before I tell you about the empirical, real-world
>> evidence I have could you please accept that hashes collide
>> and that no matter how many samples you use the probability of
>> finding two files that do collide is small but not zero.
>
> I'm afraid you will need to back up your claims with real files.
> Although MD5 is a smaller, older hash (128 bits, so you only need
> 2**64 files to find collisions),

You don't need quite that many to have a significant chance of
a collision.  With "only" something on the order of 2**61
files, you still have about a 1% chance of a collision.

Just for fun here are a few data points showing the probability
of at least one collision in a sample of size n using a perfect
128-bit hash.  These were calculated using the taylor-series
approximation shown at

 http://en.wikipedia.org/wiki/Birthday_paradox#Calculating_the_probability

For "a few million files" (we'll say 4e6), the probability of a
collision is so close to 0 that it can't be calculated using
double-precision IEEE floats.

For a few _billion_ files, the taylor series approximation is
still 0 to about 15 significant digits.

For a few _trillion_ files, you finally get a "non-zero"
probability of about 2e-14.

Here are a few more points:

n =     1806791225998070; p(n) = 0.00000000
n =     1987470348597877; p(n) = 0.00000001
n =     2186217383457665; p(n) = 0.00000001
n =     2404839121803431; p(n) = 0.00000001
n =     2645323033983774; p(n) = 0.00000001
n =     2909855337382151; p(n) = 0.00000001
n =     3200840871120366; p(n) = 0.00000002
n =     3520924958232403; p(n) = 0.00000002
n =     3873017454055643; p(n) = 0.00000002
n =     4260319199461207; p(n) = 0.00000003
n =     4686351119407328; p(n) = 0.00000003
n =     5154986231348061; p(n) = 0.00000004
n =     5670484854482868; p(n) = 0.00000005
n =     6237533339931155; p(n) = 0.00000006
n =     6861286673924271; p(n) = 0.00000007
n =     7547415341316699; p(n) = 0.00000008
n =     8302156875448370; p(n) = 0.00000010
n =     9132372562993208; p(n) = 0.00000012
n =    10045609819292530; p(n) = 0.00000015
n =    11050170801221784; p(n) = 0.00000018
n =    12155187881343964; p(n) = 0.00000022
n =    13370706669478362; p(n) = 0.00000026
n =    14707777336426200; p(n) = 0.00000032
n =    16178555070068822; p(n) = 0.00000038
n =    17796410577075706; p(n) = 0.00000047
n =    19576051634783280; p(n) = 0.00000056
n =    21533656798261608; p(n) = 0.00000068
n =    23687022478087772; p(n) = 0.00000082
n =    26055724725896552; p(n) = 0.00000100
n =    28661297198486208; p(n) = 0.00000121
n =    31527426918334832; p(n) = 0.00000146
n =    34680169610168320; p(n) = 0.00000177
n =    38148186571185152; p(n) = 0.00000214
n =    41963005228303672; p(n) = 0.00000259
n =    46159305751134040; p(n) = 0.00000313
n =    50775236326247448; p(n) = 0.00000379
n =    55852759958872200; p(n) = 0.00000458
n =    61438035954759424; p(n) = 0.00000555
n =    67581839550235368; p(n) = 0.00000671
n =    74340023505258912; p(n) = 0.00000812
n =    81774025855784816; p(n) = 0.00000983
n =    89951428441363312; p(n) = 0.00001189
n =    98946571285499648; p(n) = 0.00001439
n =   108841228414049616; p(n) = 0.00001741
n =   119725351255454592; p(n) = 0.00002106
n =   131697886381000064; p(n) = 0.00002548
n =   144867675019100096; p(n) = 0.00003084
n =   159354442521010112; p(n) = 0.00003731
n =   175289886773111136; p(n) = 0.00004515
n =   192818875450422272; p(n) = 0.00005463
n =   212100762995464512; p(n) = 0.00006610
n =   233310839295010976; p(n) = 0.00007998
n =   256641923224512096; p(n) = 0.00009678
n =   282306115546963328; p(n) = 0.00011710
n =   310536727101659712; p(n) = 0.00014169
n =   341590399811825728; p(n) = 0.00017144
n =   375749439793008320; p(n) = 0.00020744
n =   413324383772309184; p(n) = 0.00025099
n =   454656822149540160; p(n) = 0.00030369
n =   500122504364494208; p(n) = 0.00036745
n =   550134754800943680; p(n) = 0.00044460
n =   605148230281038080; p(n) = 0.00053794
n =   665663053309141888; p(n) = 0.00065088
n =   732229358640056192; p(n) = 0.00078751
n =   805452294504061824; p(n) = 0.00095280
n =   885997523954468096; p(n) = 0.00115278
n =   974597276349915008; p(n) = 0.00139469
n =  1072057003984906624; p(n) = 0.00168733
n =  1179262704383397376; p(n) = 0.00204131
n =  1297188974821737216; p(n) = 0.00246945
n =  1426907872303911168; p(n) = 0.00298726
n =  1569598659534302464; p(n) = 0.00361345
n =  1726558525487732736; p(n) = 0.00437061
n =  1899214378036506112; p(n) = 0.00528601
n =  2089135815840156928; p(n) = 0.00639252
n =  2298049397424172800; p(n) = 0.00772975
n =  2527854337166590464; p(n) = 0.00934539
n =  2780639770883249664; p(n) = 0.01129680

Here's the Python function I'm using:

def bp(n, d):
    return 1.0 - exp(-n*(n-1.)/(2.*d))

I haven't spent much time studying the numerical issues of the
way that the exponent is calculated, so I'm not entirely
confident in the results for "small" n values such that
p(n) == 0.0.

-- 
Grant Edwards                   grante             Yow! ... the MYSTERIANS are
                                  at               in here with my CORDUROY
                               visi.com            SOAP DISH!!