[Monotone-devel] a sha-0 collision

[graydon hoare]

hi,

as you may all have read on slashdot recently, someone has found a
collision in SHA-0.

http://www.mail-archive.com/cryptography%40metzdowd.com/msg02554.html

this is not the disaster that it sounds like, and certainly doesn't
represent complete brokenness of the hash, much less monotone.

first, some caveats about their effort:

 - they collided SHA-0 not SHA-1.

 - all hashes collide on input spaces bigger than their
   output space. this is a fact. it is not a cut-and-dried proof
   of hash algorithm brokenness to have found a collision: it is
   simply a lower-bound reducing (weakening) of some of the
   desired cryptographic "hardnesses" associated with various
   related tasks.

 - theoretical weakness in SHA-0 has been known for some time.
   this is just an example of someone throwing a lot of hardware
   at the problem for demonstration purposes.

 - they collided it over 2 weeks of a small supercomputer's time,
   which is still not exactly trivial. it is still much cheaper
   for most attackers to pay an insider to compromise a system.

 - they collided two small (256-byte) random inputs: this means
   they were searching for a colliding pair (birthday paradox
   metric) not working with a chosen preimage.

 - this only relates to active attack; there is no clear consensus
   about the odds of unintentional SHA-1 collision having changed.

second, how it affects monotone:

 - if SHA-1 falls completely (trivial inversion), it is a small
   amount of work to switch monotone to a new algorithm. this is
   a simple fact of life when working with security software: it
   is an arms race. we will have to do the same when someone
   trivializes RSA as well (as will SSH, SSL, GPG...)

 - content addressing has the wonderful property that you can
   recompute all existing object identifiers under a new hash,
   so history doesn't get lost if we do this. it just creates
   a communication barrier with old clients. we'll bump the
   protocol number and carry on.

 - before trotting out the "this would not happen if only you used
   GUIDs rather than hashes" argument, consider: a GUID in a system
   with a broken digesting function likely has all its digest-based
   RSA signatures broken too, so is exactly as insecure as one in
   which the identifiers themselves are suspect.

as I said, working with security software means working in an arms
race. it doesn't matter if some of the objects in your system are
named by DNS or GUID or clock or what have you: your security
ultimately rests on upholding the hardness of some tasks, and hard
things get made easier by clever people all the time.

(and yes, in the future, say in between 1.0 and 2.0 when we're sipping
 drinks on a tropical island, it may be worth the time to reorganize
 monotone's database to slowly randomize hash seeds to help detect and
 correct the most corner-y of corner cases, but we have more pressing
 bugs at the moment.)

-graydon