1
$\begingroup$

Assume a collision-resistant hash function $h$ which compresses sequences of length $2n$ to length $n$. It must be examined whether the hash function which compresses seqs. length $4n$ to $n$:

$$ h_1(x_1 || x_2 || x_3 || x_4) = h((x_1 \oplus h(x_2 || x_2)) || (h(x_3 || x_3) \oplus x_4)) $$

is collision-resistant or not. ($\oplus$ is XOR, $||$ is concatenation and $|x_i| = n$).

Attempt:

Assume we can easily find two distinct sequences $(y_1, y_2) = (x_1 || x_2 || x_3 || x_4, x_5 || x_6 || x_7 || x_8)$ such that $h_1(y_1) = h_1(y_2)$.

Then, we can easily find $(y_1, y_2)$ such that:

$$ h(g(y_1)) = h(g(y_2)) $$

where $g(y) = g(x_1||x_2||x_3||x_4) = (x_1 \oplus h(x_2 || x_2)) || (h(x_3 || x_3) \oplus x_4)$.

But then, if we can easily find such $(y_1,y_2)$, we can also easily find $(g(y_1), g(y_2))$ and thus $h$ is not collision-resistant.

In case the above argument isn't valid, another idea would be to state that $g(y_1), g(y_2)$ cannot be distinct (with non-negligible probability) since $h$ is collision-resistant and continue with solving $g(y_1) = g(y_2)$ etc until we get $y_1 = y_2$.

It'd be very helpful if someone pointed out to me which of the two (if any) is the correct proof.

$\endgroup$
8
  • $\begingroup$ what do you mean by "collision-free"? $\endgroup$
    – cisnjxqu
    Dec 2 '20 at 8:59
  • $\begingroup$ $h(x)$ is collision-free if it's computationally hard to find $x,x'$ such that $h(x) = h(x')$. In other words, an efficient algorithm (solving a $P$-problem) has negligible probability of finding such $x, x'$. $\endgroup$
    – Paris
    Dec 2 '20 at 9:04
  • 2
    $\begingroup$ Okay, I wasn't sure, because collision-resistant is the terminology I'm used to, since by the pigeon principle $h$ cannot be "free" from collisions. $\endgroup$
    – cisnjxqu
    Dec 2 '20 at 9:05
  • $\begingroup$ Yes, 'resistant' is a more accurate term. $\endgroup$
    – Paris
    Dec 2 '20 at 9:18
  • 5
    $\begingroup$ One of the many nice things at crypto-SE (compared to usenet's sci.crypt) is that it's possible to edit questions and replace a term by a more accurate one. Update: that works in the title too! Hint: one way to solve a problem involving a statement is to prove that it's false by constructing a counterexample. Here you'd assume $h$ is collision-resistant, and nevertheless exhibit a collision for $h_1$. $\endgroup$
    – fgrieu
    Dec 2 '20 at 9:23
1
$\begingroup$

Your proof starts with the correct approach, but $h_1$ is not collision-resistant (CR), and therefore your proof should give you a hint as to why it's not CR.

Edit: I have removed the counterexample, since it should be easy to figure out using the proof attempt below.

Attempt to prove

You want to prove that:

If $h$ is CR, then $h_1$ is CR.

We prove the contraposition of that statement:

If there exists an adversary $\mathcal{A}^{h_1}$ breaking $h_1$, then there exists an adversary $\mathcal{A}^{h}$ breaking $h$.

We want to assume the existence of $\mathcal{A}^{h_1}$ and use it to construct $\mathcal{A}^{h}$.

$\mathcal{A}^{h}$ is playing the CR game, and is supposed to output a collision for $h$. To achieve that, we let $\mathcal{A}^{h_1}$ run. Since by assumption $\mathcal{A}^{h_1}$ has a non-negligible probability of succeeding, it will output a collision of $h_1$ with non-neglibile probability, i.e. a $x^a \neq x^b$ such that $h_1(x^a) = h_1(x^b)$.

We now want to win the CR game against $h$ and construct a collision for $h$ from $x^a$, $x^b$.

We know that $h_1(x^a) = h_1(x^b)$, and $x^a \neq x^b$. Therefore, using your $g(\cdot)$, $h(g(x^a)) = h(g(x^b))$.

There are two cases here:

1. Either: $g(x^a) \neq g(x^b)$

then we immediately find a collision: since $h(g(x^a)) = h(g(x^b))$ and $g(x^a) \neq g(x^b)$, the pair $(g(x^a), g(x^b))$ is a collision for $h$.

2. Or not: $g(x^a) = g(x^b)$

then we have to look further for a collision. by $g(x^a) = g(x^b)$ we know that

$\underbrace{(x^a_1 \oplus h(x^a_2 || x^a_2))}_\text{first part}\ ||\ (h(x^a_3 || x^a_3) \oplus x^a_4) = (x^b_1 \oplus h(x^b_2 || x^b_2))\ ||\ (h(x^b_3 || x^b_3) \oplus x^b_4)$.

By $x^a \neq x^b$ we know that at least one of these 4 cases must hold:

2.1. $x^a_1 \neq x^b_1$

By $g(x^a) = g(x^b)$, the first part of the input of the outer $h$ must be equal:

$x^a_1 \oplus h(x^a_2 || x^a_2) = x^b_1 \oplus h(x^b_2 || x^b_2)$.

This is where the proof breaks down. You cannot construct a collision from this.

2.2. $x^a_2 \neq x^b_2$

2.3. $x^a_3 \neq x^b_3$

2.4. $x^a_4 \neq x^b_4$

Hope I could help!

$\endgroup$
5
  • $\begingroup$ Thanks! One quick last question: if for $h_1$ we had something like: $$h_1(x_1 || x_2 || x_3 || x_4) = h(h(x_1||x_2) || h(x_3 ||x_4))$$ is it valid to apply my second method and yield $y_1 = y_2$? (I'm asking because I want to know if this method works for proving a function collision resistant.) $\endgroup$
    – Paris
    Dec 2 '20 at 10:09
  • $\begingroup$ As far as I can see this is homework and per our policy, we only provide hints for those in the comments. $\endgroup$
    – kelalaka
    Dec 2 '20 at 10:18
  • $\begingroup$ @kelalaka I have removed the counter example, which was likely the solution to the homework. I can remove the complete answer if so desired. However, I feel like seeing how the proof would break down can help you in identifying why something is not true (and this proof would not have fit into the comments). There were also some issues with the askers attempt at proving the statement, so they can learn from the proof attempt laid out here. Do you think it is acceptable to leave the answer as it is now? $\endgroup$
    – cisnjxqu
    Dec 2 '20 at 10:30
  • $\begingroup$ @cisnjxqu there is no remove, it is on the history of the answer and the OP already got it :). In any case, the HW question need not be answered. We had long chat conversions for some OPs to be consistent with our current policy. If you don't like the current policy you can vote against it or write another answer so that the community can upvote or downvote. bests. $\endgroup$
    – kelalaka
    Dec 2 '20 at 10:35
  • $\begingroup$ @kelalaka My question was focused on the verification of the method for proving that a hash function is collision-resistant. Unfortunately, the example I gave was not on point. I wasn't seeking the 'solution' to this specific example, but rather an elaboration on the reasoning. $\endgroup$
    – Paris
    Dec 2 '20 at 11:16

Your Answer

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

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