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

[Andrey Jivsov <[e-mail]>]

On 10/30/2015 07:46 AM, Watson Ladd wrote:
> 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).

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