[tahoe-dev] [tahoe-lafs] #753: use longer storage index / cap for collision resistance

[tahoe-lafs]

#753: use longer storage index / cap for collision resistance
---------------------------+------------------------------------------------
 Reporter:  warner         |           Owner:           
     Type:  defect         |          Status:  new      
 Priority:  major          |       Milestone:  undecided
Component:  code-encoding  |         Version:  1.4.1    
 Keywords:                 |   Launchpad_bug:           
---------------------------+------------------------------------------------

Comment(by warner):

 Well, "It Depends". Current servers do no checking of shares.

 (I agree, I like server-side share-verification, except for the load and
 complexity it adds to the storage servers)

 == Immutable Files ==

 Current code has uploaders quietly+simplisticly believing servers who say
 "I
 already have a share by that SI", without additional checking. (they don't
 search very far for existing shares, but if the server list is the same as
 it
 was for the first file, they'll get complete overlap). This results in the
 second file appearing to upload correctly but being completely
 unrecoverable
 (all shares for that SI are for the first file, so a download of the
 second
 file will get shares that fail the hash checks and fail).

 The uploader that we haven't written yet will probably search further for
 existing shares (especially once it's seen evidence of one), and will do
 some
 amount of verification of those shares (at the very least pulling down the
 UEB to make sure it's for the same file). This uploader will see evidence
 of
 an SI collision and probably fail the upload (with an exception that
 basically says "please pick a different SI, perhaps a random one").
 Unless,
 of course, you're unlucky and wind up talking to a different servers
 during
 the two uploads. The subsequent downloader will either succeed but notice
 a
 lot of "corrupted" shares (if they can talk to the second uploader's
 servers)
 or fail due to a lot of corrupted shares (if they can't).

 If we further improve the servers to verify the integrity of immutable
 shares
 upon receipt, and we change the protocol to split server-selection-index
 from
 storage-index, and assume that the SI is required to be derived from the
 verifycap (so that servers can validate the share all the way up to the
 SI),
 then we're still in the same boat as the previous paragraph: servers who
 don't yet have a share will accept either the first upload or the second
 (since we're assuming a too-short SI, and these two files are colliding),
 and
 if the second upload succeeded due to disjoint peersets, then second-file
 downloaders will succeed or fail depending upon which servers they're able
 to
 talk to.

 == Mutable Files ==

 We get the same issues here: if the storage-index is too small, then there
 will be multiple RSA keys which map to the same SI. A validating server
 which
 has accepted a share for key1 will reject an update for key2 (because it's
 looking at the full pubkey inside the share), but other servers might
 accept
 key2 (if they don't already have a share).

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