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

Taylor R Campbell <campbell+cfrg@mumble.net> Fri, 30 October 2015 18:32 UTC

Return-Path: <campbell@mumble.net>
X-Original-To: openpgp@ietfa.amsl.com
Delivered-To: openpgp@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id B01FB1B302C for <openpgp@ietfa.amsl.com>; Fri, 30 Oct 2015 11:32:37 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.61
X-Spam-Level:
X-Spam-Status: No, score=-2.61 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_LOW=-0.7, T_RP_MATCHES_RCVD=-0.01] autolearn=unavailable
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id QsJdtiDIuI9I for <openpgp@ietfa.amsl.com>; Fri, 30 Oct 2015 11:32:31 -0700 (PDT)
Received: from jupiter.mumble.net (jupiter.mumble.net [74.50.56.165]) by ietfa.amsl.com (Postfix) with ESMTP id 523111B3023 for <openpgp@ietf.org>; Fri, 30 Oct 2015 11:32:31 -0700 (PDT)
Received: by jupiter.mumble.net (Postfix, from userid 1014) id 35630603F0; Fri, 30 Oct 2015 18:32:23 +0000 (UTC)
From: Taylor R Campbell <campbell+cfrg@mumble.net>
To: Daniel Kahn Gillmor <dkg@fifthhorseman.net>
In-reply-to: <87twp91d8r.fsf@alice.fifthhorseman.net> (dkg@fifthhorseman.net)
Date: Fri, 30 Oct 2015 18:32:30 +0000
Sender: Taylor R Campbell <campbell@mumble.net>
User-Agent: IMAIL/1.21; Edwin/3.116; MIT-Scheme/9.1.99
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Message-Id: <20151030183223.35630603F0@jupiter.mumble.net>
Archived-At: <http://mailarchive.ietf.org/arch/msg/openpgp/nJKTcC61EKHQmaDxa8C9-a2aOcU>
X-Mailman-Approved-At: Sun, 01 Nov 2015 07:51:55 -0800
Cc: openpgp@ietf.org, cfrg@irtf.org
Subject: Re: [openpgp] [Cfrg] streamable AEAD construct for stored data?
X-BeenThere: openpgp@ietf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: "Ongoing discussion of OpenPGP issues." <openpgp.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/openpgp>, <mailto:openpgp-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/openpgp/>
List-Post: <mailto:openpgp@ietf.org>
List-Help: <mailto:openpgp-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/openpgp>, <mailto:openpgp-request@ietf.org?subject=subscribe>
X-List-Received-Date: Fri, 30 Oct 2015 18:32:37 -0000

   Date: Fri, 30 Oct 2015 08:11:48 +0900
   From: Daniel Kahn Gillmor <dkg@fifthhorseman.net>;

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

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.