Security of a given hash function

Question

We have a message denoted $M$. Let us suppose that we have a collision-resistant hash function $h_0$ with output length $n$. We then consider two other independent (different) hash functions $h_1$ and $h_2$, with output length $n/2$. For instance, we can choose SHA-256 for $h_0$, and SHA-256 with a truncated output (128 bits) for $h_1$ and $h_2$. Note that $h_1$ and $h_2$ are obtained by domain separation, i.e. $h_1=\operatorname{lsb}_{128}(\mathrm{SHA256}(M\| 1))$ and $h_2=\operatorname{lsb}_{128}(\mathrm{SHA256}(M\|2))$.

We now consider the hash function $h_3$: $$h_3(M)=h_1(h_0(M)) \| h_2(h_0(M))$$

I have read that the concatenation of two independent hash functions appied on the same message does not increase the security when the message is long. What about the above $h_3$ function, when compared to $h_0$? In terms of collision-resistance and second-preimage resistance.

Answer 1

$h_3$ is at most as collision and 2nd-preimage resistant as $h_0$.

Proof:
Suppose we have a collision for $h_0$, that is, we know $x\neq y$ with $h_0(x)=h_0(y)=h$. Now observe that $h_3(x)=h_3(y)$ as follows: $$h_3(x)=h_1(h_0(x))\parallel h_2(h_0(x))=h_1(h)\parallel h_2(h)=h_1(h_0(y))\parallel h_2(h_0(y))=h_3(y)$$

---

Now that we have established that $h_3$ cannot be more secure than $h_0$, let's look at the "lower bound". Let $c_i$ be the boolean variable that indicates that a collision on hash function $h_i$ is known. Then the following holds: $$c_3\rightarrow c_0\oplus(c_1\land c_2)$$ (with $\oplus$ denoting XOR)

That is, $h_3$ is at least as secure as $h_0$ or ($h_1$ and $h_2$). This assumes there are no subtle interactions between the hash functions which would facilitate a structure-lead collision search.

Suppose we have a collision on $h_3$, that is we know $x\neq y$ such that $h_3(x)=h_3(y)$. $h_3(x)=h_3(y)$ implies that $h_1(h_0(x))=h_1(h_0(y))$ and $h_2(h_0(x))=h_2(h_0(y))$ (by simple decomposition) and so we would have found a collision on $h_1$ with the values $h_0(x)$ and $h_0(y)$ and a collision on $h_2$ with the same values. This assumes that $h_0(x)\neq h_0(y)$ is allowed to be called a proper collision. If this is not the case we would have found a collision on $h_0$ instead. So we have $c_0\oplus (c_1\land c_2)$ being true, deduced from $c_3$ being true.

Actually the right-side of the found collision is worth "more" than a normal collision on a hash function. Because we have found a collision on both hash functions, which is equivalent to finding a collision on $h'(M)=h_1(M)\parallel h_2(M)$ which with the constraints given in the question has $n/2$ bit security.

---

So what does all of the above mean?

• If you can break $h_0$ you can break $h_3$.
• If you can break $h_3$ you can either break $h'$ or $h_0$.
• If either $h_1$ or $h_2$ is a permutation, then breaking $h_3$ is exactly as hard as breaking $h_0$.
• If you can break $h'$ you can trivially break $h_1$ and $h_2$.
• Two "normal" collisions on $h_1,h_2$ are very likely not sufficient to break $h'$.
• A collision on $h'$ very likely does not yield a collision on $h_3$ (because you would still need to find a pre-image with respect to $h_0$).
• If $h_0,h_1,h_2$ lack structural weaknesses, $2^{n/2}$ operations are required to break $h_3$ (which is the expected value).

Reading hint for the uninitiated: "if you can break x then you can [logical formula involving breaks of $y_i$]" needs to be negated on both sides and then the sides need to be swapped for a security statement. That is "if [negated logical formula] is secure, so is x".