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

[David-Sarah Hopwood]

Below, H_x is a hash with output size x bits. H is a hash for which
there is no constraint on output size.

Brian Warner wrote:
>  * verifycap cannot be offline-derived from readcap: [...]
>  * we can't determine the storage-index until after we've encoded the
>    entire file [...]

We can fix both of these problems without increasing the size of an
immutable readcap (i.e. 2n bits for security parameter n).

Mutable files don't have the second problem, but in that case we can fix
the first problem at the cost of only doubling the bit length of a
read/verifycap to 2n bits. (These read/verifycaps can be truncated
to give an n-bit readcap as before, but the truncated readcap cannot be
offline-attenuated.)

I'll describe the immutable case first:

let          k1 = random symmetric key
              r = H_n(k1, H(plaintext))
     ciphertext = encrypt[k1](plaintext)
              v = H(ciphertext)
         k1_enc = encrypt[r](k1)
    storage_idx = H_n(r)
             v' = H_n(storage_idx, k1_enc, v)
        readcap = (r, v')
      verifycap = (storage_idx, v')

The server stores (storage_idx, k1_enc, ciphertext).

The verification check is

verifycap.storage_idx == server.storage_idx &&
verifycap.v' == H_n(server.storage_idx, server.k1_enc, H(server.ciphertext))

There is an additional constraint on the encryption schemes used on
k1 and the plaintext: if there are any additional random inputs to
these schemes, such as IVs, they must be included in the input to
the hash used to compute r (this is not shown above). Since the keys
are only used once in the immutable protocol, it is probably simpler
to avoid using random IVs.


Explanation:

For immutable files, we absolutely need 2n bits in a readcap to obtain
collision resistance. It is desirable to also have 2n bits in a verifycap,
to prevent an attack where the creator of a file can use a collision to
generate a verifycap that will succeed in verifying invalid ciphertext
(it isn't clear that this is a particularly useful attack, but it turns
out we can prevent it at no significant cost).

However, these 2n bits do not need to all be in the value called r in
Zooko's protocol. r needs to be at least n bits, in order to obtain
sufficient security against brute-force attacks. However, it is possible
for the other n bits of a readcap to encode information that both allows
performing verification, and contributes to collision resistance.

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.


The mutable case is similar, but with added asymmetric sauce:

let       writecap = random seed
                k1 = KDF("k1", writecap)
  (kSign, kVerify) = generate_keypair(KDF("key pair", writecap))
                 r = H_n(k1, kVerify)
        ciphertext = encrypt[k1](plaintext)
               sig = sign[kSign](ciphertext)
            k1_enc = encrypt[r](k1)
       storage_idx = H_n(r)
                v' = H_n(storage_idx, k1_enc, kVerify)
       readonlycap = r
     readverifycap = (r, v')
         verifycap = (storage_idx, v')

The server stores (storage_idx, k1_enc, ciphertext, sig, kVerify).

The verification check is

verifycap.storage_idx == server.storage_idx &&
verifycap.v' == H_n(server.storage_idx, server.k1_enc, server.kVerify) &&
verify[server.kVerify](server.sig, server.ciphertext)

This is all much clearer if you can see a flow diagram, so I'll draw some
diagrams and post them later tonight.

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