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

Peter Todd <pete@petertodd.org> Tue, 03 November 2015 00:43 UTC

Return-Path: <pete@petertodd.org>
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 52C311AC3E5; Mon, 2 Nov 2015 16:43:44 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.601
X-Spam-Level:
X-Spam-Status: No, score=-2.601 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001] autolearn=ham
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 iGTCw4aqiQ9Q; Mon, 2 Nov 2015 16:43:42 -0800 (PST)
Received: from outmail149077.authsmtp.com (outmail149077.authsmtp.com [62.13.149.77]) by ietfa.amsl.com (Postfix) with ESMTP id 961BA1AC3E3; Mon, 2 Nov 2015 16:43:41 -0800 (PST)
Received: from mail-c247.authsmtp.com (mail-c247.authsmtp.com [62.13.128.247]) by punt21.authsmtp.com (8.14.2/8.14.2/) with ESMTP id tA30hccV094672; Tue, 3 Nov 2015 00:43:38 GMT
Received: from muck ([50.58.157.74]) (authenticated bits=128) by mail.authsmtp.com (8.14.2/8.14.2/) with ESMTP id tA30hVms012349 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NO); Tue, 3 Nov 2015 00:43:34 GMT
Date: Mon, 2 Nov 2015 19:43:31 -0500
From: Peter Todd <pete@petertodd.org>
To: Andy Lutomirski <luto@amacapital.net>
Message-ID: <20151103004331.GA20311@muck>
References: <87twp91d8r.fsf@alice.fifthhorseman.net> <20151030183223.35630603F0@jupiter.mumble.net> <CALCETrULywQ-14gjnEgcbtO3zJoK5PhbiE953eZXO+r108eFHg@mail.gmail.com>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="cWoXeonUoKmBZSoM"
Content-Disposition: inline
In-Reply-To: <CALCETrULywQ-14gjnEgcbtO3zJoK5PhbiE953eZXO+r108eFHg@mail.gmail.com>
X-Server-Quench: ea968870-81c3-11e5-bcde-0015176ca198
X-AuthReport-Spam: If SPAM / abuse - report it at: http://www.authsmtp.com/abuse
X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVKBZePFsRUQkR bwdMdgEUFloCAgsB AmMbW1ReVF57WmY7 bgpPaA1DY09JQQJu T01BRU1TWkEZAhxZ YENdUhhwdAFPNn94 Zk9iECUKVUJyfUF9 X0ZVRm4bZGY1bX1N AxQNagNUcQZLeRkW O1F2XD1vNG8XDSUg EgkrMCgEdQZ0Jj5a d0kWMUgfSEMCFDox DzkvNBlnFkoDXDkp Mhc6YlAbBg4KLkIo PFdpVVsEOkh6
X-Authentic-SMTP: 61633532353630.1038:706
X-AuthFastPath: 0 (Was 255)
X-AuthSMTP-Origin: 50.58.157.74/587
X-AuthVirus-Status: No virus detected - but ensure you scan with your own anti-virus system.
Archived-At: <http://mailarchive.ietf.org/arch/msg/openpgp/PmYrOkFmX55JJwLnevlM-6kSGoU>
Cc: openpgp@ietf.org, "cfrg@irtf.org" <cfrg@irtf.org>, Daniel Kahn Gillmor <dkg@fifthhorseman.net>, Taylor R Campbell <campbell+cfrg@mumble.net>
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: Tue, 03 Nov 2015 00:43:44 -0000

On Fri, Oct 30, 2015 at 11:47:42AM -0700, Andy Lutomirski wrote:
> On Fri, Oct 30, 2015 at 11:32 AM, Taylor R Campbell
> <campbell+cfrg@mumble.net>; 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.

I wasn't aware of Sakura previously; it does seem very complex which I'm
sure is holding it back.

I had a need for a merkle tree over a list of items with the ability to
efficiency prove the (relative) position of items committed to in the
tree, as well as strict determinism. (for every message there is only
one valid digest) I came up a fairly simple scheme that I'm calling
merkle-mountain-ranges:

https://github.com/proofchains/python-proofmarshal/blob/master/proofmarshal/mmr.py

While I didn't write the above with hashing byte strings in mind, by
specifying a block size it could be easily modified to do so. (though be
careful you don't lose the determinism!)

-- 
'peter'[:-1]@petertodd.org
00000000000000000de6dfa01305b9163ad2efd9f72c77c23ebddf62afc18b00