Re: Why SHA are 40 bytes? (aka looking for flames)

[Andreas Ericsson <ae@op5.se>]

Marco Costalba wrote:
> 
> Someone more versed then me in SHA1 could tell the probablity to find
> a corrupted object calculating his hash and checking against his
> stored 160bits known good signature and *FAIL* to find as corrupt *the
> same object* calculating his hash and checking against a truncated sha
> to say 20bits.
> 

The probability of finding a collision when only 20 bits are used is
1 in 1048575. In other words, repositories would already be exhibiting
collisions with only 20 bits of hash, even with a perfect dispersion.

> I would say this probability is veery veery low in random case (not a
> malicious attack of course, but I think this is not the case with git
> repository as it was with SHA1 designers).
> 

I believe the KDE repo is the biggest one in git today, with its several
hundred thousand revisions (and thus most likely several million objects).

The reason it's not much use to cut down the hash-size is that it already
reflects a very small percentage of the total size of the repo, and since
using the full hash allows git to handle up to
1461501637330902918203684832716283019655932542976 objects without
encountering conflicts (it doesn't really, but that's 2 to the power of 160),
this works as a nice size for a hash to be.

If the hash is reduced to 80 bits, the maximum number of unique hashes shrinks
to 1208925819614629174706176 (less than 1% of 160 bits) while only saving 10
bytes of storage per object. Using a more efficient compression algorithm for
the objects themselves (bzip2, anyone?) will most likely reduce storage size
an order of magnitude more than reducing the size of the hash, although at the
expense of CPU-efficiency.

One must also factor in the code-changes necessary to support abbreviated hashes
and ask oneself "is it worth it?". Since using a smaller portion of the hash
doesn't only have upsides, I'd say "no, definitely not".

-- 
Andreas Ericsson                   andreas.ericsson@op5.se
OP5 AB                             www.op5.se
Tel: +46 8-230225                  Fax: +46 8-230231