Hash collision

[Brian Mearns]

On Wed, Apr 29, 2009 at 12:43 PM, Matt Mackall <mpm at selenic.com> wrote:
> On Wed, 2009-04-29 at 08:59 -0400, Brian Mearns wrote:
>> I'm curious about the possibility for collisions in the hashes that
>> mercurial uses to identify all of its revisions. I realize there are
>> yet to be any reported collisions in sha-1, but isn't it conceivable?
>
> It is conceivable.
>
> There are two kinds of attacks:
>
> 1) birthday attack - find any two messages which have the same hash
>
> 2) preimage attack - find a message that has the same hash as a given
> message
>
> The difficulty of (1) is currently estimated a 2**69 hash operations and
> no one has yet reported succeeding, though it could happen any day. The
> difficulty of (2) is probably the difficulty of (1) squared, which makes
> it computationally infeasible without some major cryptographic
> breakthrough.
>
> The basic exploit for attacking (1) is to generate two similar documents
> with some random bits in them that no one's going to look at, but where
> some significant piece is changed from harmless to dangerous. Then you
> get someone to sign the first document then swap in the second. See
> http://www.win.tue.nl/hashclash/rogue-ca/ for an impressive example of
> such an attack against MD5 (and SSL!).
>
> Someone may eventually be able to pull this off against SHA1. You'll
> know when that happens, because everyone using SSL with SHA1 (ie most of
> the internet) will freak out.
>
> But attack (1) is a lot less interesting for Mercurial: if you can get
> someone to accept the first document, they probably already trust you
> enough so that you don't need to be a world-class cryptographer to sneak
> in an exploit. Attack (2) is the one that would allow -untrusted- people
> to change history in the repository and that one is not even vaguely
> realistic. Much easier than both attacks is to break into a trusted
> user's machine by conventional means.
>
>> Does mercurial do anything to detect or defend against collisions, or
>> is it really so unlikely that it's not worth worrying about?
>
> The odds of the changeset hash colliding by accident in your first
> billion commits is basically zero. But we will notice if it happens.
> And you'll get to be famous as the guy who broke SHA1 by accident.
>
> --
> http://selenic.com : development and support for Mercurial and Linux

Thanks for the thorough feedback. I'll set up a script to commit every
second, and once the age of the Universe has reached about 10^31 times
what it is now, I should get my moment in the sun!

Okay, I'm pretty convinced now.

-Brian

-- 
Feel free to contact me using PGP Encryption:
Key Id: 0x3AA70848
Available from: http://keys.gnupg.net