[BitTorrent] BT2 & hash trees

John Prevost j.prevost at gmail.com
Wed Jul 21 17:15:07 EDT 2004

```On Wed, 21 Jul 2004 13:43:00 -0700 (PDT), Elliott Mitchell <ehem at m5p.com> wrote:
> > It depends on where you start. If you have 4 kb data and generate a
> > tree of 4 + 2 + 1 = 7 nodes, I could give you a file of 4 kb, a file of
> > 40 bytes and a file of 20 bytes that would all result in the same root
> > hash. And that's clearly not what you want.
>
> Yes, in theory it is possible to do that. Thing is it is computationally
> infeasible to produce those 20 and 40 bytes strings with the same hash.
> Adding the cookie to the SHA1 hash doesn't make this significantly more
> difficult. With or without the cookie you're not going to produce one in

You don't seem to understand--without having some sort of distinction
between internal and external hases, it is in fact trivial.  That's
what my original example is all about.  You can't deliver a chosen
signature.  Let me break it down a different way:

root---H(H(A)+H(B))---H(A)  -  from data A
|              |
|              --H(B)  -  from data B
|
--H(H(C)+H(D))---H(C)  -  from data C
|
--H(D)  -  from data D

The above is the proper tree, computed from the data A+B+C+D.  The
root value is H( H(H(A)+H(B)) + H(H(C)+H(D)) ).  Now here is the
chosen invalid tree with the same root hash:

root---H(H(A)+H(B))---H(A)  -  from data A
|              |
|              --H(B)  -  from data B
|
--H(X)-----------H(X)  -  from data X, where X = H(C)+H(D)

That is, the data value of the third block (X) is the concatenated
hashes H(C)+H(D), and H(H(C)+H(D)) is what is needed to produce the
proper root hash.

Here, the root value is H( H(H(A)+H(B)) + H(H(C)+H(D)) ) = H(
H(H(A)+H(B)) + H(X) ).

It is not trivial to calculate X given only A and B.  But if you know
the entire original message A+B+C+D, you can calculate X.  Hence, you
can provide to someone who knows only the root hash (which is the only
trusted information in a Merkle tree system) an invalid message which
appears to be valid, as long as you have access to the original
message.

That's why different hash functions are used for internal and external
nodes in the tree:

root---IH(LH(A)+LH(B))---LH(A)  -  from data A
|                 |
|                 --LH(B)  -  from data B
|
--IH(LH(C)+LH(D))---LH(C)  -  from data C
|
--LH(D)  -  from data D

root---IH(LH(A)+LH(B))---LH(A)  -  from data A
|                 |
|                 --LH(B)  -  from data B
|
--LH(X)-------------LH(X)  -  from data X, where X = ?

As long as IH is not the same as LH, there is no trivial way to
compute an X such that LH(X) = IH(LH(C)+LH(D)), whereas before, with
IH and LH being the same, all that was required was to provide
H(C)+H(D) as the X.

Adding a byte '\000' in front of internal values and '\001' in front
of leaf values (or vice-versa) is simply a trivial way of having two
distinct hash functions.  You could just as easily choose SHA-1 for
leaf hashes and SHA-256 for internal hashes, or whatever.  (Note,
however, that prepending a character to messages for only one of the
two hash functions would not work: if you prepend to internal hashes
only, the attacker can prepend in his attack data.  If you prepend to
leaf hashes only, the attacker can still attack the portion of
messages that have a hash beginning with the correct value.  By
prepending to both, you have independent functions.)

Make sense now?

John.

Make a clean sweep of pop-up ads. Yahoo! Companion Toolbar.
http://us.click.yahoo.com/L5YrjA/eSIIAA/yQLSAA/dkFolB/TM
--------------------------------------------------------------------~->

<*> 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/

```