Re: Thinking aloud.

Hi.

On 10/26/2012 07:24 PM, Martin Schläffer wrote:
>> Thanks for your response - I'm no cryptography guru, so it's good to
>> hear from people who obviously know more than I do. I guess the way to
>> go then is to build a table of hashes that have been seen and compare
>> the actual content if/when you get a collision? I suppose that would
>> also help in seeing whether/how often pages have the same content.
> Yes. If you see a collision in SHA1 hashes, you can be sure that the
> pages are the same. You do *not* need to compare the actual content
> since you won't see a collision (see below).
>
> If you do a fast checksum first, you only save the time to compute the
> (more expensive) SHA1 checksum, if the fast checksum detects that the
> pages are different.
>
>> Also, may I ask?: How does checksumming a page compare to using SHA1
>> hashes for git blobs? I've read that Linus isn't concerned about
>> collisions there, but don't fully understand why it's not an issue
>> there, but is here.
> I am a cryptographer. Believe me, just ignoring that a SHA1 collision my
> happen is a lot saver than reading data from disk and comparing it (see
> e.g. [1]).
>
> Compared to bugs in software, a SHA1 collision is *really* insanely
> unlikely. The probability to find a collision in SHA1 by coincidence is
> 2^-80. That means, you need to hash about 2^80 SHA1 blocks, or
>
> 1.000.000.000.000 TeraBytes of data
>
> to find a collision. Just make sure that you can easily switch to a
> different hash (like SHA-256), if SHA1 gets broken in practice some day.
Thanks Martin. Making sure you can easily switch is done - the name of 
the algo is a sysfs entry.

Regards,

Nigel