# 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.
– fgrieu
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
• @fgrieu: the problem with that definition is that no fixed hash function, such as SHA-3-512, can satisfy it (as there exists a simple program that will output a collision - we don't know what that program is, but it does exist) Dec 13, 2020 at 23:06

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$$.
As @user1035648 refered to the solution given by Katz-Lindell, you need to find the collision-resistant hash function s.t. $$h(L,x)=L-n$$. Here I give the construction. We let $$h^{s}(x_1\Vert x_2)=g^s(L\Vert 0^n) \oplus g^{s}(x_1\Vert x_2) \oplus (L-n)$$, where we assume that the hash function $$g^s:\{0,1\}^{2n} \rightarrow \{0,1\}^n$$ is collision resistant. And we can prove that $$h^s$$ is a collision resistant hash function. Assuming that $$h^s$$ is not collision resistant, there is a pair of messages $$(x_1\Vert x_2, x'_1\Vert x'_2)$$ such that $$h^s(x_1\Vert x_2) = h^s(x'_1\Vert x'_2)$$. That is, $$g^s(L\Vert 0^n) \oplus g^s(x_1\Vert x_2) \oplus (L-n) = g^s(L\Vert 0^n) \oplus g^s(x'_1\Vert x'_2)\oplus (L-n)$$, which leads to $$g^s(x_1\Vert x_2)=g^s(x'_1\Vert x'_2)$$ and then we construct one collision of $$g^s$$. But according to our assumption, $$g^s$$ is collision resistant. So we get the contradiction. Then we can say $$h^s$$ is collision resistant and it makes $$h(L,0^n)=L-n$$ true.