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

----- Original Message ----- 
From: "Nick Johnson" <[email protected]>
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 






 
Yahoo! Groups Links

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

<*> To unsubscribe from this group, send an email to:
    [email protected]

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