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

[Peter Todd <[e-mail]>]

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.

-- 
'peter'[:-1]@petertodd.org
000000000000000003ee8302880a8e3d7a1e76be81c561cee33a44767680472e