Assume there are two keyed hash-functions $H_1(k_1, m)$ and $H_2(k_2, m)$, with $k_1$ and $k_2$ being independently randomly sampled public keys.

The XOR-combiner is defined as $C_\oplus^{H_1, H_2}:=H_1(k_1, m) \oplus H_2 (k_2, m)$.

Assuming at least one of $H_1$ and $H_2$ is collision resistant, is $C_\oplus^{H_1, H_2}$, as defined above, necessarily collision-resistant for any combination of $H_1, H_2$?

Mittelbach (2014) says: "The exclusive-or combiner is also not robust for collision resistance, even assuming independent functions, as a collision on the combiner does not require collisions under both input functions.", but he's talking about Hash-functions without keys. He also does not provide a proof or counterexample which I could attempt to apply for this problem.

Here's my approach which unfortunately did not lead anywhere:

When attempting a reduction proof, I realized that if an adversary $A$ finds a collision against $C_\oplus^{H_1, H_2}$, that means that $H_1(k_1, m_0)\oplus H_2(k_2,m_0)=H_1(k_1, m_1)\oplus H_2(k_2,m_1)$. However, as Mittelbach (2014) stated, this does not necessarily imply that $H_1(k_1, m_0)=H_1(k_1, m_1)$ or $H_2(k_1, m_0)=H_2(k_1, m_1)$, because it is possible that $H_1(k_1, m_0)\oplus H_1(k_1, m_1)=H_2(k_2, m_0)\oplus H_2(k_2, m_1) \neq 0$.

Unfortunately, I couldn't find a counterexample for $H_1, H_2$ for which I could construct an adversary that breaks collision resistance, leaving me stuck in both attempts of proving and disproving the collision-resistance of $C_\oplus^{H_1, H_2}$.

  • $\begingroup$ What is the origin of this question? The answer is not simple see link.springer.com/article/10.1007/s00145-019-09328-w $\endgroup$
    – kelalaka
    Jan 3 at 15:55
  • 1
    $\begingroup$ @kelalaka It's an exercise for an introductary cryptography course... I'll have a look at the article you linked, thank you! $\endgroup$ Jan 3 at 17:39
  • $\begingroup$ If $H_k$ is collision resistant, then $H'_k(x\Vert b) = H_k(x)\Vert b$ is also collision resistant. (left as an exercise to the reader) What happens if you instantiate both hash functions with $H'$? $\endgroup$
    – Maeher
    Jan 3 at 19:44
  • $\begingroup$ I'm assuming $b$ refers to a single bit? Then $C_\oplus^{H_1', H_2'}=H_1(k_1, m)\|b\oplus H_2(k_2, m)\|b=(H_1(k_1, m)\oplus H_2(k_2, m))\|(b\oplus b)=(H_1(k_1, m)\oplus H_2(k_2, m))\|0$. How would you construct an adversary against this without solving the original problem? $\endgroup$ Jan 3 at 23:02
  • 1
    $\begingroup$ Well, are $m\Vert 0$ and $m\Vert 1$ for some fixed $m$ the same message? Do they have the same hash value? $\endgroup$
    – Maeher
    Jan 4 at 12:57


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.