2
$\begingroup$

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

Improve this question
$\endgroup$
7
  • 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-onstrike ♦
    Dec 13, 2020 at 10:28
  • $\begingroup$ Have you tried proving that it's collision resistant? Do you know whether $h$ is CR? $\endgroup$
    – ambiso
    Dec 13, 2020 at 13:16
  • $\begingroup$ yes, h is collision resistant. $\endgroup$
    – user84987
    Dec 13, 2020 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, 2020 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-onstrike ♦
    Dec 13, 2020 at 17:35

1 Answer 1

Reset to default
0
$\begingroup$

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$.
BUT, the question is:
How to show that it is possible to construct a hash function with this property, assuming collision-resistant hash functions exists?

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.