2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – otus Feb 5 '16 at 7:24
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – otus Feb 5 '16 at 7:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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