# Security of a given hash function

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.

$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".

• Thank you SEJPM. what about a lower bound? I suspect a decrease in security since the collision resistance of $h_1$ and $h_2$ are reduced. – Adam54 Sep 13 '17 at 13:48
• @Adam54, I'd have to run through the math. Yes, we can find a collision in either in an expected $2^{64}$ calls to the hash function, so we can find a collision in both in $2^{65}$ calls, but those collisions will (with very high probability) not have the same input, so that would not result in a collision on $h_3$. To get that, we would need multiple collisions on $h_1$ and $h_2$. We would need enough collisions on both to have a high probability of having a collision from the same input under both. – mikeazo Sep 13 '17 at 14:12
• @mikeazo If you think about it, finding the same collision for two hash functions is equivalent to finding a collision on the concatenation of the functions. Which would imply $2^{128}$ work in this case as the output of the concatenation is 256-bit. – SEJPM Sep 13 '17 at 14:24
• @SEJPM, that is what I was assuming, but I wanted to make sure. I'm pretty sure we had a question on here once about finding multiple collisions. I.e., how many calls to the hash function do we need to have $k$ collisions? Can't find it at the moment. – mikeazo Sep 13 '17 at 15:17
• @SEJPM Thank you very much for your answer. I am not sure, I think that I have understood. What is the conclusion of your second paragraph? Can we say that $h_3$ is as secure as $h_0$? The first comment of mikeazo suggests that we should find a huge number of collisions for $h_1$ and $h_2$ in order to find a collision for $h_3$. How can we estimate the overall number of calls? If we want to conclude that $h_3$ has the same collision resistance than $h_0$, we should prove that the "overall" number of calls is about $2^{128}$? Right? – Adam54 Sep 13 '17 at 19:24