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 ♦
    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
  • 1
    $\begingroup$ @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) $\endgroup$
    – poncho
    Dec 13, 2020 at 23:06

2 Answers 2

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$
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

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

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