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

Andy Lutomirski <luto@amacapital.net> Tue, 03 November 2015 00:15 UTC

Return-Path: <luto@amacapital.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 AF7531A92AF for <openpgp@ietfa.amsl.com>; Mon, 2 Nov 2015 16:15:41 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.279
X-Spam-Level:
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 mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id Sj-SkJQhDywn for <openpgp@ietfa.amsl.com>; Mon, 2 Nov 2015 16:15:40 -0800 (PST)
Received: from mail-oi0-x230.google.com (mail-oi0-x230.google.com [IPv6:2607:f8b0:4003:c06::230]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 998001A9245 for <openpgp@ietf.org>; Mon, 2 Nov 2015 16:15:40 -0800 (PST)
Received: by oiao187 with SMTP id o187so378011oia.3 for <openpgp@ietf.org>; Mon, 02 Nov 2015 16:15:40 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=amacapital_net.20150623.gappssmtp.com; s=20150623; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type; bh=/X47oRfSSuY1gvtx5kAoo8Ro4c/qjRjusOcbKSIlJaI=; b=BqmKcgPmH0GV/cC/VjKGTnFVUMPcTWG2En954xdZAPB7EOVZ6EMyjyPZyksTIYuIAI n5qhSUk8NgODz/ajEH73nSxGJwTtUfMe6QfTH/D9u5e798EKJ72doTbZZsDQXmVekgWq MvlJHR7TbVFjZOoppCJhPUJ4uVPV6BkwkBTOh88hjsnXORiRtZoAC2RYHugDyc1mYUmo 40EkbfmEUzn8q1g8GznxhGkvx63lcl4ztjnQSoJLID6vskDeL8708N+dYWGTkPB9dXBG TFeW1gNGtdYYCuu6zR9KZ9q1vdOs/Axljqj7tebBPJr9inKStBMdj35UT7Ly/TxpU2jq RUfA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc:content-type; bh=/X47oRfSSuY1gvtx5kAoo8Ro4c/qjRjusOcbKSIlJaI=; b=P/t39tJ09Y+hfFiGg7fE/uY5CA05G6MgCv8Q4BD5QiJIvKm19cPwtkhYkuTAPwKZGQ sRa6aq/x86WZCjEV6PPT9wUbTKW44c0TGuEk4N9E3Xd6wiIbz5VmI7bnpiMBtMQXkXTR ahIWu3Bais1/eyiSGxyBzRvERIIJB0J/xjbQrJ+EP0JNfQc4LJQBGLeui5t++hkyUNaQ 93TwZTvx5FJ8OEROSzeMa4z1Yn/bpzf2/qfMW2Sz9LGiCo12/vn6OXh3RuLE3JvPrOn3 IH9e8+3ZdODMe2zr1FBHn5c4hz66jQeDl7Ayhlgmrh3qmK7y++PK0CZvqvxlsRQIoZN5 az3g==
X-Gm-Message-State: ALoCoQmZIlZpt1CEvGTuXhpSPeQtHnGAuhVqgm95xlx16eZjKDFcDbEmZv/TSE4mRhJv0FUBcdSs
X-Received: by 10.202.204.67 with SMTP id c64mr15940225oig.93.1446509740023; Mon, 02 Nov 2015 16:15:40 -0800 (PST)
MIME-Version: 1.0
Received: by 10.202.205.216 with HTTP; Mon, 2 Nov 2015 16:15:20 -0800 (PST)
In-Reply-To: <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> <20151103001239.GA1313@muck>
From: Andy Lutomirski <luto@amacapital.net>
Date: Mon, 2 Nov 2015 16:15:20 -0800
Message-ID: <CALCETrVyCgjU0=n1JHkEiBy-du69hqCCtEZiQduDLZAn_tk2VQ@mail.gmail.com>
To: Peter Todd <pete@petertodd.org>
Content-Type: text/plain; charset=UTF-8
Archived-At: <http://mailarchive.ietf.org/arch/msg/openpgp/1VPwck7e5iGmFiZVdPDehj4B3-Q>
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:15:41 -0000

On Mon, Nov 2, 2015 at 4:12 PM, Peter Todd <pete@petertodd.org>; wrote:
> 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.
>

Indeed.  My point is just that hash trees are useful and that they're
apparently easy enough to screw up that major commercial users have
screwed them up.

Sakura is interesting because it allows lots of flexibility while
retaining a security proof.  For applications that require or even
demand reduced flexibility, other options would work fine as well.

--Andy