Score:2

Implementing a Merkle tree using a 128 bit hash function?

ge flag

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?

bk2204 avatar
fr flag
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.
DannyNiu avatar
vu flag
@bk2204 Actually, we can use [randomized hashing](https://link.springer.com/chapter/10.1007/11818175_3) 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.
Score:1
mx flag

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.

I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.