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$?

  • $\begingroup$ How large is $N$? If it is half as large as the hash function output (in bits), it's easy $\endgroup$ – poncho Jun 2 '20 at 12:09
  • $\begingroup$ @poncho: N can be arbitrary, but "reasonable", much lower than 2^bits. Let's say for simplicity 1< N < 1000, bits = 256. $\endgroup$ – valdo Jun 2 '20 at 12:17
  • $\begingroup$ So it's a sort of a birthday attack, but the collision criteria is weaker. Does this have a better solution? $\endgroup$ – valdo Jun 2 '20 at 12:17
  • 1
    $\begingroup$ For bits=256, N=128 is easy $\endgroup$ – poncho Jun 2 '20 at 13:10
  • 1
    $\begingroup$ 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. $\endgroup$ – 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.


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.