SHA-1 and changeset signatures

[Eric Hopper]

On Fri, Aug 26, 2005 at 02:37:32PM -0700, Chad Netzer wrote:
> On Fri, 2005-08-26 at 09:59 -0700, Eric Hopper wrote:
> 
> > Generating SHA-1 collisions isn't impractical.  I believe there's a
> > website that will generate them for you.
> 
> I'd like to see that link, as I'm more than a bit skeptical.  Sure,
> maybe there is a listing of known hashes that collide, but to
> "generate" them as you wait?  Do I have to wait for weeks, months, or
> years?

I found it, and it's MD5, not SHA-1.  And they don't generate
collisions, they record known hashes.  *sigh* Good for password
cracking, but not helpful for an attack against Mercurial.  Sorry I was
being alarmist.

> In any case, the 'break' of SHA-1, seems to state that I can generate
> two pieces of input that generate the same hash value, faster than a
> brute-force search.  It does NOT state that, if I'm given a hash
> value, I can find some input that generates that same hash faster than
> a brute force search.  That is a much harder proposition, and probably
> more relevant to the hash's use in Mercurial.

In order to attack Mercurial, you do not need to do this.  You need to
be a malicious developer who is going to pretend to contribute to a
project.  Then you create two different changes.  One looks innocuous
and it gets accepted.  The other is clearly not innocuous, but it
happens to have the same hash.  You give the malicious one to people
after the non-malicious one has been vetted.  Changesets are identified
by hash, so it's quite likely that there will be some system (perhaps
even an automated one) that the malicious change can be slipped into and
be falsely identified as a non-malicious change.

Here is a link to a clearer description of this process:

http://www.cits.rub.de/MD5Collisions/

This attack is definitely feasible.  And it does not require mega-hours
of computer time each time it is carried out.  But, it is against MD5.

But, SHA-1 is just as vulnerable to this exact kind of attack.  The
amount of computer time required is much higher, but still within the
realm of feasibility for a determined attacker, say a powerful
government who wanted to insert a backdoor into gpg.  Not only that, but
the attack on SHA-1 has been getting better as researchers look into it
more.

Because of the general nature of SHA-1 and MD5 (and SHA-{256,384,512}),
being able to generate two random texts that hash the same mean that you
can generate two texts that are mostly not random that hash to the same
value.  This is enough.

Have fun (if at all possible),
-- 
"It does me no injury for my neighbor to say there are twenty gods or no God.
It neither picks my pocket nor breaks my leg."  --- Thomas Jefferson
"Go to Heaven for the climate, Hell for the company."  -- Mark Twain
-- Eric Hopper (hopper at omnifarious.org  http://www.omnifarious.org/~hopper) --
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
Url : http://www.selenic.com/pipermail/mercurial/attachments/20050826/56a6d55b/attachment.pgp