Re: Hash collision count

On 4/23/05, Jeff Garzik <jgarzik@pobox.com> wrote:

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