Subject: [Cfrg] 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: Natanael <[email-masked]>
Date: Fri, 30 Oct 2015 13:25:03 +0100

> decrypted data, like this:

[...]

>     they're capable of coping with truncation)

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.

To solve B what you need to do is something like signing a list of
ciphertext hashes/authentication tags.

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.

---

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

> > 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.

The idea below demands conditions beyond MAC security.

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.
>
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Natanael <[email-masked]>
Date: Fri, 30 Oct 2015 14:18:12 +0100

I'm not sure if we read the requirements differently. He asked for
immutable signed files, as in that an AEAD authentication key is
insufficient because the other recipients all have the same key and can
substitute the ciphertext. There's an explicit requirement that the
capabilities of the sender and (potentially multiple) receivers are
different.

Yes, the signature would fail if combining standard AEAD with a full
ciphertext signature and one receiver modified the ciphertext, but see the
reasoning for why it is necessary again - by the time the failure is
detected, the software that's performing the streaming decryption and
processing may already have taken some undesired action, or might fail to
cancel a future undesired action (by not deleting the resulting plaintext).
Preemptively preventing mistakes done by the client software.

It isn't just AEAD, it is seekable streaming AEAD with per-block
verification of immutability. Allowing you to look up any block
individually and confirm *that block* hasn't been modified by anybody but
the original sender.

Imagine for example an encrypted video or a large archive of files being
sent to multiple receivers. With AES-GCM and a signature at the end, you
either decrypt and verify everything before viewing or you decrypt just one
part and accept that another one of the receivers may have tampered with
your copy of the video/files (if it for example is stored on a NAS).

Or worse, the software parsing the plaintext might have an exploitable bug,
which may then already have been exploited when the signature verification
fails, so that even if the decryption software rolls back everything it did
then you now have malware on your system anyway.

The other option is of course the sender creating multiple ciphertexts with
separate keys for every recipient. Very much not ideal for large files.

> The idea below demands conditions beyond MAC security.

Feel free to explain what conditions those are. I'll happily admit I'm just
a cryptography novice, I'm willing to learn why this might be flawed or
insufficient.

---

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: Hanno Böck <[email-masked]>
Date: Fri, 30 Oct 2015 15:29:46 +0100

On Fri, 30 Oct 2015 08:11:48 +0900

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

Adam Langley also explained this problem in a talk which is worth
watching if you're interested in these issues:
https://external.global.media.yahoo.com/video/yahoo-trust-unconference-tls-adam-223046696.html?format=embed&player_autoplay=false

May be helpful for the lazy ones who like watching a video more than
reading a complicated text :-)

-- 
Hanno Böck
http://hboeck.de/

mail/jabber: [email-masked]
GPG: BBB51E42

---

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: Taylor R Campbell <[email-masked]>
Date: Fri, 30 Oct 2015 18:32:30 +0000

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

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.

---

From: Andy Lutomirski <[email-masked]>
Date: Fri, 30 Oct 2015 11:47:42 -0700

> -- it takes a single pass over the whole input.
...which reminds me:

As far as I know, everyone thinks they know how to do a Merkle tree
for things like this, but there doesn't seem to be a credible
standard, and there are at least two modern examples of doing it
wrong: Amazon's Glacier hash and (unless it changed) Bittorrent's new
Merkle tree.

