Is the composition of collision resistant hash with non collision resistant hash a collision resistant hash?

Question

Suppose $h_1$ is collision resistant, and $h_2$ isn't.

Will $h(x)=h_2(h_1(x))$ always be collision resistant?

[Edited:] the output of h2 must be uniformly distributed

Answer 1

Will they always be collision resistant? No

For example, let $h_2(x)=0$. Then, $h(x)=h_2(h_1(x))=0$, which certainly isn't collision resistant.

---

Can it be collision resistant? Yes

For example, suppose we define $h_1(x)=\mathrm{SHA256}(x)$ and

$$ h_2(x)=\begin{cases} 0 & |x|=1 \\ \mathrm{SHA256}(x) & \mathrm{else} \end{cases} $$

Then, since the output of $|h_1(x)|=256$, the composition will leave: $$h(x)=\mathrm{SHA256}(\mathrm{SHA256}(x))$$ Which is believed to be collision resistant from the collision resistance of Sha256.

---

But what if $h_2$ is uniformly distributed across a 'sensible' codomain? As before

_{I add the requirement that it must be uniformly distributed across a sensible codomain since I assume this clarification wishes to prohibit hash functions for which the target space is too small to possibly be secure)}

We can trivially create two examples that demonstrate the above properties. Let $W=\{0,1\}^{256}$. Then, as before let $h_1$ be a cryptographically secure hash function, with $h_1 \colon \{0,1\}^* \to W$ (eg SHA256 as above). Define $h_2(x) = h_1(\mathrm{MSB_{256}}(x))$.

Then $h_2$ is not collision resistant (since for any $x\in W$ and $y\in\{0,1\}^*$ we have $h_2(x)=h_2(x||y)$), but as before $h(x)=h_1(h_1((x))$.

Defining $h_2(x) = h_1(\mathrm{LSB_{256}}(\mathrm{MSB}_{512}(x))$ (ie we extract bits 256->511) we get the composition $h(x)=0$ which is not collision resistant.

_{A slight issue here might be justifying $h_2$ is uniformly distributed, but this comes down to how you attach a distribution to the set of all random strings - ie the distribution taken by $\{0,1\}^*$}

Answer 2

Obviously not. For example, the function $h2(x) = 0$ is not collision resistant, $h2(h1(x))$ shares that property.

This remains true even in less trivial cases; if $h2$ is not collision resistant because its output is too short (it has an $n$-bit output, with $2^{n/2}$ being small enough to do a search over), then $h2(h1(x))$ will also be too short