3
$\begingroup$

I'm reading the fourth edition of "Cryptography: Theory and Practice" by D.R. Stinson and M.B. Paterson. In the book, they have mentioned the concept of "collision-resistant hash" and I've stumbled upon the following question from another source:

Is there a collision resistant hash function $h(x)=h_1(x)\oplus h_2(x)$ so that $h_1$ and $h_2$ are not collision resistant?

It seems interesting to think about it, but I couldn't find any relevant answers for this topic…

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ HINT: Consider a 256-bit hash function where the last 128-bits of output are all set to zero. $\endgroup$
    – Daniel S
    Dec 1, 2022 at 17:31
  • $\begingroup$ Nice solution :) Thank you! $\endgroup$
    – Dniel BV
    Dec 1, 2022 at 18:47
  • 1
    $\begingroup$ @DnielBV Considering answering the question yourself using the hint. $\endgroup$
    – JAAAY
    Dec 1, 2022 at 20:55
  • $\begingroup$ @JAAAY This is considered a homework question, so we only provide hints in comments, see our current homework policy $\endgroup$
    – Maarten Bodewes ♦
    Dec 2, 2022 at 12:24
  • 1
    $\begingroup$ It is worth noting that the current hint gives a quite inefficient example, in terms of the work factor to produce new collisions for the component hashes. One can construct examples where generating collisions for the components is essentially free (hint: think about preimages of zero). $\endgroup$
    – Polytropos
    Dec 4, 2022 at 7:30

1 Answer 1

Reset to default
2
$\begingroup$

Let $g$ be a collision-resistant hash. We build $h_1$ to be $g$ with the first half replaced with all zeros, and $h_2$ to be $g$ with the second half replaced with all zeros. Neither are collision-resistant as both have effectively half the bit strength they should. Yet their XOR is exactly $g$ we assumed to be collision resistant.

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.