Subject: Re: [PATCH] diff.c: Ensure "index $from..$to" line contains unambiguous SHA1s

From: Johan Herland <[email-masked]>
Date: Mon, 31 May 2010 01:23:22 +0200

On Sunday 30 May 2010, Johannes Sixt wrote:
> On Sonntag, 30. Mai 2010, Johan Herland wrote:
> > +cat >expect_initial <<EOF
> > +100644 blob 51d2738463ea4ca66f8691c91e33ce64b7d41bb1	foo
> > +EOF
> > +
> > +cat >expect_update <<EOF
> > +100644 blob 51d2738efb4ad8a1e40bed839ab8e116f0a15e47	foo
> > +EOF
> > +
> > +test_expect_success 'setup' '
> > +	echo 4827 > foo &&
> 
> ...
> 
> > +	echo 11742 > foo &&
> 
> How the fscking hell did you find these two simple values that are an
> almost-SHA1-collision? It's easier to hit the jackpot!?!

Finding matches in the intial 7 hex chars (== 28 bits) of a SHA1 isn't 
_that_ hard. In this case, I used the attached hack/program[1], which found 
the above values in <0.9 seconds, albeit you need ~1 GB free RAM to run 
it[2].

The program simply increments a 32-bit integer, and produces simple (but 
unique) blob objects (merely containing the 32-bit integer in decimal 
format) for each integer, then hashes that blob object and stores the 
original integer in a reverse dictionary (actually, a 2^28-entry array), 
keyed/indexed by the first 28 bits of the hash. Then, repeat until we find 
an integer whose blob hashes to the same location as a previous integer. 
Since we're using a 32-bit integer to generate inputs to a 2^28-entry array, 
we're bound to find collisions long before the integer overflows.

FTR, there are already several almost-collisions in real-world repos. I 
first found some in repos at my $DAYJOB, but there are also multiple cases 
in the git.git repo. The following command will list all 7-char ambiguities 
in a packfile:

  git verify-pack -v $pack.idx | cut -c1-7 | uniq -d

Have fun! :)

...Johan

[1]: Put the attached file in your git.git checkout and compile it with:

  gcc -o find_sha_dup find_sha_dup.c block-sha1/sha1.c

[2]: Double that for each additional bit you want to crack. I.e. cracking 
the first 8 hex chars (== 32 bits) would require ~16 GB free RAM. I'm sure 
there are more efficient ways of doing these things...

-- 
Johan Herland, <[email-masked]>
www.herland.net