Suppose there are two collision-resistant hash functions $h_1$ and $h_2$ with output sizes of $n_1$ and $n_2$ respectively.
Is $H'(x) = h_1(h_2(x))$ collision resistant for the different relationships between $n_1$ and $n_2$?
This has been boggling me and my colleagues for the past few days since two different approaches contradict each other:
1st approach:
Based on the definition of collision resistance $H'$ has an output of $n_1$ length and so if we can find an attack with less complexity than $\mathcal O(2^{n_1/2})$ it is not collision-resistant.
We want $$\mathcal O(2^{n_2/2}) < \mathcal O(2^{n_1/2}) \implies \ldots \implies n_2 < n_1$$
So if $n_2 < n_1, H'$ is not collision resistant and in other cases it is
2nd approach:
Let's suppose $H'$ is not collision resistant.
Then there exist different $x_1$ and $x_2$ so that $H'(x_1) = H'(x_2)$ i.e. $h_1(h_2(x_1)) = h_1(h_2(x_2))$
That can happen if $h_2(x_1) = h_2(x_2)$, but $h_2$ is collision resistant
It can also happen if $h_1(A) = h_1(B)$ where $A = h_2(x_1)$ and $B = h_2(x_2)$ but $h_1$ is collision resistant.
We have proved that $H'$ is collision-resistant and the relationship of $n_1$ and $n_2$ doesn't matter.