# Will XORing two bad hashes lead to a collision resistant hash?

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…

• HINT: Consider a 256-bit hash function where the last 128-bits of output are all set to zero. Dec 1, 2022 at 17:31
• Nice solution :) Thank you! Dec 1, 2022 at 18:47
• @DnielBV Considering answering the question yourself using the hint. Dec 1, 2022 at 20:55
• @JAAAY This is considered a homework question, so we only provide hints in comments, see our current homework policy Dec 2, 2022 at 12:24
• 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). Dec 4, 2022 at 7:30

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.