# Is the XOR-combiner of independent keyed hash-functions collision resistant?

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

• What is the origin of this question? The answer is not simple see link.springer.com/article/10.1007/s00145-019-09328-w Jan 3 at 15:55
• @kelalaka It's an exercise for an introductary cryptography course... I'll have a look at the article you linked, thank you! Jan 3 at 17:39
• 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'$? Jan 3 at 19:44
• 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? Jan 3 at 23:02
• Well, are $m\Vert 0$ and $m\Vert 1$ for some fixed $m$ the same message? Do they have the same hash value? Jan 4 at 12:57