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

Peter Todd <pete@petertodd.org> Mon, 02 November 2015 23:25 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 4F3101A9057 for <openpgp@ietfa.amsl.com>; Mon, 2 Nov 2015 15:25:14 -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 qkuEtWV746Bb for <openpgp@ietfa.amsl.com>; Mon, 2 Nov 2015 15:25:13 -0800 (PST)
Received: from outmail149112.authsmtp.co.uk (outmail149112.authsmtp.co.uk [62.13.149.112]) by ietfa.amsl.com (Postfix) with ESMTP id 9C17C1A904E for <openpgp@ietf.org>; Mon, 2 Nov 2015 15:25:12 -0800 (PST)
Received: from mail-c247.authsmtp.com (mail-c247.authsmtp.com [62.13.128.247]) by punt22.authsmtp.com (8.14.2/8.14.2/) with ESMTP id tA2NPABN096064; Mon, 2 Nov 2015 23:25:10 GMT
Received: from muck ([50.58.157.74]) (authenticated bits=128) by mail.authsmtp.com (8.14.2/8.14.2/) with ESMTP id tA2NP37h027617 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NO); Mon, 2 Nov 2015 23:25:07 GMT
Date: Mon, 2 Nov 2015 18:25:02 -0500
From: Peter Todd <pete@petertodd.org>
To: Andy Lutomirski <luto@amacapital.net>
Message-ID: <20151102232502.GA20756@muck>
References: <87twp91d8r.fsf@alice.fifthhorseman.net> <20151030183223.35630603F0@jupiter.mumble.net> <CALCETrULywQ-14gjnEgcbtO3zJoK5PhbiE953eZXO+r108eFHg@mail.gmail.com> <CAMfhd9XE_v5ngzfq0g9dGdjKRp82-GxZwMNLoCYeUr6ZcvOjJw@mail.gmail.com> <CALCETrWuw9s5QP_pQArwG+Ykf4nbq_NxzdGpQSfDzrEaRE-Q2g@mail.gmail.com>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="T4sUOijqQbZv57TR"
Content-Disposition: inline
In-Reply-To: <CALCETrWuw9s5QP_pQArwG+Ykf4nbq_NxzdGpQSfDzrEaRE-Q2g@mail.gmail.com>
X-Server-Quench: f4c3b15a-81b8-11e5-bcde-0015176ca198
X-AuthReport-Spam: If SPAM / abuse - report it at: http://www.authsmtp.com/abuse
X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVKBZePFsRUQkR bwdMdgAUFloCAgsB AmMbWVdeUlh7WWs7 bgpPaA1DY09JQQJu T01BRU1TWkEZA2Jh BRlGUht1cQRBNn91 Z0dnECZfD0codEMs X0ZVR2UbZGY1bX1N 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/n-gv9J9NMqyTq1Rw7DbNGjO3Nyo>
Cc: Adam Langley <agl@imperialviolet.org>, openpgp@ietf.org, "cfrg@irtf.org" <cfrg@irtf.org>, 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: Mon, 02 Nov 2015 23:25:14 -0000

On Fri, Oct 30, 2015 at 03:09:19PM -0700, Andy Lutomirski wrote:
> No, but here goes:
> 
> Amazon does this:
> 
> http://docs.aws.amazon.com/amazonglacier/latest/dev/checksum-calculations.html
> 
> Take 1MB chunks (and a possible short trailing chunk).  Hash them with
> SHA256.  Then, as long as you have more than one hash in your array,
> hash pairs of hashes together and just keep the extra odd one at the
> end, if any.  This reduces the number of hashes from n to ceil(n/2).
> When you have exactly one hash left, you're done.
> 
> This is vulnerable to a trivial second-preimage attack.  Fortunately,
> it seems to be okay if you also store the length of the data along
> with the hash value.

Mind explaining in a bit more detail what exactly you think this attack
is? Bitcoin did have an attack on a similar implementation, but with the
critical difference that in Bitcoin rather than moving the odd block up
to the "next level" it was duplicated:

https://github.com/bitcoin/bitcoin/blob/d22701118413b876579c020ea90ecf7a0d5671cb/src/primitives/block.cpp#L17

-- 
'peter'[:-1]@petertodd.org
00000000000000001082036bc5c78a25a50b85744159b260e5136771a5611715