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

[Andy Lutomirski <[e-mail]>]

On Mon, Nov 2, 2015 at 3:25 PM, Peter Todd <[e-mail]> 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