# Is this modification in Merkle-Damgård collision-resistant?

We modify Merkle-Damgård construction by setting $$z_0:=L$$ (the length of the message), computing $$z_i:=h(z_{i-1}||x_i)$$ for $$i=1,...,B$$ and defining $$H(x):=z_B.$$ Is this construction collision-resistant?

I think that it can not be collision resistant, because by adding the input length in the beginning after many steps two different messages may have the same output, but I can not find a counterexample to refute the assumption.

Collision resistant definition (from Katz&Lindell Introduction to Modern Cryptography): it is difficult to find $$x$$ and $$x'$$, with $$x \neq x'$$ such that $$H(x)=H(x')$$.

• Yes, no, or less, depending on the definition of collision-resistant. Suggestion: write down the definition considered, and wonder if the attack in the question works per that definition. The answers to that different question can help. If stuck, per our policy on what's on-topic, add the definition of collision-resistant considered in the question, and explain where applying it is difficult. Dec 13, 2020 at 10:28
• Have you tried proving that it's collision resistant? Do you know whether $h$ is CR? Dec 13, 2020 at 13:16
• yes, h is collision resistant. Dec 13, 2020 at 13:25
• The standard way of proving a construction is CR (based on a CR primitive) is to show, given a collision with the construction, you can show a collision in the CR primitive. Does that proof technique work in this case? How does it break down? That should show you how to construct a CR $h$ where your modified MD construction is not CR... Dec 13, 2020 at 17:31
• In my edition of K&L, definition 5.2 is much more complex than yours. In particular, it makes "difficult" something on the tune of: there exists no polynomial-time algorithm. Dec 13, 2020 at 17:35

As Katz-Lindell said, assume there is a collision-resistant compression function such that it is possible to efficiently find some $$L, x \in \{\ 0, 1\}^{n}$$ such that $$h(L,x) = L - n$$.
In this case, the hash of any message $$y$$ of length $$L-n$$ is equal to the hash of the message $$(x \| y)$$ of length $$L$$.