concerning collision-resistant hash function

Question

Let H, H' be collision-resistant hash functions. Which of the following functions H'' is NOT
necessarily collision-resistant?

1) H''(x) = H(H'(x))

2) H''(x) = H(x)||H'(x), where || denotes concatenation.

3) H''(x) = H(x)||0...0, where || denotes concatenation.

4) H''(x) = H(x) xor H'(x)

My conclusion is the following:

1. H(H'(x)) is the collision resistant as H(x) is collision resistant thus it will return the output as collision resistant.

2. In this there is concatenation of two collision resistant functions thus the output will also be collision resistant.

3. It is also collision resistant as this is just concatenation of collision resistant and 0.'s thus it will also be collision resistant.

4. As H''(x) is the XOR operation thus there could be chances that result of both of them would be same due to which it will always return 0.

Thus it may not be collision resistant.

I appreciate if experts correct me if i am wrong.

Answer 1

When given the question "here's a hash function $H''$ based on a collision resistant hash functions $H, H'$; is $H''$ also necessarily collision resistant?', there are two general ways to answer the question:

1. We can show how, given a collision in $H''$, we can deduce a collision in either $H$ of $H'$. That is, if we were given two values $x \ne y$ with $H''(x) = H''(y)$, could we then immediately give two values $z \ne w$ with $H(z) = H(w)$ or $H'(z) = H'(w)$? If we can, then we can conclude that $H''$ is collision resistant (because if it weren't, that is, if we could find a collision, we'd also find a collision in $H$ or $H'$, and we assumed we weren't able to do that.

2. We can demonstrate a pair of collision resistant functions $H, H'$ (possibly quite artificial ones, but you won't need that here) that, with the construction, make finding a collision in $H''$ easy. This would show that $H''$ needn't necessarily be collision resistant.

It turns out that, for all four examples you gave, demonstrating either 1 (for an answer "yes") or 2 (for an answer "no") is quite straight-forward.

Your homework is to figure out the details...