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

[David-Sarah Hopwood]

Brian Warner wrote:
> [only responding to one point right now since I don't have much time;
> I'll try to respond to the rest later]
> 
>> Actually the KC_sign value acts either as an add-only cap, or as a
>> write-only cap when it is used for mutable files. A write-only cap
>> does not allow reading any of the previous plaintexts or future
>> plaintexts. I don't know how useful this is, but it was trivial to
>> support.
>>
>> Also note that "full-writecap" doesn't make sense in the add-only
>> case, since there is no writing, only adding and destroying. (It might
>> have been a mistake to try to explain the mutable and add-only cases
>> in the same diagram, but the crypto was identical.)
> 
> Actually, the add-only (or "write-only") cap needs another couple layers
> of boxes, because we'll need asymmetric encryption (as opposed to
> authentication) for it. KC_sign allows an adder/writer to create signed
> values that will be accepted by readers, but it doesn't give them a way
> to add confidential data which can only be read by readers (and not by
> everyone else).

Oh, good point. I'll fix that in the next version.

> I suppose another useful diagram might to show the various caps in
> different columns, list the operations available for each (write, add,
> read, verify), the strengths of the security properties available to
> each (C/I/Ir bits, collision resistance, etc), and which attenuations
> can be performed with or without server interaction. There should be an
> additional column for the server itself, showing how strong of a
> verification step it can do rooted solely upon the storage-index.

I may do that as text; it takes quite a bit of time to draw the diagrams
in Inkscape.

> One more idea to throw out.. to make the immutable uploading process
> more stateless, we were thinking of defining an "upload id", which is
> used from the initial "will you accept my share" request to the final
> "that was the last byte of the share, make it visible to the world".
> This upload-id would bind together all of the various pipelined messages
> that will constitute the upload. (the storage-index could be used for
> this, except that in our new schemes, it won't be known until the end).
>
> The upload-id could also be used to resume an interrupted upload,
> assuming the client can remember (or re-derive) it, and the share hasn't
> been finalized.
> 
> Now, to avoid needing an encrypted transport, we must avoid shared
> secrets, so one idea we've discussed was to use an ECDSA keypair as the
> "upload id". Basically the initial "will you hold my share" request
> includes a verifying key, and all subsequent upload messages will be
> signed by the corresponding signing key. When the upload process is
> finalized, the keypair is discarded. This keypair could even be shorter
> than usual, because it doesn't need to provide long-term security.
> 
> Anyways, such a keypair might tie in to some of the other
> proof-of-knowledge schemes you've mentioned.

In principle it could be the same keypair as the one used for the proof
of knowledge of R, provided that it is not dependent on UEBhash (i.e. if
S depended only on R and not T). However, the proof of knowledge isn't
really needed in the immutable case, because t needs to be large enough in
that case for the read cap to provide sufficient collision resistance,
which will also make it large enough to prevent roadblocking.

For example, if we want 2^n work to find a collision, then t must be equal
to n (so that (n+t)/2 = n), therefore the proof-of-knowledge scheme is not
needed because roadblocking would take 2^t = 2^n work anyway.

It's only in the mutable case, where we want the read cap length to
be less than 2n bits, that we need the proof-of-knowledge scheme.
But in that case there is no requirement for a separate upload id, since
the storage index can be computed immediately (once the KC_sign/verify
keypair has been generated) before doing erasure coding or encryption.

(Another advantage of having t >= n for immutable files, is that then
it is not necessary to have two kinds of read caps, one kind that can
be off-line attenuated to a verify cap, and a shorter kind that can't.
If t = n, then we will have n bits of integrity from a verify cap derived
directly from a 2n-bit read cap without using the U field. As the notes
on the right-hand-side of the diagram point out, the protocol does not
attempt to prevent the creator of a file from producing verify caps that
result in false positives. Therefore, collision resistance is not a
requirement for verify caps, and so n bits is enough.)


Re using an ECDSA keypair as the "upload id":
I think it's desirable to continue to avoid relying on public key
cryptography in the immutable file protocol. The above argument shows
that we don't need it to prevent roadblock attacks. In fact the only
advantage of using it, would be to make the authentication of
uploaded data per-message rather than per-upload (since the integrity
of the whole upload will still be protected by the check on T being
derived from the UEBhash). That might be of benefit against an
attacker who can disrupt individual messages only with some probability
significantly less than 1; but I think it is more reasonable to
assume that if an attacker can disrupt any messages between a given
client and server, then it can disrupt all of them.

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