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

Andy Lutomirski <> Fri, 30 October 2015 18:48 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id C9EDD1B30D2 for <>; Fri, 30 Oct 2015 11:48:07 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.279
X-Spam-Status: No, score=-1.279 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, FM_FORGED_GMAIL=0.622, SPF_PASS=-0.001] autolearn=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id Cl9TIlAXMGIG for <>; Fri, 30 Oct 2015 11:48:06 -0700 (PDT)
Received: from ( [IPv6:2607:f8b0:4003:c06::22b]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 7EBAB1B30D1 for <>; Fri, 30 Oct 2015 11:48:02 -0700 (PDT)
Received: by oiad129 with SMTP id d129so64593055oia.0 for <>; Fri, 30 Oct 2015 11:48:01 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20150623; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type; bh=Zkqh4v+uLnsUeESbRQFeyvoFdD8c++44GkfyRRKsoaI=; b=tCl/8XT5VE9A9gKteLMw78VHY3NshbhuglO/8tOC1m2vwS6cJcoxUbttI/fK3T638v 2yYKbr5MtJOGq9tXZ0KSLMVvQsFrFRfDYES94EEQSgGM0BQziW7ojRvhnPzaBpR4xPl9 qKzLSO3F6su5YXtl/LEAWh7z8USw0xf27Ys9WWYjxEbHhyxHP5/lUaRni09z+U55SQBY 0gIVP37WxFZX17sVQ1GQ0RZbiD4owtrHjMVwP2lUrGfTbPAI4h9XUXD+Wx5g+CPmulDJ +s50++n/RwujlVq7KsnezkcFivehV2fmTpZ0EpQTTvK1vIacN/wDe+MpkYTIUocvcPRc 0XmQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc:content-type; bh=Zkqh4v+uLnsUeESbRQFeyvoFdD8c++44GkfyRRKsoaI=; b=IKCELtSz6PZpO+/oIdQoxAdxeEU8iy9r2e6kebVyR4bkXt1vVtlZJojvagb1Ff7TpC KECaH7PA/S/1am/MuuzZYavryOxEV6RLbUMYqFfxlfcVBtRM6YsyOsGdTU7X3kVGM5zz OSUEUoPGEJWvGRKRbjMNK8Edde3qhdi3r+tPARMdJk0jsToitWZtY6xv9flvm1Q3GKjn VmjLp0xf7bYbXjwLGQgZBroJg2y3HArVptmVCXFzRNjPbz7kOVWDF5rJnpwO0C4gq0rl 2kdAO5J0PA+uNMF2I0Gtd4HyUShTH+WGEG8Q0jNqhxTPoMWOUJJMv+1iJVwngHnjDo1v vAdA==
X-Gm-Message-State: ALoCoQkrnswS9v0R5xqvbqpSyxPfDv1GeBV/3YWK1GMk7a5w5i5yAof+bMaf7zYVnucKqKqoDUkS
X-Received: by with SMTP id c130mr6651942oia.116.1446230881711; Fri, 30 Oct 2015 11:48:01 -0700 (PDT)
MIME-Version: 1.0
Received: by with HTTP; Fri, 30 Oct 2015 11:47:42 -0700 (PDT)
In-Reply-To: <>
References: <> <>
From: Andy Lutomirski <>
Date: Fri, 30 Oct 2015 11:47:42 -0700
Message-ID: <>
To: Taylor R Campbell <>
Content-Type: text/plain; charset=UTF-8
Archived-At: <>
X-Mailman-Approved-At: Sun, 01 Nov 2015 07:51:57 -0800
Cc:, "" <>, Daniel Kahn Gillmor <>
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 18:48:08 -0000

On Fri, Oct 30, 2015 at 11:32 AM, Taylor R Campbell
<>; wrote:
> This requires only O(log n) working memory to compute the Merkle tree
> -- it takes a single pass over the whole input.
...which reminds me:

As far as I know, everyone thinks they know how to do a Merkle tree
for things like this, but there doesn't seem to be a credible
standard, and there are at least two modern examples of doing it
wrong: Amazon's Glacier hash and (unless it changed) Bittorrent's new
Merkle tree.

Should CFRG consider standardizing a transport format for hash tree
verifiers (or proofs or whatever they're called) and for a large blob
that can be used to efficiently generate the proofs (essentially some
kind of serialized tree)?  The Sakura construction could be a good
starting point.  If I were designing such a standard, I would be
extremely hesitant to start with SHA256 or similar because of the lack
of personalization, whereas Sakura (and maybe BLAKE2) doesn't have
this problem.

Sadly, Sakura doesn't seem to be officially blessed yet.