David-Sarah Hopwood wrote: > Brian Warner wrote: >> David-Sarah Hopwood wrote: >>> I've designed a new version of the cap protocol I posted a few days >>> ago, that addresses Brian's comments about roadblock attacks.
(Current version at <http://jacaranda.org/tahoe/mutable-addonly-elkpoint-3.png> <http://jacaranda.org/tahoe/mutable-addonly-elkpoint-3.svg>.) [...] >> * The destroy-cap is a neat bit of feature, but I'd want to think about >> it further before actually building it in. It makes a lot more sense >> in the context of add-only files.. if you don't have those, then >> there's not a lot of difference between filling the mutable slot with >> an empty file and completely destroying the slot. > > It makes sense for both add-only files and immutable files. Note that in > the case of immutable files it doesn't compromise collision resistance: > after a file has been destroyed it is possible for it to be recreated at > the same storage index (and made accessible by the same read cap), but in > that case it must have the same contents. Note that there's a minor error in the diagram concerning the destroy cap: it shows the destroy cap as KD, but in fact it has to include S and T as well as KD. This is so that the holder of a destroy cap can determine the storage index (and therefore which servers hold shares), and so that the servers are able to index shares only by their storage index. > Of course there are limitations to how thoroughly a file can be deleted, In support of how difficult it is to delete data by deleting shares in a DHT-based storage system, see the paper at: <http://www.freedom-to-tinker.com/blog/felten/breaking-vanish-story-security-research-action> The attack described there is not directly relevant to Tahoe unless it were used in a particular unusual way; however, the paper shows that it is easy to overestimate the cost to an attacker of collecting a large proportion of the shares stored in a DHT. Of course in Tahoe, recording the ciphertext of shares will only help attackers who have the corresponding read caps. On the other hand, they could record the ciphertext and only gain access to the read cap later. > given that it can *necessarily* be recreated even by anyone who knows just > the "green" information, i.e. they don't need to have had the read cap. Actually this may not be true, if the servers retain a small amount of information about each share that has been deleted; see below. > I agree that we need to think about this feature further before deciding > whether to add it. As I see it, there are several classes of reasons why > you might want to delete a file: > > a) you don't care about it any more and want the space to be reclaimable. This reason is not affected by the fact that an attacker can retain copies of shares, since the attacker will pay the cost of storing their copies. However, that assumes that upload messages cannot be directly replayed by an attacker in such a way that the storage cost will be charged to the quota of the original uploader. (So, if a signature on an upload message is used to authenticate that it should be charged to a given quota, the message that is signed should include a fresh challenge from the server.) > b) its contents are obsolete and you no longer want people to rely on > them, even though it isn't important whether they know the contents. > c) you have a legal and/or moral obligation to no longer store the > contents or otherwise contribute to providing access to them. Define an "undeletion attack" to be an attack that reinstates a deleted share in such a way that it can still be read by an existing read cap. Provided undeletion attacks are not possible, the fact that an attacker can retain copies of shares does not prevent deletions for reason b) and/or c) from being effective: in b), the fact that an attacker holds copies does not prevent deletion of the original shares (if they cannot be undeleted) from acting as a signal that the content is obsolete. in c), servers that were asked to delete their shares of a file are no longer contributing to providing access to the content. If an attacker knew the plaintext then it can re-upload it, but only at a new storage index, so that existing read caps are invalidated. Attackers who do not know the plaintext or read cap cannot re-upload it. This adequately discharges the server operator's obligations. To prevent undeletion attacks, it should be possible to tell a server to remember that the share at a given storage index has been deleted. The cost of storing this information (which is much smaller than the original file) can be accounted for by the usual quota mechanism. Note that some care is required to simultaneously prevent both undeletion attacks and roadblock attacks, because deletion could potentially be used to create a roadblock. For example, in the Elk Point 3 design, if the server *only* remembers storage indices that have been deleted, then that would enable a roadblock attack with cost 2^t, because the attacker would only need to find an (EncK1, Dhash, V) triple that is a T-bit preimage for the T value of the target share, and use it to delete the share before it is uploaded. (It is desirable to allowing a share to be "deleted" even if it does not yet exist on a given server, to ensure that it cannot be uploaded to that server in future.) To prevent such attacks, what the server should remember for each deleted share, is the verify cap (S, T, U). That can be implemented by mapping each storage index S || T to a set of shares, and a set of deletion records each consisting of a U value. When a share is uploaded, the server should refuse to store it if the corresponding storage index has any deleted U value that matches that share. Adding a share or deletion record at a given storage index, would not displace any existing shares or deletion records at that index for which the U values do not match. For this scheme to be secure against undeletion attacks, it must not be possible to find a share related to a given share for a file F, that will fail to verify, but nevertheless be readable by a read cap for F. The Elk Point designs do appear to have that property: changing any of EncK1, Dhash, or V in a share will cause it to be unreadable as well as failing to verify. It is also possible to change Sig_KR, but that does not matter because uploaded shares are only checked against deleted U values; Sig_KR is checked separately. > d) you screwed up and made information available that should have been > confidential. We wouldn't claim to address this case. -- David-Sarah Hopwood ⚥ http://davidsarah.livejournal.com _______________________________________________ tahoe-dev mailing list [email protected] http://allmydata.org/cgi-bin/mailman/listinfo/tahoe-dev
