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

Andy Lutomirski <luto@amacapital.net> Mon, 02 November 2015 23:45 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 3AF5F1A90A0 for <openpgp@ietfa.amsl.com>; Mon, 2 Nov 2015 15:45:05 -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 T9GeLsheZcwa for <openpgp@ietfa.amsl.com>; Mon, 2 Nov 2015 15:45:03 -0800 (PST)
Received: from mail-oi0-x22f.google.com (mail-oi0-x22f.google.com [IPv6:2607:f8b0:4003:c06::22f]) (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 8E1611A90BA for <openpgp@ietf.org>; Mon, 2 Nov 2015 15:45:03 -0800 (PST)
Received: by oiao187 with SMTP id o187so52573oia.3 for <openpgp@ietf.org>; Mon, 02 Nov 2015 15:45:03 -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=CqPnaG585VFUOioRG/itVRBPn82f4YrSVXbLKCttRk0=; b=q7b8n34/SWnBocLtJG+jWwJpWSVaLsVbtGuvRedze267SbJJq097Y5Mui7VCwe9u4V F/b78DxN9iWzh+gHFNHCU4wKA5tlH+fEpmsCmWvmH8o/A5378YzyGwl3QG7uyjJLdVOF mkAhZDtzH9EzZOmb+mrQxgx7NKyF/FfQdedGDtja/dMYfD9OGNSQu+bJ8VXSxipPYgww sRZT7WJGWs8/QKUTuNlQouaAPFwgWfy2zqCmVJef3KZGZAmXJVs1vy4tsNvLktgCtkBT p0dAvPdKASEfQXTAlrzufXpgPSm6mxE5pDR15Bsc00BJTIp5Xrt9FSAheFwGf1WdEGM/ bT3g==
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=CqPnaG585VFUOioRG/itVRBPn82f4YrSVXbLKCttRk0=; b=AGoepnALPvUKp9YKFrsAnPz6LMwyYN9B+VeZMC5bkYOiEuNYMEeNJEGe5IAiniiebl d9b4aIkjgxeWYMp0I4utd/t+NV2efGlrfNlYu2MgMJuc1ga0EqqeXiM95m8WlRtBb1DQ quyHTlW3ERRVC2Df4APpHD50AuRFZlyhMY7S46oViNKDaG788RfCMjlURTAGdJFtMb8e vtKF9e7NraRXVerj4z1LerjtVeYCn7fWtdfQl73Afk6zO0km4YGPwHxXY1NPIPBUrjIF zINQyDgrtSJn7dmlBdG5QQtDhijrpQo+QMtsfNVIRt3J9uMMQ/4i1N4VCm5OzGA6P2y6 dWDA==
X-Gm-Message-State: ALoCoQmL1XL/xwh43HuCdAMwPo8Cmewrn73C1hvVGhRsnr7UwsBSMA7w5op7yRNDo5RNQ85nWuEG
X-Received: by 10.202.53.136 with SMTP id c130mr15717210oia.116.1446507902963; Mon, 02 Nov 2015 15:45:02 -0800 (PST)
MIME-Version: 1.0
Received: by 10.202.205.216 with HTTP; Mon, 2 Nov 2015 15:44:43 -0800 (PST)
In-Reply-To: <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> <20151102232502.GA20756@muck>
From: Andy Lutomirski <luto@amacapital.net>
Date: Mon, 2 Nov 2015 15:44:43 -0800
Message-ID: <CALCETrVMcSy41Hiz+WUcdZ2fUGouV8hNmax+OUpG41iuFPgoVg@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/aQrQJe-iGvhQj8ziBo5GW1OrbO4>
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:45:05 -0000

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

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.

--Andy