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

[David-Sarah Hopwood]

David-Sarah Hopwood wrote:
> 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.

Diagrams:
<http://jacaranda.org/tahoe/imm-short-readcap-davidsarah.png>
<http://jacaranda.org/tahoe/imm-short-readcap-davidsarah.svg>

The diagrams omit the intermediate hashes H(plaintext) and H(ciphertext),
since they are not strictly necessary. I've uppercased some of the variable
names to be consistent with Zooko's diagram.

> Explanation:
[...]
> 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.

I may not have been clear enough that this approach gives a confidentiality
strength of "only" 2^n, even though the read cap length is 2n bits. This
is a disadvantage, but I don't think it is a serious one as long as n is
chosen to be at least 128 bits.

> The mutable case is similar, but with added asymmetric sauce:
> 
> let   writecap = W = random seed
>                 K1 = KDF("K1", W)
> (K_sign, K_verify) = generate_keypair(KDF("key pair", W))
>                  R = H_n(K1, K_verify)
>         ciphertext = encrypt[K1](plaintext)
>                sig = sign[K_sign](ciphertext)
>             K1_enc = encrypt[R](K1)
>        storage_idx = H_n(R)
>                 V' = H_n(storage_idx, K1_enc, K_verify)
>        readonlycap = R
>      readverifycap = (R, V')
>          verifycap = (storage_idx, V')
> 
> The server stores (storage_idx, K1_enc, ciphertext, sig, K_verify).
> 
> The verification check is
> 
> verifycap.storage_idx == server.storage_idx &&
> verifycap.V' == H_n(server.storage_idx, server.K1_enc, server.K_verify) &&
> verify[server.K_verify](server.sig, server.ciphertext)

Diagram:
<http://jacaranda.org/tahoe/mut-short-readcap-davidsarah.png>
<http://jacaranda.org/tahoe/mut-short-readcap-davidsarah.svg>

Note that Firefox can render the SVG files, but does a poor job of it.

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