ietf-openpgp
[Top] [All Lists]

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

2015-11-02 17:45:09
On Mon, Nov 2, 2015 at 3:25 PM, Peter Todd <pete(_at_)petertodd(_dot_)org> 
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

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