[tahoe-dev] "Elk Point" design for mutable, add-only, and immutable files

[David-Sarah Hopwood]

James A. Donald wrote:
> Zooko O'Whielacronx wrote:
>> We should think that issue through, along with the accompanying issue
>> of "how low a chance of success is low enough".  If there are 2^50
>> caps in use, and some technique can "attack all known caps at once",
>> then do we need to increase the size of the caps (possibly by up to 50
>> bits) to make it so that the chance of success against *any* target is
>> still negligible?  Or is it just unreasonable to think that some
>> adversary would spend massive amounts of computer power in order to
>> forge some random cap out of a large set of caps? 
> 
> Obviously this depends on what caps are being used for.  For what caps 
> are *now* being used for, no one would to forge some random cap out of a 
> very large set of caps.
> 
> If caps were used for the purpose that the shared secret of a credit 
> card is used for, *then* people would be interested in forging some 
> random cap - but that is a new kind of cap, which could be defined with 
> a new number of bits.

I disagree. I'm in favour of choosing conservative parameters from the
start, on the basis that (as has been proven time and time again) users
are in the habit of employing protocols in unusual and surprising ways
*without* consulting any cryptographers or implementors, or changing any
parameters from the defaults. That is, you simply cannot assume that you
know how a protocol will be used, or reused -- or that you know what
attackers' motivations might be.

In any case, Tahoe is supposed to be a fully general-purpose file storage
system, so we have no idea what will be stored in it (or for how long),
even if it is only used for storage as such.

However, I think that conventional wisdom about reasonable key and hash
sizes does already factor in low-success-probablity and multiple-target
attacks to *some* extent, although perhaps not quite conservatively enough.

The page at <http://allmydata.org/trac/tahoe/wiki/NewCaps/WhatCouldGoWrong>
now takes into account such attacks in the cost formulae:

 - the cost for attacks on encryption is proportional to the success
   probability
 - the cost for preimage attacks is proportional to the success probability
   divided by the number of targets
 - the cost for a collision attack is proportional to the square root
   of the success probability.

So yes, adding 50 bits, or maybe 40 bits (to R, preferably) will effectively
squash the multiple-target attacks, and low-success-probability attacks are
probably adequately taken into account already by a 128-bit key. 50 bits is
only about 8 or 9 characters in a base-62 URI; it's not so bad.

-- 
David-Sarah Hopwood  ⚥  http://davidsarah.livejournal.com