# Finding collisions for XOR of many hashes

There's a collision-resistant hash function $$H$$.

Given $$x$$, how hard would it be to find a set $$a[i]$$ such that:

$$H(a[1]) \oplus H(a[1]) \oplus \cdots \oplus H(a[N]) = H(x)$$

whereas none of $$a[i]$$ equals to $$x$$?

• How large is $N$? If it is half as large as the hash function output (in bits), it's easy – poncho Jun 2 '20 at 12:09
• @poncho: N can be arbitrary, but "reasonable", much lower than 2^bits. Let's say for simplicity 1< N < 1000, bits = 256. – valdo Jun 2 '20 at 12:17
• So it's a sort of a birthday attack, but the collision criteria is weaker. Does this have a better solution? – valdo Jun 2 '20 at 12:17
• For bits=256, N=128 is easy – poncho Jun 2 '20 at 13:10
• My guess would be that you should treat the $H$ outputs as random bit-vectors that you want to linearly combine over $\mathbb F_2$ to get $H(x)$. This is a standard problem in linear algebra. – SEJPM Jun 2 '20 at 14:01

This question is studied extensively in the paper

In appendix A, they describe how to break the one-wayness of the function $$H(x_1,\ldots, x_n) = h(x_1) \oplus h(x_2) \oplus \cdots \oplus h(x_n)$$. The idea is as @SEJPM suggests in the comments above: XOR is the operation of a vector space over $$\{0,1\}^\ell$$ (where $$\ell$$ is the output length of $$h$$). Sufficienctly many $$h(x_i)$$'s form a basis for this vector space. Once you have a basis, you can easily solve for a subset of basis vectors that XOR to any desired value.

I had started typing an answer, but @Mikero gave the answer for the regime $$N>\mathrm{bitlength}$$ that you are interested in, which is when the problem is easy to solve.

This answer complements his, for the case $$N$$ is a small constant and the problem is of exponential complexity in the bitlength.

Let $$\ell$$ be the bitlength of the hashes. Assume we have a random set of $$K=2^{\ell/N}$$ hashes. Since here are $$K^N=2^\ell$$ possible $$N-$$sums $$H(a[1])\oplus H(a[2]) \oplus \cdots \oplus H(a[N])$$ we can obtain from this set, with constant probability one of these will hit your $$H(x)$$ since the hash target space has size $$2^{\ell}.$$

If $$\ell=256,$$ and $$N=2$$ this would essentially be the birthday problem with complexity $$O(2^{\ell/2}).$$ By reduction to the case when $$N=2^v$$ is a power of 2 Wagner's paper gave an $$O(2^{\ell/(1+\lceil \log N\rceil)})$$ recursive solution.

No good algorithm is known for $$N=3.$$ The $$N-$$XORSUM problem is relevant to learning parity with noise and to the Equihash blockchain mechanism.