0
$\begingroup$
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.

$\endgroup$
  • 2
    $\begingroup$ For 1 and 4, there is no doubt. For 2 and 3, things depend on if the definition of collision resistance asks for a fixed level of resistance (as assumed in the conclusions), or one that grows as $2^h$ where $h$ is the width of the hash. $\endgroup$ – fgrieu Apr 13 at 14:11
  • $\begingroup$ Is this a homework question? $\endgroup$ – kelalaka Apr 14 at 13:59
  • $\begingroup$ Ahmed, we have a specific rule with regards to homework questions. Basically we require some indication that the asker did try and solve the questions for themselves (which, it seems, you did). Furthermore we generally provide hints or partial answers to get you on the way. The question if something is a homework question is therefore relevant - it is just required for us to abide by the rules. $\endgroup$ – Maarten Bodewes Apr 15 at 17:02
2
$\begingroup$

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

| improve this answer | |
$\endgroup$

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.