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

Bryan Ford <> Sat, 07 November 2015 07:19 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id DA3D01B2BC0 for <>; Fri, 6 Nov 2015 23:19:27 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.999
X-Spam-Status: No, score=-1.999 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, HTML_MESSAGE=0.001, SPF_PASS=-0.001] autolearn=unavailable
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id ubThPA_lWoZe for <>; Fri, 6 Nov 2015 23:19:25 -0800 (PST)
Received: from ( [IPv6:2607:f8b0:400e:c03::22e]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 6A2691B2BBF for <>; Fri, 6 Nov 2015 23:19:25 -0800 (PST)
Received: by pacdm15 with SMTP id dm15so120874576pac.3 for <>; Fri, 06 Nov 2015 23:19:25 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20120113; h=content-type:mime-version:subject:from:in-reply-to:date:cc :message-id:references:to; bh=HGFUjSK9NCc5Aa4yAheTqHiQS29ajPSGyTc6qkqW758=; b=xNFYu71mzT3E73fxlEMExhI12+YutTGNvz3eHRmewQyNvmbkY/x7ckR8cn78dG3j97 zqbFX3x8ToT1IBcRUqtDKBcu2RGRRmmUiSYLmm/z1YqEnjMJFPUfYnz+sntke1LtkDsu 9qt4uepHxbst8hwiEEND9w3k8Zgt0yQi3cvDZiU39M/yVZtT7tf2z49MgyW5JF8cwtYD GQV70ZysyeKSkY3TVmHzzIHv5mk61Tknofy+1SKBdIHeEovEdx7jreT3QWQ5LoRzn/Gg XGIS84sVt1yNPlmMCDtUshmW8JAcURHLgoUe931yo0da3kRKMWsfO3y7+c8jHRuf+kw9 jnuA==
X-Received: by with SMTP id ex11mr23656196pad.126.1446880765004; Fri, 06 Nov 2015 23:19:25 -0800 (PST)
Received: from [] ( []) by with ESMTPSA id rm10sm3334560pbc.96.2015. (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Fri, 06 Nov 2015 23:19:23 -0800 (PST)
Content-Type: multipart/signed; boundary="Apple-Mail=_00EB7649-793A-42AD-B008-E1C26609DC92"; protocol="application/pkcs7-signature"; micalg=sha1
Mime-Version: 1.0 (Mac OS X Mail 8.2 \(2104\))
From: Bryan Ford <>
In-Reply-To: <>
Date: Sat, 7 Nov 2015 16:19:21 +0900
Message-Id: <>
References: <> <> <> <>
To: Andy Lutomirski <>
X-Mailer: Apple Mail (2.2104)
Archived-At: <>
Cc:, "" <>
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: Sat, 07 Nov 2015 07:19:28 -0000

On Nov 7, 2015, at 10:54 AM, Andy Lutomirski <>; wrote:
> On Fri, Nov 6, 2015 at 5:46 PM, Bryan Ford < <>> wrote:
>> 1. How important is the ability to achieve goal #1 above in the OpenPGP
>> format (streaming-mode integrity-checking)?
> Are you willing to accept a format that allows streaming decryption
> but not streaming encryption?  If so, then you'd only need one
> signature if you organize your Merkle tree correctly.  In fact:

That’s certainly one reasonable use-case to consider, but I don’t think it fully satisfies the “filter-mode encrypted backup” scenario that DKG originally brought up.  If I’m encrypting and streaming my huge backups to a huge network connection, then I don’t want the encryption side to have to store the whole huge backup tarball locally either.  My intuition is that if the "filter-mode streaming backup” scenario is important on either the encryption or decryption side, then it’s probably important to be able to handle on both sides.

On the other hand, it might be quite reasonable to define an encrypted message format that allows either mode of operation, and have the encryptor choose the mode of operation automatically depending on the situation.  If the encryptor sees that both its input and its output are regular files, i.e., it knows the total length of its input and can seek in its output, then the encryptor could (as you suggest) leave room for a signed Merkle tree at the beginning, process everything, then go back to the beginning and fill in the Merkle tree and the signature on its root.  Then a streaming-mode decryptor would get the signed Merkle tree first and subsequently be able to integrity-check all subsequent chunks independently.  However, if the encryptor finds that either it doesn’t know the length of its input in advance, or has been told to send output to a non-seekable stream (e.g., over an SSH-forwarded network pipe), then the encryptor might have to fall back to a more incremental approach, with signatures (or signature-plus-incremental-Merkle-trees) after each chunk.

>> 2. How important is the ability to achieve goal #2 above in the OpenPGP
>> format (random-access integrity-checking)?
> It's fairly easy to imagine a format that allows both streaming
> verification and random-access verification with minimal size
> overhead.  You could even create the thing in a semi-streamy manner,
> where you'd stream out the bulk portion with blanks where the internal
> nodes go and then write the internal nodes after the fact.
> The best of all worlds might be to treat the Merkle data and the
> signature as a detached file.  I bet that one could streamily encrypt
> and sign a big file and produce *two* output streams: the bulk data
> and a detached serialization of intermediate nodes, where there's a
> single signature at the end.  A reader with access to both files could
> random-access it or seek the detached signature a bit and then stream
> the bulk file.

I think detached files sound convenient to implementers but prove troublesome to users who need to know how to juggle and keep track of two files where before they only need to keep track of one. :)


> --Andy