Should CFRG consider standardizing a transport format for hash tree
verifiers (or proofs or whatever they're called) and for a large blob
that can be used to efficiently generate the proofs (essentially some
kind of serialized tree)?  The Sakura construction could be a good
starting point.  If I were designing such a standard, I would be
extremely hesitant to start with SHA256 or similar because of the lack
of personalization, whereas Sakura (and maybe BLAKE2) doesn't have
this problem.

Sadly, Sakura doesn't seem to be officially blessed yet.

--Andy

---

From: Adam Langley <[email-masked]>
Date: Fri, 30 Oct 2015 14:28:10 -0700

> wrong: Amazon's Glacier hash and (unless it changed) Bittorrent's new

Do you have references for either of these two issues? I wasn't aware of them.

Cheers

AGL

-- 
Adam Langley [email-masked] https://www.imperialviolet.org

---

From: Andy Lutomirski <[email-masked]>
Date: Fri, 30 Oct 2015 15:09:19 -0700

> Do you have references for either of these two issues? I wasn't aware of them.

No, but here goes:

Amazon does this:

http://docs.aws.amazon.com/amazonglacier/latest/dev/checksum-calculations.html

Take 1MB chunks (and a possible short trailing chunk).  Hash them with
SHA256.  Then, as long as you have more than one hash in your array,
hash pairs of hashes together and just keep the extra odd one at the
end, if any.  This reduces the number of hashes from n to ceil(n/2).
When you have exactly one hash left, you're done.

This is vulnerable to a trivial second-preimage attack.  Fortunately,
it seems to be okay if you also store the length of the data along
with the hash value.

I don't know what Bittorrent is actually doing, but I found this
thing:  http://www.bittorrent.org/beps/bep_0030.html  It seems
similarly broken.

--Andy

---

From: Björn Edström <[email-masked]>
Date: Sat, 31 Oct 2015 10:20:53 +0100

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

Is that constraint really set in stone?

PGP is a complicated system to use and understand for most people and
the more an implementation can do to prevent potential dangers the
better. I think it could be worthwhile of the spec to have security
guidelines for implementers to make dangerous invocations more
difficult.

To use your example, consider the following further examples:

pgp --decrypt --file backup.pgp | tar x

The above is fine. Run two passes over the file, one for integrity,
one for output.

pgp --decrypt < small-backup.pgp | tar x

The above is fine. The file is small and it fits into some predefined
buffer in memory before reaching EOF. Similar to the above: check
before outputting anything.

pgp --decrypt < backup.pgp | tar x

The above is *not* fine, and the user should have to go through hoops
to make it work (for example some kind of --unsafe option, or big
warning pop up box in a GUI application).

In general I think the OpenPGP spec should have more guidelines for
implementors since it's very easy for the user to screw up if the user
is not familiar with intricate details of the system. This is to a
greater extent than other specs, that mostly concern specialists
anyway.

Removing the constraint above, and living in the normal world where
you do 1 pass integrity before decrypting, you can use much more
boring and standard cryptographic constructs, which I personally would
prefer in this case.

Cheers
Björn

---

From: Taylor R Campbell <[email-masked]>
Date: Sat, 31 Oct 2015 19:36:26 +0000

Date: Fri, 30 Oct 2015 14:28:10 -0700
   From: Adam Langley <[email-masked]>

The naive approach of computing

Naive-Merkle-SHA256(a || b) = SHA256(SHA256(a) || SHA256(b))

lends itself to the trivial second-preimage attack

Naive-Merkle-SHA256(a || b) = Naive-Merkle-SHA256(SHA256(a) || SHA256(b))

provided the leaves are >=64 bytes so that SHA256(a) || SHA256(b)
makes up a single leaf.  Both the Amazon Glacier and the BitTorrent
Merkle trees that Andy cited use this naive approach.

Sakura and Blake2's family of Merkle tree constructions, which tweak
the underlying hash function for each distinct depth, offset, tree
fanout, and other parameters, are adequate for the purposes of signing
a monolithic document, as dkg was originally asking for, but are a
little unsatisfying for other applications, such as deduplicated
storage.

In particular, for deduplication, in order to store a || c as well as
a || b || c.  we would like the Merkle tree of the first object to be
a function of H(a) and H(c), and that of the second object to be a
function of H(a), H(b), and H(c), for a fixed hash function H.

But Sakura and Blake2 both use a different function for each internal
and leaf node, indicating its depth and its offset from the start of
the message -- which works for fixed-width edits to a disk image, as
the Blake2 specification suggests, but breaks down in the case of
insertions or deletions.

Tahoe-LAFS uses a different function for internal nodes vs leaves, but
otherwise no differences (e.g., no difference between height-1 and
height-2 internal nodes), by prepending a tag to the input of SHA256d:
x |---> SHA256(SHA256(x)).  In particular, it is something like:

Tahoe-Merkle(a || b) =
    SHA256d('internal' || SHA256d('leaf' || a) || SHA256d('leaf' || a))

This avoids the trivial second-preimage attack, enables deduplication,
and allows receivers to incrementally verify paths from a signed root
to leaves.  (SHA256d avoids concerns with standard Merkle-Damgard
length-extension attacks.)  But I'm not aware of any formal analysis
of this construction.

---

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

---

From: Andrey Jivsov <[email-masked]>
Date: Sat, 31 Oct 2015 19:10:41 -0700

> one, I don't know it, and I suspect there isn't for confidentiality).

Such a generic claim about "absence of a beyond-birthday bound 
security", is unfortunately not true for AES-GCM.

David Mcgrew pointed out his eprint paper, which I will distill here 
into a practical attack on the current TLS 1.3 privacy feature. The 
feature in question intends to hide the size of the TLS record 
(https://tools.ietf.org/html/draft-ietf-tls-tls13-10#section-5.2.3)

The feature is broken in the very use case the feature was intended to 
defend against:
- passive monitoring, including analysis of previously recorded traffic
- the size of the protected (real) plaintext is revealed, and not just 
the the fact that the padding was used.

The only challenge in this attack is the need to accumulate on the order 
of 2^64 16 byte blocks for a probability 1/2 statements, but this will 
be less, accordingly, for lower probability, and actually we will see 
that this even less due to the design of the feature. However this 
storage requirement is a common property of birthday boundary attacks.

To remind, the TLS 1.3 padding pads the plaintext record at the end with 
Z=0^128 blocks.

The key property that enables the attack is that encryption of Z will 
produce a block that is unique so far for the given stream.

Let's see in details how this is exploited.

- accumulate all 16-byte ciphertext blocks in the TLS session, building 
the table T with all seen 16-byte C_i.
- Once the table has near 2^64 unique entries, we are setup to break the 
padding
- For a new TLS record, iterating from the last_index-x 16-byte block: 
If the block is unique, this is likely C_j = AES-GCM(Z). Iterating up, 
we stop when we have a collision with an entry in T. On collision, we 
know that C_j wasn't an encrypted Z.

Note that the property of multiple Z at the end amplifies this attack 
(not discussed further here). This means that we will need much less 
than 2^64 blocks for 1/2 probability.

( x here is to adjust for the fact that the very last block won't be Z 
due to fixed metadata. This shouldn't be a problem in practice. )

( One possible fix is to use random/pseudorandom data instead of Z. 
Another is to limit the number of records sent, currently 2^64, which is 
too high in this attack).

( It's true, however,  that AES-GCM seems to go farther than AES-CBC or 
AES-CFB in its defense against outright decryption of plaintext. )