[tahoe-dev] [tahoe-lafs] #217: DSA-based mutable files -- small URLs, fast file creation

[tahoe-lafs]

#217: DSA-based mutable files -- small URLs, fast file creation
----------------------------+-----------------------------------------------
 Reporter:  zooko           |           Owner:  zooko     
     Type:  enhancement     |          Status:  assigned  
 Priority:  major           |       Milestone:  eventually
Component:  code-mutable    |         Version:  0.7.0     
 Keywords:  mutable crypto  |   Launchpad_bug:            
----------------------------+-----------------------------------------------

Comment(by zooko):

 I have realized that embedding an ECDSA public key directly into the
 capability doesn't allow for caps to be as short and secure as embedding a
 secure hash of an ECDSA key into the capability. That's because ECDSA keys
 have a crypto strength in bits which is half of their size in bits, but
 secure hash functions have a crypto strength in bits against second-pre-
 image attacks which is equal to their size in bits.

 Now, traditionally in Tahoe we don't rely on a {{{K}}}-bit hash function
 for more than {{{K/2}}} bits of security, because that way we don't have
 to think about the situation that collisions are feasible even though
 second-pre-images aren't.  (Collision-resistance can't be better than
 {{{K/2}}} because of the "Birthday Paradox".)

 Now when we're talking about immutable file caps, we have to keep doing
 that, because the user-visible requirement on an immutable file cap is
 that there is exactly one file that can match it. So immutable file caps
 in the new crypto cap scheme will still need to be sufficiently long,
 let's say 256-bits long, that nobody can find a collision. They would look
 like this:

 {{{
 iaUVPT93Sw1xp9u1MX6JTrv5IMse29V34ZaZ2U8JK91E
 }}}

 (256 bits) (See http://allmydata.org/trac/tahoe/ticket/102 for some other
 details about formatting of caps.)

 But for mutable files, the user-visible requirement is that an
 unauthorized writer can't create files that would match, which corresponds
 to second-pre-image resistance instead of collision-resistance, so the
 caps can look like this:

 {{{
 raIUXhc56d4U18EAlpxZph
 }}}

 (125 bits)

 I think it would be valuable to have the latter kind of caps that are that
 much shorter.  The smaller the caps are, the more uses people will adopt
 them for.  The short 125-bit caps are within striking distance of "tiny
 urls".  Here's the first tiny url that I found on twitter just now:
 http://bit.ly/ossLb .

 There is a trade-off to this, however -- you can't do off-line diminish
 from a write-cap to a read-cap (or a verify-cap) in this scheme. On the
 other hand, the caps are small enough that you can carry around both the
 write-cap and the read-cap in the same space that would hold just the
 write-cap in the other scheme, which is just as good as doing off-line
 diminish from write-cap to read-cap, if you thought to keep the read-cap
 around.

 Another trade-off is that this makes us vulnerable to weaknesses in a
 secure hash function in addition to weaknesses in the digital signature
 scheme.

 (By the way, in the future, using this scheme would make it easier to use
 a digital signature scheme which has even more than 2K bits in its public
 or private keys. Of particular interest to me are schemes for post-quantum
 cryptography (http://cr.yp.to/talks/2008.10.18/slides.pdf ) such as
 "multivariate quadratic" signatures e.g. sflashv2. Here are benchmarks:
 http://bench.cr.yp.to/results-sign.html .)

-- 
Ticket URL: <http://allmydata.org/trac/tahoe/ticket/217#comment:43>
tahoe-lafs <http://allmydata.org>
secure decentralized file storage grid