Tag Info

Hot answers tagged

7

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


5

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


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


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

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


2

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}$


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.


2

Updating a Merkle hash tree is trivial. For instance, if you want to update a leaf, then you update it and then update every node on the path from it to the root. If you have a particular operation on the tree in mind, the necessary updates follow immediately from the kind of update you want to do. It's all very straightforward. There's no reason to ...


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

Yes, a stateless hashbased signature method called Sphincs was recently proposed. It works by having a moderately large Merkle tree (similar to what D.W. suggested), but instead of using Lamport or Winternitz one time signatures at the bottom, it uses a hash based few-time signature method; this allows an occasional collision at the very bottom of the tree. ...


1

While I originally looked into what would require the use of some Tree Topology or use of Bloom Filters, I asked a friend on this problem. He gave me a more practical solution: Sort each Tree by Leaves Seperately Then you put each result in heaps - sort of like a merge step of the quick sort algorithm. You then take the First Heap from the first tree and ...


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

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

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

In a Merkle Tree, data is eventually and inevitably lost, because it is compressed away. If a Merkle Tree used a non-padded compression function, the size of the resulting hashes would go down level by level, resulting in a top hash that is very short. The shorter that top hash is, the less it CAN say about the contents of its tree. The longer the resulting ...



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