[tahoe-dev] how to encrypt, integrity-check, and offline-attenuate with only 2n bits

[Brian Warner]

Thanks so much for the diagrams! They make this a lot easier to follow.
I've attached a modified diagram (apologies for my crude artwork) with
some modifications to achieve the low-alacrity validation part that I
was talking about: the black arrows show how we should create the same
UEB that the current immutable-encoding protocol uses, and use it to
generate both R and the verifycap.

I've also added a red X (removing SI from the input to the V' hash),
because I was going to argue that folding the storage index into the
"V'" value doesn't improve the validating power of the verifycap holder
or the storage server. But, in reading through your explanation, I think
this may be false, specifically because of this paragraph:

> There is a potential weakness that we need to avoid: in order for the
> two halves of the readcap to effectively act as a single hash value
> for the purpose of obtaining collision resistance, it must not be
> possible to find a collision for one of the H_n hashes (with 2^(n/2)
> work), and then find a collision for the second H_n hash (also with
> 2^(n/2) work) by varying its input while leaving the input to the
> first hash fixed. The protocol above prevents this by making v' a
> deterministic function of r, so that the attacker has no freedom to
> independently vary the second hash's input.

Is the fact that R affects K1enc (which then affects V') insufficient to
provide this property? If I applied my red X, would the readcap (=R+V')
be reduced in integrity-strength from 2n bits to n bits?

So, I see how this gives us a 2n-long readcap, where the n-bit long "R"
value provides both confidentality and integrity, and the other n bits
"V'" provide additional integrity.

And I see how the verifycap will be n+len(storageindex) bits long, and
the V' value provides the same n bits of integrity. However, I don't see
how the verifycap's copy of the storage index brings it up to 2n bits of
integrity. I can find two colliding shares, both with SI="1", with
different ciphertexts, that generate the same V' value (but different R
values), with a work factor of 2^(len(V')/2) (i.e. n/2). I put one share
each on two different servers, then give the common verifycap to a
repair process. Which share should it believe? The readcap-holder won't
be fooled (since to make the readcap collide too, I'd have to find a
collision for both V' and R, which is twice as long, assuming that the
intermediate UEBhash is at least 2n long). But the verifycap holder
would be, since it doesn't get to know R, and so it can't confirm the
share->R->SI->verifycap path.

So I'd argue that this scheme results in a verifycap that's half as
strong as the readcap.

And I'll still argue that the server gets zero gives of integrity
checking. Even if you give the server a copy of the "correct" value of
V' along with the rest of the share, why should it believe you? Suppose
I've learned that you've just started to upload shares for SI="1". I
create a share full of junk, pretend I'm storing it under SI="1",
compute my V' value, then run to remaining storage servers and upload
the whole thing before you can complete your uploads. The server could
compute it's own copy of V' and confirm that they match the one that
I've provided, but it doesn't prove anything. If the server accepts my
shares, then you'll be unable to upload your own legitimate ones.

The only way to provide this server-side validation is to make the
storage index be a hash of the share contents, so the server can reject
uploads which don't match. Giving it additional hashes that don't get
included in the SI doesn't help. And, in this scheme, we *must* have the
SI derive from the readcap instead of the share contents, otherwise the
readcap-holder will never be able to locate the share contents in the
first place.

As before, I'm still stuck :).

I'll take a look at the mutable diagram separately.

thanks! this discussion is great!
 -Brian
-------------- next part --------------
A non-text attachment was scrubbed...
Name: imm-short-readcap-brian.png
Type: image/png
Size: 114397 bytes
Desc: not available
URL: <http://tahoe-lafs.org/pipermail/tahoe-dev/attachments/20090909/21cc4c0c/attachment.png>