# Examine whether a hash function is collision-resistant

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.

• what do you mean by "collision-free"? Dec 2, 2020 at 8:59
• $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'$. Dec 2, 2020 at 9:04
• 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. Dec 2, 2020 at 9:05
• Yes, 'resistant' is a more accurate term. Dec 2, 2020 at 9:18
• 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$.
– fgrieu
Dec 2, 2020 at 9:23

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.4. $$x^a_4 \neq x^b_4$$

Hope I could help!

• 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.) Dec 2, 2020 at 10:09
• As far as I can see this is homework and per our policy, we only provide hints for those in the comments. Dec 2, 2020 at 10:18
• @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? Dec 2, 2020 at 10:30
• @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. Dec 2, 2020 at 10:35
• @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. Dec 2, 2020 at 11:16

I am not sure the conlusion on the answer above, it was what it meant to be. Since the answer is old and the writer may be inactive, I am going to point out that:
Assuming that $$h_1$$ is not collision free means $$\exists x, x',\; x \neq x' :\quad h_1(x) = h_1(x')$$ $$h_1(x)= h_1(x') \implies h(g(x)) = h(g(x')) \implies g(x) = g(x')$$ (the last implication due to h being a collision free).
Now $$g(x) =g(x') \implies (x_1 \oplus h(x_2 || x_2)) || (h(x_3 || x_3) \oplus x_4)= (x_1' \oplus h(x_2' || x_2')) || (h(x_3' || x_3') \oplus x_4')$$
Now let me do that only for the right part of the concatenation (it's the same for the left), assuming $$x_1||x_2=x_1'||x_2''$$.
$$h(x_3 || x_3) \oplus x_4)=h(x_3' || x_3') \oplus x_4')\implies \begin{cases} x_4 = x_4' \wedge h(x_3||x_3) = h(x_3'||x_3'), \quad (1)\\ x_4 = h(x_3'||x_3') \wedge h(x_3||x_3)=x_4', \quad (2) \end{cases}$$ Now in case (1) we reach the conclusion that $$x=x'$$ which means that the only chance $$h_1(x)=h_1(x')$$ is $$x=x'$$ .
Now in case (2) we reach the conlusion that we can find an $$x_3'$$ such that $$h(x_3'||x_3')=x_4$$ which would imply that h does not have first input preimage resistance and therefore is not collision free either. In both cases, we contradicted the hypothesis, therefore $$h_1$$ must be collision resistant.

(Please any active member to verify my proof is valid, or offer their advice to make it correct)

• Collision free has little to do with collision resistance. A hash function can by definition not be collision free. (pigeon hole principle). Also note that H1 is not CR because a counterexample exists. Feb 12, 2023 at 20:29