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

Andrey Jivsov <> Sun, 01 November 2015 02:10 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id C0B331B5050 for <>; Sat, 31 Oct 2015 19:10:52 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.9
X-Spam-Status: No, score=-1.9 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HTML_MESSAGE=0.001, SPF_PASS=-0.001] autolearn=ham
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id FiQCUUISjAHG for <>; Sat, 31 Oct 2015 19:10:44 -0700 (PDT)
Received: from ( [IPv6:2001:558:fe16:19:96:114:154:164]) (using TLSv1.2 with cipher DHE-RSA-AES128-SHA (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id CF9C71B504B for <>; Sat, 31 Oct 2015 19:10:43 -0700 (PDT)
Received: from ([]) by with comcast id c2A81r0075E3ZMc012Ajci; Sun, 01 Nov 2015 02:10:43 +0000
Received: from [] ([]) by with comcast id c2Ah1r00B0ZpzqZ012Ahv4; Sun, 01 Nov 2015 02:10:43 +0000
Message-ID: <>
Date: Sat, 31 Oct 2015 19:10:41 -0700
From: Andrey Jivsov <>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.7.0
MIME-Version: 1.0
To: Watson Ladd <>
References: <> <> <> <> <>
In-Reply-To: <>
Content-Type: multipart/alternative; boundary="------------020802080502020801030206"
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=q20140121; t=1446343843; bh=GXkySd0rhp1EN8Zj/JV34UdlR04y9KHEtNENpTclsjA=; h=Received:Received:Message-ID:Date:From:MIME-Version:To:Subject: Content-Type; b=AZl2qBhYr3WiYh7YSue5zAYgLaDiMCKe3FMuaHUtJ3u1yHC787v5jAfqlk52BJ+Qj LiG3i6fdjJ5+nJLhGubnrgbk9wntF1PTqaTQ8ZtQa/X2D8LX8Y9R2gWj+bCKwUQqo+ 0OR0pad9Hw+4GgLOJMA98sMg2F56wXWBSjrYViN8ABeSJJJobRB+OeCh8y83YEI6ps 2VX4aP0V5SMOICwKV93Xz0S/2gp1JfHkDDAT2OhKwSbkPbTAY+JRZpOzGG1Id5mDza 7iQwkfRMxqKhXaAz3ZI1Gz3ZEM1kRcRfXklQEJccocP123M2n1V3VlfMAX3gk6ELU3 hbFO6OwTiIZHA==
Archived-At: <>
X-Mailman-Approved-At: Sun, 01 Nov 2015 07:51:57 -0800
Cc: IETF OpenPGP <>, "" <>
Subject: Re: [openpgp] [Cfrg] streamable AEAD construct for stored data?
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: "Ongoing discussion of OpenPGP issues." <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Sun, 01 Nov 2015 02:10:52 -0000

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 

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