# Is finding a three way hash collision infeasible [duplicate]

Is there an equivalent to the birthday paradox for more than 2 messages.

Solving Hash(x) = 0 takes $$2^{bits}$$ steps on average

Solving Hash(x) XOR Hash(y) = 0 takes around $$2 ^{bits/2}$$ due to the birthday paradox.

Is there an algorithm that can solve Hash(x) XOR Hash(y) XOR Hash(z) = 0 in $$2^{bits/3}$$ steps (or similar)?

If so, does it get easier to find a solution if you add more terms?

 The second post by Squeamish Ossifrage is what I was looking for, thanks.

• Actually, I guess this is more like crypto.stackexchange.com/q/48333 since $H(x) + H(y) + H(z) = 0$ is not the same as $H(x) = H(y) = H(z)$, which is what the Joux multicollisions paper is about. See Wagner's generalized birthday paper for more details. Nov 5 '19 at 23:35
• Here is the first link provided from Squeamish, which is a similar question but not a complete dupe. Nov 6 '19 at 1:14
• Further, note that solving the 3XORSUM problem $H(x) \oplus H(y) \oplus H(z) =0$ is open, in the sense of finding an algorithm with complexity less than $2^{n/2},$ and approaching $2^{n/3}.$ Wagner's algorithm gives relatively efficient solutions for $k$ a power of two, when we consider $H(x_1)\oplus H(x_2) \oplus \cdots \oplus H(x_k)=0.$ Nov 6 '19 at 23:29
• See the following related questions to 3XORSUM. cstheory.stackexchange.com/questions/37233/… and cstheory.stackexchange.com/questions/42246/… Nov 6 '19 at 23:32