# Implementing a Merkle tree using a 128 bit hash function?

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?

• 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. Commented May 6, 2023 at 7:42
• @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. Commented May 6, 2023 at 11:43

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