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

Watson Ladd <> Fri, 30 October 2015 14:46 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 57B6E1A6F6E for <>; Fri, 30 Oct 2015 07:46:50 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Status: No, score=-2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, SPF_PASS=-0.001] autolearn=unavailable
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id 73IFS79Ru5ZY for <>; Fri, 30 Oct 2015 07:46:48 -0700 (PDT)
Received: from ( [IPv6:2a00:1450:400c:c05::236]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 9313C1A6F63 for <>; Fri, 30 Oct 2015 07:46:47 -0700 (PDT)
Received: by wicll6 with SMTP id ll6so12220380wic.1 for <>; Fri, 30 Oct 2015 07:46:46 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=qsuhNHjCSvw7Qjsl2282demS53vTT3h/Get7FFvZEEc=; b=yfocB8SfZnd/Dvu6T/a6ffNmTC0mrigrCBS0yc7Vz6ivuNQ5EXHZ/fXlRkK0xPX2Yr +HsJcXeQ1hZY7RPqDMMqnLp3KR8Oulq3CapZk0JABiYli8ZCTOPjqUKr/p/gNkFY+0Qm EXQw9DF1CIhSkfVmAoPhWN1FPvDG7giF1X1Q5K0oA6qGkuaZoVevtep5SR+oxAKyF0z5 1+FoL7LiXATtvyiKW6u1vr8ANg/t8YXFhY0MtfECk6+Z3kFmrlf9GDuC2R7r+JhB0i+O Wb26ClTdR47A9o5Kcp5ELWyX7jMEYsL38bBR3B9AGhedgKDrqUH6Pid3hzhc3Ke708Jm 4l9Q==
MIME-Version: 1.0
X-Received: by with SMTP id r14mr10594976wjq.37.1446216406087; Fri, 30 Oct 2015 07:46:46 -0700 (PDT)
Received: by with HTTP; Fri, 30 Oct 2015 07:46:46 -0700 (PDT)
In-Reply-To: <>
References: <> <> <> <>
Date: Fri, 30 Oct 2015 10:46:46 -0400
Message-ID: <>
From: Watson Ladd <>
To: Daniel Kahn Gillmor <>
Content-Type: text/plain; charset=UTF-8
Archived-At: <>
Cc: IETF OpenPGP <>, "" <>, Natanael <>
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: Fri, 30 Oct 2015 14:46:50 -0000

On Fri, Oct 30, 2015 at 10:11 AM, Daniel Kahn Gillmor
<> wrote:
> On Fri 2015-10-30 21:30:44 +0900, Watson Ladd wrote:
>>> >  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.
>> Use authenticated encryption so no signatures are required. Detached
>> signature verification is used for large public messages already: no
>> streaming needed.
> 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
> re-focus on the main original question:
>> AGL describes this problem here:
>> 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:
>> 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?

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

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.

>   --dkg

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