Is the composition of collision resistant functions H' = h1(h2()) collision resistant?

Question

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.

Answer 1

This has been boggling me and my colleagues for the past few days since two different approaches contradict each other

The reason is that these two approaches assume differing definitions of 'collision-resistant'; these two definitions are not equivalent; that is, we can find functions that meet one definition and not the other.

The first attempt uses the definition 'there is no collision finding attach that takes less that $\mathcal{O}(2^{n/2})$ operations; because $n$ is fixed, we use this as shorthand for 'an attack takes $c2^{n/2}$ operations, for some $c$ not drastically far from 1, and some reasonable definition of operation (in this case, hash function evaluation).

The problem with this definition is that it leads to some absurd conclusions, for example, SHA-256 truncated to 8 bits is 'collision resistant' by this definition. In the other direction, 1kbyte output from SHAKE-256 is not 'collision resistant', because you can find collisions with far fewer than $2^{8192/2}$ hash evaluations.

In contrast, approach 2 uses the definition 'a hash function is collision resistant if we cannot find a collision'. Expressing this formally is a bit tricky (because, as long as the input is allowed to be longer than the output, there must be collisions, we just don't know what they are), and also because this is relative to the computational resources we have (right now, SHA-256 truncated to 200 bits is collision resistant; it might not be 20 years from now as we gain more computational power); on the other hand, it is closer to the intuitive notion of 'collision resistant' that we have.

With this definition, approach 2 could be reworded as 'if we assume $H'$ is not collision resistant, then we know $x \ne y$ with $H'(x) = H'(y)$. Then either $h_2(x) = h_2(y)$ (and hence $h_2$ is not collision resistant, as we know a collision), or $h_2(x) \ne h_2(y)$, in which case we have $h_1(u) = h_1(v)$ for $u = h_2(x), v = h_2(y), u \ne v$ (and hence $h_1$ is not collision resistant, as we know a collision).

Answer 2

I got the chance to ask my professor and he expected the first solution, as the second assumes $ n_1 = n_2 $ (i still don't know why or where it does that).

He also explained that:

• a $n_2$ of 1000 bits that then converts to a $n_1$ of 2 bits is considered collision resistant since you utilize the full security the 2 bits provide i.e. you get all the value that 2 bits that you "paid" for.
• On the contrary a $n_2$ of 500 bits that then converts to a $n_1$ of 1000 bits is not considered collision resistant since you "pay" for 1000 bits of security and only use 500.

This really helped me understand the concept in an intuitive and logical way.