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$
$\endgroup$
8
-
$\begingroup$ How large is $N$? If it is half as large as the hash function output (in bits), it's easy $\endgroup$– ponchoCommented Jun 2, 2020 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$– valdoCommented Jun 2, 2020 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$– valdoCommented Jun 2, 2020 at 12:17
-
1$\begingroup$ For bits=256, N=128 is easy $\endgroup$– ponchoCommented Jun 2, 2020 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$– SEJPMCommented Jun 2, 2020 at 14:01
|
Show 3 more comments
2 Answers
$\begingroup$
$\endgroup$
0
This question is studied extensively in the paper
- A New Paradigm for Collision-free Hashing: Incrementality at Reduced Cost by Bellare & Micciancio
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.
$\begingroup$
$\endgroup$
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.
