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

[Andy Lutomirski <[e-mail]>]

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