[darcs-users] Why Bitkeeper still wins

Jamie Webb j at jmawebb.cjb.net
Tue Mar 22 14:53:29 UTC 2005


On Tue, Mar 22, 2005 at 02:34:26PM +0100, Daan Leijen wrote:
> >That depends on your definition of useful. The break in SHA1 is
> >largely theoretical at this point. 
> >
> Well, Bruce Schneier seems to say that it is definitely broken (as of 
> February 15, 2005):

Yes. It's broken, as I said. It now takes 2^69 ops to find a
collision, rather than the 2^80 required for a brute force attack.
Which in a few years time might be a reasonable number of ops for a
supercomputer to perform. But, you must understand what they mean by
'find a collision'. They can find two random strings of garbage with
the same hash. This has a lot of theoretical significance, and may
pave the way to more severe attacks, but it does not allow them to
take one meaningful document written by someone else, modify it to
introduce a malicious meaning, and then add a few bytes to give it the
same hash. That is /much/ harder. I.e. doing it by brute force
requires typically 2^159 ops, not 2^80.

There may be social engineering workarounds that allow a
two-chosen-texts attack (AFAIK it's not been suggested that the
current break provides this, but it at least lays the groundwork), but
due to Monotone's tree-versioning approach I couldn't think of a
practical one. Also, no such attack would be possible against existing
tree versions (because this attack depends on 'planting' a patch and
at present there's not enough computing power to calculate a patch to
plant) and so could only be mounted against the trees that are
'current' in a few years time (when 2^69 ops is feasible), by which
time Monotone will presumably have changed hash.

In summary: feel free to object to Monotone. I don't use it either.
But the fact that it currently uses SHA1 is not a sound reason.

-- Jamie Webb




More information about the darcs-users mailing list