# Tag Info

9

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

6

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

5

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

5

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

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

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

4

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

4

If you are not worried about revealing information, then you can commit to the set of data items in one Merkle tree, and to the frontier of that set in another Merkle tree. A frontier is the set of ancestors to all values that are not in the tree (note that this is about the same size as the size of the set itself). Then, in order to prove that a value is ...

3

Depending on your trust assumptions about this server, you might be able to use cryptographic accumulators which provide constant-sized (non)membership proofs. However, as far as I know, no efficient strong accumulator scheme has been developed yet. Most accumulator constructions rely on the RSA assumption where the server knows the factorization $n = pq$ ...

3

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

3

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

3

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

If your data is a set $S$ of key-value pairs, such that $S = \{(k,v) \vert k \in K, v \in V\}$, you can have non-membership proofs for your data by using a sorted Merkle tree (sorted by the keys in $K$). This tree can be a binary-search tree, a trie, a sparse Merkle Tree (similar to the one in Micali's Zero Knowledge sets paper, and also reintroduced by ...

2

Assuming that you know that $h_0$ is the root hash of a Merkle tree for the file, you can be sure that $h_1$ is a hash of a section of the file if you know that it's one of the hashes of the sections one level below the root and you know its sibling hashes, i.e. you have values $(h_1^1, \dots, h_1^{m_1})$ such that $\mathscr{H}(h_1^1, \dots, h_1^{m_1}) = h_0$...

1

What do you mean that you keep the root of the merkle tree locally? Is the merkle tree signed? If i understand what you are saying correctly, then the server can choose not to display to the public the changes you have made and keep presenting the merkle tree for the values before you updated them. Even if you sign the merkle tree the server can still do ...

1

SHA-1 is measurably faster and I would like to know if its insecurity is still there, when used in a Merkle tree. Yes, the insecurity is still there. Any collision in the underlying hash function can be used to produce a collision in the root of the Merkle tree. A quick example: Suppose our SHA-1 Merkle tree has two leaf nodes, $a$ and $b$, and that we ...

1

It is not true that there would always be at most two hashes required per elided range. Suppose you have an eight-byte long content and want to elide all but the last. You need to supply one hash for the left half, one to cover the next two and one more to cover the last one. Similarly, with 16 bytes of content, eliding the first 15 requires four hashes. ...

1

Merkle trees provide authentication with no secrets, and can more efficiently authenticate large-enough contiguous regions. It is "more simple to ask" for "a particular piece of Db (suppose a database divided in blocks) and receive from the cloud provider that block with the digital signature". (I believe "with no secrets" is the more important ...

1

Given only the information in the original question, it would be easy for an attacker to calculate generate an arbitrary message E, then calculate the Hash("This is message E + ab3ed") = 31415, and if the system can be tricked into trusting that 31415 is the hash of a valid message, there's no way to prove that E isn't really a valid sibling of B. This may ...

1

I would like to extend Chrystographer answer. If this is a part of a incoming or outgoing message, you cannot prove it. Anybody can write valid messages. You need Merkle tree and digital signature of the root's hash.

1

If dynamically added, then I assume you know of the siblings at the time a node needs to be added, and ideally some order to the siblings. If that's all true, then instead of adding the hash of the parent, add the hash of the last sibling. If there are no siblings at insertion time, then revert to adding the parent's hash. So then you'll be able to prove ...

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

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

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

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