Consider two sets $A=\{a_1,a_2,\cdots,a_n\}, B=\{b_1,b_2,\cdots,b_m\}$; $m,n$ can be different. we can calculate the xor summation of each element's hash value: $XOR(A)=(hash(a_1)\oplus hash(a_2) \oplus \cdots \oplus hash(a_n))$ and $XOR(B)=(hash(b_1) \oplus hash(b_2) \oplus \cdots \oplus hash(b_m))$. Is it possible that set $A$ does not equal set $B$, yet $XOR(A)=XOR(B)$?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
As for the feasibility of finding such a colliding set, well, as long as the sets are allowed to be relatively long (e.g. at least as long as it bit values being xor'ed), then it is easy.
First off, we assume that the hash output is $n$ bits. Then, we select $n+1$ distinct values $X_i$ and set $\delta_i = Hash(X_i)$. Then, we use linear algebra to find a subset of the values $\{ \delta_1, \delta_2, ..., \delta_n \}$ that xor to $\delta_0$ (note, there is a probability that there won't be such a subset; that probability can be minimized by including a few extra values).
With such a subset $\{ \delta_{z_0}, \delta_{z_1}, ..., \delta_{z_k} \}$, we have $$Hash(X_0) = Hash(X_{z_0}) \oplus Hash(X_{z_1}) \oplus ... \oplus Hash(X_{z_k})$$
That is, the sets $\{ X_0 \}$ and $\{X_{z_0}, X_{z_1}, ..., X_{z_k} \}$ collide
-
1$\begingroup$ Might be useful to note that if you're limited to $k$ values, then the computational hardness is $O(2^{n - k})$, so xor summing hashes is secure when $k$ is small. $\endgroup$ Commented Nov 27, 2018 at 7:29
$\begingroup$
$\endgroup$
2
In the trivial case, take a compressing hash function $hash$ then there must exist a collision i.e. $ \exists a \neq b $ such that $ hash(a) = hash(b)$. Therefore, $ A = \{a\} $ and $B=\{b\}$ with $A \neq B$ yet $XOR(A) = XOR(B)$. This says nothing about how easy it is to find this collision if the hash function is collision resistant, but it does exist.
-
$\begingroup$ I know we can always find a colision of a hash. But I want to proof that the probability of this case XOR(A)=XOR(B) is very small, which is computationally infeasible to find. $\endgroup$ Commented Jan 31, 2018 at 12:40
-
1$\begingroup$ Then you should formulate your question differently, as it currently explicitly asks for the possibility of having $XOR(A)=XOR(B)$, not for its probability, nor for the computational hardness of finding such sets. $\endgroup$ Commented Jan 31, 2018 at 14:37