On Fri, Oct 30, 2015 at 2:28 PM, Adam Langley
<agl(_at_)imperialviolet(_dot_)org> wrote:
On Fri, Oct 30, 2015 at 11:47 AM, Andy Lutomirski
<luto(_at_)amacapital(_dot_)net> wrote:
As far as I know, everyone thinks they know how to do a Merkle tree
for things like this, but there doesn't seem to be a credible
standard, and there are at least two modern examples of doing it
wrong: Amazon's Glacier hash and (unless it changed) Bittorrent's new
Merkle tree.
Do you have references for either of these two issues? I wasn't aware of them.
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.
I don't know what Bittorrent is actually doing, but I found this
thing: http://www.bittorrent.org/beps/bep_0030.html It seems
similarly broken.
--Andy
_______________________________________________
openpgp mailing list
openpgp(_at_)ietf(_dot_)org
https://www.ietf.org/mailman/listinfo/openpgp