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

Peter Todd <pete@petertodd.org> Tue, 03 November 2015 00:12 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 417A11A9238 for <openpgp@ietfa.amsl.com>; Mon, 2 Nov 2015 16:12:52 -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 l68AX2Eqet-m for <openpgp@ietfa.amsl.com>; Mon, 2 Nov 2015 16:12:49 -0800 (PST)
Received: from outmail148095.authsmtp.com (outmail148095.authsmtp.com [62.13.148.95]) by ietfa.amsl.com (Postfix) with ESMTP id 4643C1A923D for <openpgp@ietf.org>; Mon, 2 Nov 2015 16:12:49 -0800 (PST)
Received: from mail-c232.authsmtp.com (mail-c232.authsmtp.com [62.13.128.232]) by punt23.authsmtp.com (8.14.2/8.14.2/) with ESMTP id tA30Cls9034221; Tue, 3 Nov 2015 00:12:47 GMT
Received: from muck ([50.58.157.74]) (authenticated bits=128) by mail.authsmtp.com (8.14.2/8.14.2/) with ESMTP id tA30CeOk071600 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NO); Tue, 3 Nov 2015 00:12:44 GMT
Date: Mon, 2 Nov 2015 19:12:40 -0500
From: Peter Todd <pete@petertodd.org>
To: Andy Lutomirski <luto@amacapital.net>
Message-ID: <20151103001239.GA1313@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> <20151102232502.GA20756@muck> <CALCETrVMcSy41Hiz+WUcdZ2fUGouV8hNmax+OUpG41iuFPgoVg@mail.gmail.com>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="0F1p//8PRICkK4MW"
Content-Disposition: inline
In-Reply-To: <CALCETrVMcSy41Hiz+WUcdZ2fUGouV8hNmax+OUpG41iuFPgoVg@mail.gmail.com>
X-Server-Quench: 9c0c5960-81bf-11e5-829e-00151795d556
X-AuthReport-Spam: If SPAM / abuse - report it at: http://www.authsmtp.com/abuse
X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVKBZePFsRUQkR bwdMdgEUFloCAgsB AmMbW1ReUV97XWU7 bgpPaA1DY09JQQJu T01BRU1TWkEZAhxy U2FFUh5zcQVGNn93 Y0BnEHkIXBd/fEB9 X0ZVRzsbZGY1bX0X UkkNagNUcQZLeRZA PlV6Uj1vNG8XDSUg EgkrMCgEdQZ0Jj5a d0kWMUgfSEMCFDox DzkvNBlnFkoDXDkp Mhc6YlAbBg4KLkIo PFdpVVsEOkh6
X-Authentic-SMTP: 61633532353630.1037: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/XAVjPQZVsWc9Ac0YH7phmUDJh3M>
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: Tue, 03 Nov 2015 00:12:52 -0000

On Mon, Nov 02, 2015 at 03:44:43PM -0800, Andy Lutomirski wrote:
> > 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:
> >
> 
> In the simple case, take any long input that's a power of two blocks
> long.  Calculate its Amazon-style hash tree root value.  While
> calculating it, remember the top two non-root internal node hash
> values.  Concatenate them and compute the Amazon-style hash tree root
> for *that*.  You'll get exactly the same hash tree root.
> 
> This violates both the collision resistance and second-preimage
> resistance properties of hash functions, so the Amazon hash tree
> construction is not a cryptographically secure hash function.
> 
> This attack isn't just theoretical.  It means that, for any given big
> file you archive in Glacier, there exists an incorrect and easy to
> construct file that could be substituted and would pass a hash
> equality check.  That's not okay.

Ah, that's a different attack than what I was thinking of. You could
also fix this attack by simply using tagged hashing to make the
computation of inner nodes and leaf nodes be guaranteed to be different.
If so, concatenating the two leaf nodes' digests and computing the
Amazon-style hash tree root value would result in a different digest.

-- 
'peter'[:-1]@petertodd.org
000000000000000003ee8302880a8e3d7a1e76be81c561cee33a44767680472e