2
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Adam54 Sep 13 '17 at 13:48
  • $\begingroup$ @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. $\endgroup$ – mikeazo Sep 13 '17 at 14:12
  • $\begingroup$ @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. $\endgroup$ – SEJPM Sep 13 '17 at 14:24
  • $\begingroup$ @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. $\endgroup$ – mikeazo Sep 13 '17 at 15:17
  • $\begingroup$ @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? $\endgroup$ – Adam54 Sep 13 '17 at 19:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.