Question about hash collisions If we have a hash function $h(x)$ and then a hash function $H(X) = h(h(X_0) || h(X_1))$ where $X_0$ is the first half of $X$, $X_1$ is the second half of $X$ and $||$ is concatenation. Then assuming we can easily find a collision for $H$, then it would be easy to find a collision for $h$ as well - Therefore finding a collision for $H$ is as hard as finding one for $h$.

Why is this? I can to some extent understand why that might be the case, but I can't logically connect the dots. Can anyone help me with some logic or math behind it or link to some resources where it is explained. I have tried google, but without the precise correct terminology I'm having a hard time finding the right pages.

Thanks
The general idea is that either one of the inner hashes, or the combining hash must collide, since there is not other place to introduce the collision.

Assume we found a collision for H. This means we have X, Y with $X \neq Y$ such that:

$h(h(X_0)||h(X_1)) = h(h(Y_0)||h(Y_1))$

Now we define: $A = h(X_0)||h(X_1)$ and $B = h(Y_0)||h(Y_1)$

This gives us a new equation h(A) = h(B)


If $A \neq B$, we found a collision, and are done.
If $A=B$ we know that $h(X_0)||h(X_1) = h(Y_0)||h(Y_1)$, which we can split into $h(X_0)=h(Y_0) \land h(X_1)=h(Y_1)$. From $X \neq Y$ follows $X_0 \neq Y_0 \lor X_1 \neq Y_1$. Thus at least one of $h(X_0)=h(Y_0)$ and $h(X_1)=h(Y_1)$ has different inputs on both sides of the equation, and thus represents a collision.