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

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

• Not always, but in practice it will often be even for relatively weak hashes $h_2$. The most important property required of $h_2$ is that preserves at least $2n$ bits of entropy, where $n$ is the target security level. (even that's not sufficient in pathological cases) Dec 3, 2013 at 13:07
• "Uniformly distributed" over what? $f(x)=0$ is uniformly distributed over its image of $\{0\}$. Dec 3, 2013 at 13:24

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\}^*$

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

• Ironically, $H_2(x)$ is collision resistant if you assume the appropriate security claim for the output domain: $1$.
– orlp
Dec 3, 2013 at 15:38