Re: Thinking aloud.

Hi.

On 10/26/2012 08:40 AM, Theodore Ts'o wrote:
> On Fri, Oct 26, 2012 at 07:51:50AM +1100, Nigel Cunningham wrote:
>> Taking it one step further, would you agree with the assertions of
>> others that even if the SHA1s match, I still need to memcmp the
>> pages to check they're actually the same (so SHA1 is effectively
>> reducing an O(n^2) comparison of pages with each other to O(n)).
> SHA1 creates a 160 bit hash.  So let's suppose you have a 64GB worth
> of memory, which means you have 2**44 4k pages.  What's the
> probability that there will be a collision?  Well:
>
>      m = 2**44
>      n = 2**160
>      P = 1 - e**(-m**2 / 2n)
>        = 1 - e**(-2**88 / 2**160)
>        = 1 - e**(-2**(-72))
>        = 2.1175 x 10**-22 (or 2.1775E-22)
>
> This is a very tiny number.  To give you some context, let's assume
> the annual failure rate percentage is 0.34%.  (Other manufacturers
> have claimed an AFR of 0.88%, and the "Disk Failures in the Real
> World" paper by Schroeder and Gibson claim rates of 2-4%, with up to
> 13% observed in some cases.)  But will assume a super-reliable disk
> and assume the annual failure rate of 0.34%.  OK, let's turn that into
> a failure rate on a per-second basis (assuming that we can suspend and
> resume in a second).   What is the per-second failure rate?  1.07813E-10
>
> So it is **far** more likely that the hard drive will fail than the
> chance that you will observe a SHA1 hash collision.  Heck, I'm pretty
> sure chances of the memory going wonky on you when you do the memcmp
> is probably more likely....
You wouldn't be concerned about someone trying to craft two pages having 
the same hash and using it as a security vulnerability? (So I should 
just be happy with comparing hashes?) Would you be concerned if an MD5 
hash was used instead?

Hmm. 64GB is actually 2**24 4k pages, isn't it? (That would make your 
argument above even stronger!) So for MD5 it's 1 - e**(-2**48 / 2 ** 
128) = 1 - e**(-2**(80)) == less likely than above. So if I've got 
things right, if you're not concerned about the numbers above, you 
wouldn't be concerned about this number and using MD5 would be 
preferable (faster without giving a significant chance of a random 
collision)?

Still, if that collision does happen, the results could be not very 
nice.  Perhaps it would be worth the time/effort of checking for 
collisions and doing the memcmp to be 100% sure?

Regards,

Nigel