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

  • 1
    $\begingroup$ 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. $\endgroup$ – fgrieu Dec 13 '20 at 10:28
  • $\begingroup$ Have you tried proving that it's collision resistant? Do you know whether $h$ is CR? $\endgroup$ – cisnjxqu Dec 13 '20 at 13:16
  • $\begingroup$ yes, h is collision resistant. $\endgroup$ – user84987 Dec 13 '20 at 13:25
  • 2
    $\begingroup$ 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... $\endgroup$ – poncho Dec 13 '20 at 17:31
  • $\begingroup$ 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. $\endgroup$ – fgrieu Dec 13 '20 at 17:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.