Subject: [openpgp] streamable AEAD construct for stored data?

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

Hi CFRG folks--

We're looking into fixing the OpenPGP symmetrically-encrypted data
formats for RFC4880bis.  The structures are used for mail messages but
also for large file encryption.  It's clear that the OpenPGP CFB mode
isn't designed to modern symmetric encryption standards, so we're hoping
to introduce a better approach.

We need, among other things to address integrity protection in a more
meaningful way than the current OpenPGP MDC (modification detection
code), which is basically a SHA-1 hash of the cleartext.  This was never
much better than a band-aid.  And as discussed in the recent "OpenPGP
SEIP downgrade attack" thread, an "integrity-protected" packet with an
MDC can be stripped down to produce a syntactically-valid packet without
integrity protection.

But one of our constraints is the OpenPGP use case that streams
decrypted data, like this:

 pgp --decrypt <backup.pgp | tar x

It's unlikely that this use case will go away.

With the MDC approach, or even with a full-packet AEAD approach, the
decryption command either has to (a) buffer all data before producing
output, or to (b) risk producing intermediate output that it later
discovers is not integrity-protected.

A better approach would be a streamable/chunked AEAD approach -- this
would allow the decrypting process to release integrity-checked chunks
as it goes.

AGL describes this problem here:

 https://www.imperialviolet.org/2014/06/27/streamingencryption.html

and he roughly outlines a generic construction of a composable/chunkable
approach using AEAD:

> Ideally such a scheme would take an AEAD and produce something very
> like an AEAD in that it takes a key, nonce and additional data, but
> can safely work in a streaming fashion. I don't think it need be very
> complex: take 64 bits of the nonce from the underlying AEAD as the
> chunk number, always start with chunk number zero and feed the
> additional data into chunk zero with a zero byte prefix. Prefix each
> chunk ciphertext with a 16 bit length and set the MSB to indicate the
> last chunk and authenticate that indication by setting the additional
> data to a single, 1 byte. The major worry might be that for many
> underlying AEADs, taking 64 bits of the nonce for the chunk counter
> leaves one with very little (or none!) left.

Two examples of projects that take something like this approach are
miniLock and Tahoe-LAFS:

 https://github.com/kaepora/miniLock
 https://tahoe-lafs.org/trac/tahoe-lafs/browser/docs/specifications/file-encoding.rst

I'm unaware of any formalization of this approach, though.  Does anyone
know of one?  If OpenPGP were to adopt AGL's construct, are there
specific risks to be aware of?

This approach still has two notable problems i can see, which may or may
not be addressable (but if they are, i'd love to hear it):

 a) it doesn't deal with truncation -- the initially-streamed data has
    already been streamed by the time a truncation is discovered.
    (there may be no way to fix this; it seems kind of like a fact of
    nature, and if so, systems should only do streaming decryption if
    they're capable of coping with truncation)

 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)?

Thoughts, pointers, or suggestions would be much appreciated.

         --dkg

---

From: Watson Ladd <[email-masked]>
Date: Fri, 30 Oct 2015 08:30:44 -0400

On Oct 30, 2015 8:25 AM, "Natanael" <[email-masked]> wrote:
>
>
> Den 30 okt 2015 11:01 skrev "Daniel Kahn Gillmor" <[email-masked]>:
> >
> > Hi CFRG folks--
> >
> [...]
> Does it help to define the ciphertext length and check that first, before
decrypting? Doesn't help if the file isn't local and the connection is
broken, but then at least your software should detect that and halt of
necessary.
> > Thoughts, pointers, or suggestions would be much appreciated.

Use authenticated encryption so no signatures are required. Detached
signature verification is used for large public messages already: no
streaming needed.
>
> To solve B what you need to do is something like signing a list of
ciphertext hashes/authentication tags.

The idea below demands conditions beyond MAC security.

