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

Andy Lutomirski <luto@amacapital.net> Fri, 30 October 2015 22:09 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 667CD1ACF18 for <openpgp@ietfa.amsl.com>; Fri, 30 Oct 2015 15:09:41 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.121
X-Spam-Level:
X-Spam-Status: No, score=0.121 tagged_above=-999 required=5 tests=[BAYES_05=-0.5, 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 Rhz0hHhqUiFs for <openpgp@ietfa.amsl.com>; Fri, 30 Oct 2015 15:09:40 -0700 (PDT)
Received: from mail-oi0-x236.google.com (mail-oi0-x236.google.com [IPv6:2607:f8b0:4003:c06::236]) (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 4E25D1ACF0A for <openpgp@ietf.org>; Fri, 30 Oct 2015 15:09:40 -0700 (PDT)
Received: by oiad129 with SMTP id d129so67346992oia.0 for <openpgp@ietf.org>; Fri, 30 Oct 2015 15:09:39 -0700 (PDT)
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=IvAb7Irk6rQZK/5bD0oTQC5nKWvaoE0uDzRRR92Shfs=; b=KtXGase/LCN/wMvs5VoqMVNP2ItSOlGoHtZc0BkPbg1a7MxiLutYLt2Ro2PAdjB1AD gbYaxF8mfmJOqtuxtXlTe1XRZHd7hlVwPxzcFYcDbi3tfT/mXHeN7yhb9wmzHS/fYIzp 3I9FvIVM4Deua0iJgCZFpD68I+WKXwqCIzr8KkQkm6A1ESWfAucz6sbYX1XxYHz5zua8 uCZE2qdvlDwabiSBVCDRT4zO9VR8b/g6Wn3TI7P62LnCYyuhaeZ2X25bgU0NbSl6ytnY FjmVOEt9m1Gmcz+iVozrlvn+XqnL7baAXs1Jpb3BkmNTWe6NRdrPOGvgalBGX/FPl1MN Xs1w==
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=IvAb7Irk6rQZK/5bD0oTQC5nKWvaoE0uDzRRR92Shfs=; b=Y5XArhzq9a+Kr5YWHWy1XSblaNhZquyg1xpdtFZCfVZBdbUpWMQehXKh/oQtaFSYr/ wl6XDEgzBBRYPa5VI7NID5xi3yARexeFzC0nA6eIcE24RokUe/6jeFFr8X3jUCuXZCI/ xpC0WOR8uOlQbQlOAILKCPMnB9ObV+EuueG7xp+5/zzgowgGLAoHptQmpl4p9hZZjOFS Hah4ImtsFZhZMhOrUNrrwZd6nu7qXkTSSME+5BbV3dkQXZ8agdzS3YN9LNGfxDSL67n+ iuZQnegK3D9EFuAVejq1Skv6OIgvn1dOrIy/WOfQJ1iSgh2aezFnEzCZz6E8JnJgKCNi sRwQ==
X-Gm-Message-State: ALoCoQlSS+2IrbxyBwgdTst7B5mF0yFvOAUBpbfXoXnOODazk9TzVfA4F7CE99N/OMVnfePhtSXI
X-Received: by 10.202.184.130 with SMTP id i124mr6611321oif.122.1446242979565; Fri, 30 Oct 2015 15:09:39 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.202.205.216 with HTTP; Fri, 30 Oct 2015 15:09:19 -0700 (PDT)
In-Reply-To: <CAMfhd9XE_v5ngzfq0g9dGdjKRp82-GxZwMNLoCYeUr6ZcvOjJw@mail.gmail.com>
References: <87twp91d8r.fsf@alice.fifthhorseman.net> <20151030183223.35630603F0@jupiter.mumble.net> <CALCETrULywQ-14gjnEgcbtO3zJoK5PhbiE953eZXO+r108eFHg@mail.gmail.com> <CAMfhd9XE_v5ngzfq0g9dGdjKRp82-GxZwMNLoCYeUr6ZcvOjJw@mail.gmail.com>
From: Andy Lutomirski <luto@amacapital.net>
Date: Fri, 30 Oct 2015 15:09:19 -0700
Message-ID: <CALCETrWuw9s5QP_pQArwG+Ykf4nbq_NxzdGpQSfDzrEaRE-Q2g@mail.gmail.com>
To: Adam Langley <agl@imperialviolet.org>
Content-Type: text/plain; charset=UTF-8
Archived-At: <http://mailarchive.ietf.org/arch/msg/openpgp/2U01gigZJdrJ92pyc52SwIUjvmo>
X-Mailman-Approved-At: Sun, 01 Nov 2015 07:51:57 -0800
Cc: 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: Fri, 30 Oct 2015 22:09:41 -0000

On Fri, Oct 30, 2015 at 2:28 PM, Adam Langley <agl@imperialviolet.org>; wrote:
> On Fri, Oct 30, 2015 at 11:47 AM, Andy Lutomirski <luto@amacapital.net>; wrote:
>> 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.
>
> Do you have references for either of these two issues? I wasn't aware of them.
>

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.

I don't know what Bittorrent is actually doing, but I found this
thing:  http://www.bittorrent.org/beps/bep_0030.html  It seems
similarly broken.

--Andy