# [BitTorrent] Back to Merkle Hash Trees... [no longer on topic, wandering into cryptography]

Joseph Ashwood ashwood at msn.com
Mon Feb 7 19:18:36 EST 2005

```
----- Original Message -----
From: "Nick Johnson" <arachnid at notdot.net>
Subject: Re: [BitTorrent] Back to Merkle Hash Trees...

> As far as I'm aware, there have been no preimage attacks found in MD5,
> SHA-0, or SHA-1. See http://www.cryptography.com/cnews/hash.html.
> Trying to build a merkle tree implementation assuming fundamental
> weaknesses in the hash you're using seems a bad idea. If the hash is
> broken, all bets are off.

The first preimage attack on MD5 was published in the mid-1990s, and focused
on the final compression function. And just for the record I wouldn't
necessarily trust someone who attempted to patent differential power
analysis (which Cryptography Research did try). It is always best to assume
the worst case. Assuming that preimage attacks have been found against the
hash (which were published at the same conference but made less news because
the attacks mentioned were published first), now that is not to say that any
of these are full pre-image attacks, they are differential and linear
attacks against the ciphers which using adjusted pre-images could compute
the change faster than brute force. This is a rather obscure kind of attack,
and one that some will argue is not a "real" break. But the fact of the
matter is that they were able to, with reasonable likelihood, produce
preimages that resulted in chosen differentials from the first postimage,
i.e. they found attacks such that:
A != B
hash(A) != hash(B)
C = offset
D = result
hash(A XOR D) = hash(B) XOR C
with reasonable probability
I admit it is difficult to see how this could be used to attack a hash tree,
but consider:
target if hash(A)
alter tree such that E is the desired value.
Assume the existence of some number of post blocks to be included (attacker
can change length)
Now using the earlier result
Compute hash of rest of tree
Determine G such that hash(B| F XOR G) = hash(A) for some F
new tree includes B and F XOR G as children
root has now matches (that is if I didn't screw up the recitation from
memory).
My proposal blocks this because the attacker has to adjust the number of
children (at least one was added to the tree), that information is progated
to the next level, so the same extra branching has to be created, repeat
until root value has to be changed.

I agree that using a known broken hash is a bad idea, but not preparing for
the hash to be broken is like assuming you shouldn't wear your seatbelt
because you've never crashed your car. By assuming that breaks will happen
you can make it more difficult to perform any break, leading to more
resilient security.
Joe

<*> To visit your group on the web, go to:
http://groups.yahoo.com/group/BitTorrent/

<*> To unsubscribe from this group, send an email to:
BitTorrent-unsubscribe at yahoogroups.com

<*> Your use of Yahoo! Groups is subject to:
http://docs.yahoo.com/info/terms/

```