2
$\begingroup$

I need to implement a Merkle tree using a 128 bit hash function. In general, any hash function that guarantees pre-image, second pre-image and collission resistance should be fine to implement a Markle tree. Is it correct? Probably, it is not even necessary to have pre-image resistance as long as the other two properties are available. Indeed, if you use the Merkle tree for data integrity, you want it to be binding (it should be computationally hard to substitute leaves and get the same root) but no need to be hiding (it is fine to leak the values through the hashes). Is it correct?

Regarding 128 bits security, well known broken hash functions such as MD5 do not work. However, do I get any advantage in terms of security (with respect to MD5) by using for example SHA256 and truncate it to 128 bits?

$\endgroup$
2
  • $\begingroup$ Unfortunately, a 128-bit hash function can only have a maximum collision resistance of $ 2^{64} $, which is not considered sufficient these days, since it's easily attackable. You'll need at least a 256-bit hash for this purpose. $\endgroup$
    – bk2204
    May 6 at 7:42
  • $\begingroup$ @bk2204 Actually, we can use randomized hashing to deter collision attack. I've not read the paper and haven't carried out thought experiment to understand how it work, so I cannot make a formal answer at this point. $\endgroup$
    – DannyNiu
    May 6 at 11:43

1 Answer 1

1
$\begingroup$

You absolutely need preimage resistance (both first preimage and second preimage) to have a functional merkle tree. Preimage resistance refers to finding hash inputs that give a given output. For an ideal k bit hash the difficulty of first and second preimages is 2^k. 128 bit hashes are fine here although multi-target attacks can weaken that bound a bit (more on that later).

A hash that was collision resistant but not preimage resistant would be very strange. Certainly it wouldn't work in a Merkle tree since a first preimage attack would allow splicing a new leaf into the tree.

If adversaries get to generate Merkle trees, they can deliberately cause collisions and then collision resistance becomes nessesary. This is the same as saying the Merkle tree is computationally binding(IE an adversary can't create two different trees with the same root hash). 128 bit hashes are no longer enough since collisions can be found with 2^64 work. For this you need 256 bits or at least 192 bits.

Randomised Hashing

To get better security bounds or handle untrusted data, some merkle trees incorporate pseudorandomly generated masks into their hashes. This technique is used in XMSS to improve the security bounds by adding a location based pseudorandom mask to all hash inputs and keying each hash with another pseudorandom value. This makes it harder to find preimages using a multi target attack since the attacker's attempts don't generalise across the entire tree.

When generating a Merkle tree with untrusted data, choosing a random salt with which to generate these masks will prevent the attacker from causing collisions by maliciously choosing leaf data values. So if the person choosing the salt is honest, collision resistance is not needed.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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