# Merkle tree (dm-verity) with SHA-256 vs. SHA-1

Is there any knowledge or research on the use of different hash functions within a Merkle tree? My use case is file integrity protection. I am thinking about using different hash functions due to performance restrictions:

Linux device mapper verity target allows you to select different hash functions. I originally aimed at SHA-256, however SHA-1 is measurably faster and I would like to know if its insecurity is still there, when used in a Merkle tree. (Btw: root hash is protected by RSA signature) Assuming a storage device with 2GB of data and 4Kb blocks, verity creates a merkle tree with 3 tree levels between data and and the root hash. I understand that a single SHA-1 is unsecure for the integrity of a file, but what about the approach of having a hash per 4Kb of a file. If an attacker changes one block only, the input data for intermediate hashes change only at 20 bytes (32 byte for SHA-256) while the remaining 4064 (4076) byte are identical. So does this make finding a collision really harder or is this a misinterpretation? This partial change in data propagates up to the root of the tree.

Ok, changing only one data block with a collision in the corresponding hash breaks the hash tree, as the collision at the bottom yield to the same hash tree. This is easier with SHA-1, isn't it?

What about changes in a block without a collision where collision at the intermediate nodes must lead to the same root hash value. Is this harder?

What hash would you suggest for such a use case? There is no recommendation with Linux kernel implementation of dm-verity. Is SHA-1 too weak?

• Not an answer, but you may want to try SHA-512 or SHA-384 as well if you have a benchmark of some kind. They are usually faster than SHA-256 on 64-bit computers. However, I would not expect much difference in practice, since IO is usually slower than hashes. – otus Feb 5 '16 at 7:24

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 know a SHA-1 collision such that $\text{SHA-1}(m_1) = \text{SHA-1}(m_2)$ but $m_1 \neq m_2$. The root hash of the Merkle tree will be $h = \text{SHA-1}(\text{SHA-1}(a) \| \text{SHA-1}(b))$.

We can create two different trees with the same root hash by setting $a$ to $m_1$ in one tree, and $a$ to $m_2$ in the other (and keep $b$ the same for both trees). These trees will have the same root hash: $\text{SHA-1}(\text{SHA-1}(m_1) \| \text{SHA-1}(b)) = \text{SHA-1}(\text{SHA-1}(m_2) \| \text{SHA-1}(b))$, because $\text{SHA-1}(m_1) = \text{SHA-1}(m_2)$. In other words, an attacker can swap out a block in the bottom of the tree without the root node "noticing".

The use of a Merkle tree will not protect against problems in the underlying hash function's collision resistance. I wouldn't recommend using SHA-1 if security is an important consideration here.

Normally, I would recommend using BLAKE2. It (well, its predecessor) was a finalist in the SHA-3 competition (i.e. it's secure), and it's faster than both SHA-1 and MD5. Unfortunately, I don't know if it's available in dm-verity.

• Note that a collision attack requires the attacker being able to set a block to $m_1$ to be able to switch it to $m_2$ later. I.e. the attacker much be able to affect some data stored in the filesystem. Not necessarily insurmountable, but in some cases it can be assumed not to be the case. – otus Feb 5 '16 at 7:12