ietf-openpgp
[Top] [All Lists]

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

2015-11-02 18:13:04
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

Attachment: signature.asc
Description: Digital signature

_______________________________________________
openpgp mailing list
openpgp(_at_)ietf(_dot_)org
https://www.ietf.org/mailman/listinfo/openpgp