Re: Hash collision count

[Imre Simon <imres.g@gmail.com>]

On 4/23/05, Jeff Garzik <jgarzik@pobox.com> wrote:
> Petr Baudis wrote:
> > -DCOLLISION_CHECK
> 
> Cool.  I am happy, then :)
> 
> Make sure that's enabled by default...
> 
> Thanks,
> 
>         Jeff

I would like to second the suggestion that this should be enabled by default.

First, I do think it is highly unlikely that a collision will ever be
found. Actually because of this if one is found it would be an
important byproduct of git and it would probably influence future
system designs. Hence, I believe that it is worth loosing some
efficiency in order to illuminate better this question of the
collision.

I would like to add a reciepe by which one would surely produce a
collision with two files of the same length and quite similar to each
other. I believe that there is a popular belief that this is pretty
much impossible. Of course, we do not have time to execute this
algorithm, but I believe that it convinces everyone that similar files
*do* exist (actually in abundance) with the same hash.

1. Take your favorite text file, at least 160 characters long. 
2. Choose 160 positions in this file.
3. For each position choose your favorite mispelling of that character.
4. Produce all 2^160 text files, all of the same length, choosing for
each position either the original or the alternate character
5. Add an arbitrary file of the same length, different from the above

Two of these files have the same sha1 hash. Or, for that matter, for
any 160 bit  hash the same is true.

Cheers, Imre Simon