Re: [9fans] In case anyone worries about block hash collision in venti

[Georg Lehner <jorge-plan9@magma.com.ni>]

About a year ago i wrote a (kind of vapourware) backup system called Baccus,
based on content addressed storage. Most ideas are stolen from Plan9/venti,
but for the here discussed reasons i used the Salsa family of hashes
from Dan
Bernstein:

http://cr.yp.to/chacha.html

Respectively the Rumba-"compression":

http://cr.yp.to/rumba20.html

I combined hashing and encryption with Salsa/Rumba into one step.

The hash function in Baccus is pluggable, so the user could decide which to use
and would be able to upgrade to a stronger hash.

Maybe pluggability of the hash function would be a nice addition to venti
(if it is not there anyways).  Also Salsa should be considered a valuable addition
to Plan9.

Regards,

	Jorge-Le�n

P.S.: Here is the link to Baccus: http://wiki.tcl.tk/23064, but beware: it is in a bad
state and style.  Didn't have time to improve since then.  If you still want to look
at it, start with reading the CREDITS file.

PS2: You need at least eight rounds, else you get lots of hash-collisions.


Tim Newsham wrote:
>> 1.  the sender can't control email headers.  many
>> transfer agents add a random transfer-id which
>> would confound this attack.
>
> If you know the size of the transfer id, you can pad out
> to the next full block size.
>
>> 2.  if the rcpt uses mbox format, the sender can't
>> control how your message is fit into venti blocks.
>> the sender would need to control the entire
>> mail box.
>
> I'm ignorant on this front.
>
>> 3.  http://en.wikipedia.org/wiki/SHA_hash_functions
>> says that there have been no SHA1 collisions found.
>
> IIUC there has been significant progress in attacking
> all major hash functions and the cryptographic community
> has low confidence in all major hash functions at the
> moment.  Some hash algorithms have more serious attacks
> than others, but once a few weaknesses are found its
> usually an indication that the algorithm will fall soon.
>
> Re: SHA1, it looks like the strenght has been whittled
> down to around 2^52 operations:
> http://www.schneier.com/blog/archives/2009/06/ever_better_cry.html
>
> I'm not saying that there is a viable attack against
> your SHA-indexed venti right now.  I'm saying that its
> bunk to evaluate the storage system simply on how likely
> it is for a random collision to occur.  The proper analysis
> is how hard it is for a malicious attacker to cause a
> collision now and in the near future.
>
>> - erik
>
> Tim Newsham | www.thenewsh.com/~newsham | thenewsh.blogspot.com
>