24
$\begingroup$

We previously learned that the THEX hash tree specification, which used by some P2P systems, requires that two different hash functions be used: one for the leaf nodes (hashes of input data), and one for the internal/branch nodes (hashes of hashes).

In order to protect against collisions between leaf hashes and internal hashes, different hash constructs are used to hash the leaf nodes and the internal nodes. The same hash algorithm is used as the basis of each construct, but a single '1' byte in network byte order, or 0x01 is prepended to the input of the internal node hashes, and a single '0' byte, or 0x00 is prepended to the input of the leaf node hashes.

By contrast, the merkle tree hashes used by BitTorrent (specified as a v1 extension in BEP 30 and later as v2 in BEP 52) just use unmodified SHA-1 or SHA-256 for all hashes. It's possible that this was a trade-off of security for simplicity, but that wasn't mentioned in the proposal.

What is the benefit of using two different hashes in this scheme?

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
21
$\begingroup$

If the same standard hash function was used for both leaves and branch nodes, it would be easy to generate collisions and even second preimages.

For example, let $M$ be a message which is longer than the segment size of the hash tree, but (for simplicity) no more than two segments long. Then the hash value of $M$ is calculated as $$H(M) = H_I(H_L(M_0) \,\|\, H_L(M_1)),$$ where $H_I$ is the internal hash function, $H_L$ is the leaf hash function, and $M_0$ and $M_1$ are the first and second segments of $M$. We'll also assume that the segment size of the hash tree is at least twice as long as the length of the output of $H_L$.

Now let $M' = H_L(M_0) \,\|\, H_L(M_1)$. Since $M'$ is, by assumption, at most one segment long, its hash will be calculated as $$H(M') = H_L(M') = H_L(H_L(M_0) \,\|\, H_L(M_1)).$$ If $H_L = H_I$, then $H(M') = H(M)$, and we've just found a second preimage for $H(M)$.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ I realized that the reason BitTorrent's Simple Merkel Trees aren't vulnerable to this is that they're padded full by adding 0-leaves (until the number of them reaches a power of two). On the other hand THEX allows unpaired leaf hashes to "float up" the tree into a spot where an internal hash would otherwise be expected. $\endgroup$
    – Jeremy Banks
    Commented Mar 17, 2012 at 15:20
  • 2
    $\begingroup$ Just padding the number of segments to a power of 2 doesn't help: note that $M$ and $M'$ in my example have 2 and 1 segments respectively. However, padding the last segment itself to full length would indeed suffice to differentiate leaf hashes from internal hashes, as long as the segment length is strictly greater than the internal hash input length. (But do note that such padding itself, if not done carefully enough, may allow the construction of collisions.) $\endgroup$
    – Ilmari Karonen
    Commented Mar 17, 2012 at 15:32
  • 3
    $\begingroup$ Oops! Thank you for the clarification. New interpretation: The trees are secure in the context of BitTorrent because it already knows the total length of the input, so it's impossible for an attacker to add or remove leaves as would be necessary. $\endgroup$
    – Jeremy Banks
    Commented Mar 17, 2012 at 15:51
  • $\begingroup$ I don't get it. If you are going to apply H to M', then you have to do H_L(H_L(N_0)||H_L(N_1)) (N_0 & N_1 are the left & right halves of M', respectively). That's going to be a different result than H_L(M'). $\endgroup$
    – Melab
    Commented Jul 10, 2023 at 14:15
  • $\begingroup$ @Melab: "We'll also assume that the segment size of the hash tree is at least twice as long as the length of the output of $H_L$." $\endgroup$
    – Ilmari Karonen
    Commented Jul 11, 2023 at 16:58
14
$\begingroup$

The torrent tree hash is vulnerable to second pre-image attacks by itself, even with 00 padding. I won't repeat Ilmari Karonen's answer, who already explained that part very well.

But it isn't used to identify the data by itself:

The original publisher of the content-file set creates a so-called Merkle torrent which is a torrent file that contains a root hash key in its info part instead of a pieces key

This means the infohash, which serves as a unique ID for a torrent isn't just based on the root of the tree, but also includes the filenames and filesizes which are kept in the info dictionary.

Knowing the total size of the torrent prevents such attacks. I still don't like their design decision, since it can easily lead to bugs in torrent clients which aren't aware of this issue. For example if a client forgot to validate the size of the piece, and only checked the hash, it's still be vulnerable.

IMO this design is also flawed in non security related ways.

In particular, the hash tree still crosses file boundaries. Having one root per file would have been nicer. But I guess they tried to stay as close as possible to the original format.

And they decided to use the leaf-size as the piece-size. I would have chosen a small constant leaf-size and leave the piece-size independent from the leaf-size. This would allow changes in piece-size without changing the hash.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.