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

• If you extend this scheme directly to a tree-hash it will be trivially vulnerable to collisions with a different length. That's why tree-hashes typically use a different hash function for inner hashes and leaf hashes. Apr 23, 2012 at 18:27

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)$
• 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.