Examine whether a hash function is collision-resistant

Question

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.

Answer 1

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!

Answer 2

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)