Re: [openpgp] [Cfrg] streamable AEAD construct for stored data?

[Taylor R Campbell <[e-mail]>]

   Date: Fri, 30 Oct 2015 08:11:48 +0900
   From: Daniel Kahn Gillmor <[e-mail]>

    b) it doesn't seem to compose as well with asymmetric signatures as one
       might like: a signature over the whole material can't itself be
       verified until one full pass through the data; and a signature over
       just the symmetric key would prove nothing, since anyone getting the
       symmetric key could forge an arbitrary valid, decryptable stream.
       Is there an intermediate approach that would combine an asymmetric
       signature with a chunkable authenticated encryption such that a
       decryptor could stream one pass and be certain of its origin (at
       least up until truncation, if (a) can't be resolved)?

If only the receiving end needs streaming -- that is, if the sender
can process an entire message before the receiver receives any of it
-- then you can relatively easily address this, as Tahoe-LAFS does,
given a session key k:

(sender)
1. Break the data up into bounded-size chunks.
2. (Symmetrically encrypt the chunks with k if you want.)
3. Compute a Merkle tree under a PRF keyed by k of the chunks.
4. Sign the root of the Merkle tree.
5. Store the signed root, and each chunk alongside its path down the
Merkle tree.

This requires only O(log n) working memory to compute the Merkle tree
-- it takes a single pass over the whole input.

(receiver)
1. Verify the root of the Merkle tree.
2. When receiving a chunk and a path, verify the path from the root.
3. (Decrypt the chunk with k if you want.)

For public signatures, you can fix k = 0 and hope nobody finds
collisions in PRF_0, or randomize k and hope nobody finds
target-collision attacks on PRF (which is unlikely -- even MD5(k, m)
is probably still OK for that, as far as I know).  For authenticated
encrypted messages, you can derive it from a DH shared secret, or do
standard public-key-encrypted key wrap, &c.