# Tag Info

6

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) ...

5

Yes, you should be able to handle this situation readily. There are many optimizations available. One key observation is that if you're going to go to disk, then you might as well read lots of data: it takes just as long to read an entire block of data as to read 1 byte. So, I suggest you store the data on disk in 4096-byte blocks, and do a Merkle tree ...

4

My understanding is that, for the even more special case where a and b are not only of equal length but some power of two times a fixed block size, all hash tree systems (also called a Merkle tree system or a binary hash chain) meet your criteria. E.g. satisfying following relation h(a || b) = h(a) · h(b), where h(x) is hash function itself, x || y is ...

4

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 ...

4

The Tree Hash EXchange format (THEX) spec (which seems to have dropped off the web, but is still available on archive.org) says, in section 2: 2.1 Hash Functions The strength of the hash tree construct is only as strong as the underlying hash algorithm. Thus, it is RECOMMENDED that a secure hash algorithm such as SHA-1 be used as the basis of ...

3

You can build a gigantic, enormous tree that has capacity for up to $2^{80}$ one-time signatures (say). Then, each time you want to sign something, you randomly pick a 80-bit value and use that to select which of the $2^{80}$ subtrees to use to sign the message. As long as the number of messages you intend to sign is much less than $2^{40}$ messages, a ...

2

In general there is no reason to use tree hash modes for Merkle trees. The reason is that a Merkle tree itself is already some kind of tree hash mode. The important thing about this kind of mode is that it allows to compute the root node given the value of one leaf and one node per tree level. The possible ambiguity of hashes is not relevant for hash-based ...

2

Merkle trees allow several time-memory-tradeoffs: Using larger leaves or store only hashes at a certain level above then leaves. Now you need to hash a bigger leaf for update, but you need to keep fewer intermediate hashes in memory. Using a higher fanout. With fanout=2 you need to keep 2*n hashes in memory. With fanout=4 you only need 1.33*n hashes. But ...

2

On multi-threading: Read the code. As Paulo writes, that's up to the implementation. Read the source code of your library and see for yourself what it is doing; it shouldn't be too hard to figure it out.

1

I don't know if the mathematical property you are looking for has a name. It's a bit similar to linearity, but $||$ is of course not an addition operator (e.g. not commutative). A function with this property is not as secure as a perfectly secure cryptographic hash function of the same output length. You can find collisions with a probability related to the ...

1

Here's something similar but completely different... A 'one-way' cryptographic hash function which is regressible when combined with the function's parsed trapdoor index. That is to say, the hash function is the file and the trapdoor table file is the key! The trapdoor table generated is approximately 60% larger than the original file but eminently ...

1

It depends on what properties the compression function has, which in turn depends on how the hash function was constructed. In hash functions based on the Merkle–Damgård construction, the compression function is required to be collision, preimage and second preimage resistant, just like the hash function itself. The only difference is input length: the ...

1

The usual way to do this is by using a CSPRNG to generate the leaf values, such as AES in counter mode. That way, once you have calculated the entire tree, you only need to store the upper layers, the secret AES key, and the initial counter value, and it is quite easy to recalculate very quickly any particular branch you need. For example, let's say you ...

1

First, the passage you refer to is on page 55, 2nd paragraph. And it would also be great if you'd announce that figure 4.1 is actually in a different document ;-) took me quite a while to figure this out. Now to your question. So, I assume you understand the paragraph? You have to note that a round here corresponds to $2^{(i-1)h}$ "whole tree rounds". Now, ...

1

The shorter the hash value the less effort for the attacker to brute force it. If the output is 16bytes then the attacker must spend $2^{128/2}$ "time" to find a collision. If it was 8bytes it would need $2^{64/2}$

Only top voted, non community-wiki answers of a minimum length are eligible