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

[Andy Lutomirski <[e-mail]>]

On Fri, Oct 30, 2015 at 2:28 PM, Adam Langley <[e-mail]> wrote:
> On Fri, Oct 30, 2015 at 11:47 AM, Andy Lutomirski <[e-mail]> 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