>
> One thought I've had before (my idea is to use it for FDE*) is to for
example use HMAC over segments (including counters) or to extract AEAD tags
(prefixed with counters to preserve order) and create a Merkle tree hash of
those lists when creating the message, to then sign that Merkle tree, such
that when you decrypt and recreate the tags for comparison you can confirm
that nothing has been modified (with the level of assurance that the tags
can provide). Or you skip the standard AEAD and MAC constructs and use a
signed Merkle tree hash of the ciphertext itself as your own custom MAC.
>
> One benefit of using a hash-tree like algorithm with a signature is the
reduction of storage overhead and memory usage, and that you retain the
ability to independently verify each segment. Ideally you would use a
hash-tree like algorithm which also can be generated efficiently in a
single pass over even large ciphertexts with reasonable memory usage (does
anybody know of one?).
>
> Not that I've also read the referenced Tahoe-LAFS link, it looks like
they're doing something very close to what I described above, but slightly
different:
> They use AES-CTR over the whole file with a unique key, one plain hash
over the entire ciphertext, one Merkle tree hash over the ciphertext blocks
and one Merkle tree hash over the erasure coded shares of the blocks, if
I'm reading it correctly, with all three hashes stored in plaintext with
the shares and then hashed together (also including the length of the
file). They also have some sort of hash chain, but the graphics don't load
and I can't figure out how exactly it is applied, beyond potentially having
to do with confirming the order of blocks. Instead of using HMAC they use
double SHA256 in a particular format.
>
> Minus the erasure coding** and with an added signature of the file
hashes/header, that's almost exactly what I imagined, I'm just worried
about the risk of the performance penalty limiting adoption. If the
performance of this method is considered acceptable or can be improved to
an acceptable level, I definitely support using it.
>
> * A bit off topic here, but for FDE I imagine changing the encryption key
every write-session using a KDF and session counter, keeping an
authenticated encrypted list of which segments uses which session write
keys. This way you prevent partial ciphertext reversal and prevent
detection of when ciphertext segments repeat over time (re-zeroized or
restored files). You can also arbitrarily re-encrypt random segments to
obscure your real write patterns (and reduce the list size occasionally by
purging unused keys after re-encrypting the last segments using them).
>
> ** In Tahoe-LAFS, erasure coding of blocks is used to allow you to split
files across storage nodes with minimal risk of data loss. That's not
applicable here, as it can be applied independently when considered
necessary.
>
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Fri, 30 Oct 2015 23:11:23 +0900

> signature verification is used for large public messages already: no

OK, i am worried that i might have sidetracked the dicsussion with this
side-note here.  We don't have a solution for (b) above today, and as
Watson notes, there are use patterns that suggest people might be OK
with doing two-pass signature verification before processing large
files.

So i'd like to ask folks to put this side-note aside, please, and try to

  --dkg

---

From: Watson Ladd <[email-masked]>
Date: Fri, 30 Oct 2015 10:46:46 -0400

>> specific risks to be aware of?

In AES-GCM the nonce is 96 bits. (Yes, I know it admits any length
nonces, but there is a weakness due to Iwata-Ohashi-Minematsu for any
length not 96 bits). Reserving 64 bits for the chunk counter leaves 32
bits. Each chunk can be a maximum of 2^12 or so blocks, due to the
absence of a beyond-birthday bound security result. (Maybe there is
one, I don't know it, and I suspect there isn't for confidentiality).

ChaCha20 supports more blocks in each chunk, due to PRF, not PRP.
Therefore we can get by with fewer chunks and a larger nonce, thus
enabling random selection of the nonces even after reserving chunk
counters. Of course chunk sizes are limited by the desire to minimize
working memory more than the associated counters, so this might not be
possible.

Of course there is a way to finesse the entire issue: use hashing to
turn a longer nonce into a (key, nonce) pair ala XSalsa20. Sadly the
utility of such designs wasn't appreciated by people involved in the
choice of ChaCha20+Poly1305, instead of XSalsa20+Poly1305.

