Hash collision

[Matt Mackall]

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