SHA-1 and changeset signatures

Matt Mackall mpm at selenic.com
Fri Aug 26 12:40:50 CDT 2005


On Fri, Aug 26, 2005 at 09:59:27AM -0700, Eric Hopper wrote:
> On Fri, Aug 26, 2005 at 09:39:54AM -0700, Eric Hopper wrote:
> > One thing I would really like to see with Mercurial is the ability to
> > verify changesets come from the person they say they come from.  One way
> > to do this is to sign the hash for the changeset.  And to some extent,
> > this can be handled outside Mercurial though having a piece of changeset
> > meta-data explicitly earmarked for storing such signatures would be
> > nice.
> 
> Oops, I read the FAQ and hgeditor script, and I feel a bit stupid now.
> :-/
> 
> And I see that some thinking has gone into SHA-1, but I don't see
> anything in the changeset ID that tells you which hash was used to
> generate it.
> 
> Generating SHA-1 collisions isn't impractical.  I believe there's a
> website that will generate them for you.  And I can see a couple of ways
> that could really hurt a repository.

No one has actually done it yet, they've just shown it's feasible.

The best known work factor (announced about a week ago) is 2^63
hashes. I did some work on optimizing SHA-1 in the kernel some months
back and the current version takes about 1us per hash block on a high
end processor.

So let's assume Google can throw all their machines (rumored to be as
many as 100K) on the problem:

>>> 1e-6 * 2**64L / 3600 / 24 / 365 / 100000
5.8494241735507195

So it takes about 5 years for them to generate a collision. Practical
in some sense, and with dedicated hashing hardware (and ridiculous
amounts of storage), possibly even doable in weeks or days.

But the trouble is that the recently discovered attacks are not
finding a collisions with the hash of an existing text (a preimage
attack), but finding one between two random hashes. The existing text
case is still expected to be well beyond the reach of currently
available hardware.

So there just isn't much that can be done in the way of practical
exploits against Mercurial with these new attacks.

Within the next year, we may know more, and have a better idea of
what's actually worth switching to. For now, practical attacks are a
ways off.

-- 
Mathematics is the supreme nostalgia of our time.


More information about the Mercurial mailing list