Re: Thinking aloud.

> 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.

Martin


[1]
http://www.itnews.com.au/News/320709,stable-linux-kernels-hit-by-serious-file-system-bug.aspx