[tahoe-dev] Deletion in the Elk Point cap protocol

[David-Sarah Hopwood]

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