-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.

---

From: [email-masked]
Date: Fri, 30 Oct 2015 11:47:44 -0400

=====

Maybe sign the encrypted data.
i.e.  
an armored signed PGP message, where the plaintext is the already
encrypted armored text.
vedaal

---

From: Zooko Wilcox-OHearn <[email-masked]>
Date: Sun, 1 Nov 2015 00:48:04 +0000

Hi folks:

I'm one of the designers of Tahoe-LAFS.

First of all, I'd like to agree that this is an important issue — we
do need a data integrity protocol with which a reader can verify a
subset of the data. This is especially useful for heads — leading
bytes — of the data, so that when someone executes a command like
this:

curl http://foo.info/x.tar.pgp | gpg --decrypt | tar x

the "gpg" process can operate with limited RAM/storage and can also be
sure that any data it passes to the tar process is authentic, before
it passes that data to the tar process.

In addition, some techniques can also allow authenticated reads of
arbitrary spans of the data. The Merkle Tree approach, such as is used
in Tahoe-LAFS, allows this. Therefore if you're reading a file from
Tahoe-LAFS then if you do something like "fseek(filehandle,
1000000000, 0); fread(buf, 1, 1000000, filehandle);" then you'll get
the one million bytes of data which begins one billion bytes into the
file, but you'll get the assurance from Tahoe-LAFS that those one
million bytes are cryptographically authenticated.

Second, I'd like to emphasize something that dkg pointed out in the
first post — that even if we do this correctly at this layer, then
there is still a risk of truncation attacks. For example, imagine that
someone runs:

curl http://foo.info/x.sh.pgp | gpg --decrypt | sh

Even if gpg can ensure cryptographic integrity of every byte before it
passes that byte to sh, this is vulnerable to potentially damaging
attacks by interrupting the flow of ciphertext to gpg. This is a
problem that can't be solved by the gpg process in this example. It
has to be solved by the next process in the chain — tar in the first
example or sh in the second. But let's remember that it is a real
problem.

>     least up until truncation, if (a) can't be resolved)?

This is a big deal, and an under-appreciated one. A lot of modern
cryptography was developed in the model of a bilateral and synchronous
connection between two parties. In that model, this isn't a problem.
You have a shared secret, and anything that you receive that *you*
didn't send you can assume that the other party sent. (So you have to
prevent replay and reflection attacks, but if you've done so, then
this isn't a problem.)

But in a more asynchronous/persistent model, and in a model with more
than two parties, then you can't rely on that and you need something
else.

The way we do this in Tahoe-LAFS (like Taylor Campbell explained in
this thread), is that the writer generates a Merkle Tree over the data
and transmits, along with each block, the Merkle Branch needed to
authenticate that block.

Now the reason we do it that way in Tahoe-LAFS is that we want to bind
all the bytes of (one version of) the file together. If a reader reads
the first million bytes of a file, and then reads the second million
bytes of the file, you don't want an attacker to have the option of
supplying the first million from one version of the file and the next
million from a different version of the file, without the reader
realizing this, even if both versions of the file were, at some point,
signed by the legitimate writer.

So using the Merkle Tree provides a convenient way to:

* bundle all the bytes of the file into a single crypto value (the
Merkle Tree root) which we can then use as a "stand-in" for the
complete contents of a single version of the file, for authentication
purposes

* suffer low worst-case overhead for a read of an arbitrary span of
data (i.e., if you're reading a random span out of the middle of a
file, not just reading from the beginning)

But, we made that decision back before we were willing to rely on ECC,
so our public key digital signatures were big old 2048-bit RSA sigs.
Now that we would be willing to rely on svelte Ed25519 sigs, we might
consider including a pkdigsig with each block instead of a Merkle
Branch with each block. It would require careful engineering about the
identification and versioning of the file, either way.

Regards,

Zooko