# Why is hash function $h$ ($h(w_1 \oplus w_2) = h(w_1) \oplus h(w_2)$) not good?

Suppose $h$ is a hash function, $h$ : { 0, 1 } * $\rightarrow$ { 0, 1 } n and for all $w_1$, $w_2$ it holds: $h(w_1 \oplus w_2) = h(w_1) \oplus h(w_2)$.

$\oplus$ is the XOR operation.

Why isn't $h$ a cryptographically good hash function?

• Look at the criteria for a cryptographically good hash function and test whether h satisfies them. – Qiaochu Yuan Nov 8 '10 at 13:41
• As an aside, this is the sort of "hash" function used in WEP. – Yuval Filmus Nov 8 '10 at 13:43
• @Qiaochu Yuan: Thanks, the critieria are: strong collision-free property, weak collision-free property and one-wayness property. I believe that function $h$ breaks the collision-free criteria, but I haven't found any way how to explain why it isn't collision-free. Good definition of collision free property is on MathWorld: mathworld.wolfram.com/Collision-FreeHashFunction.html Any advice? I'd be glad to answer my question by myself, but I'm still stuck. – Tom Pažourek Nov 8 '10 at 17:37
• @tomp: I will give you the following large hint. If you have n+1 or more messages M_1, ... M_{n+1} and their hashes, you can find a collision. – Qiaochu Yuan Nov 8 '10 at 17:45
• @tomp: hmm. That's fair. I guess another criticism is even further back: such an h is not one-way because it is easy to find a message with hash zero. – Qiaochu Yuan Nov 8 '10 at 19:00

The function $h$ violates the one-wayness property of cryptographically good hash functions, because it's not computationally infeasible to recover the message $w$ from the hash $h(w)$.
If we can generate (obtain) a set of message-hash pairs, then we can use the XOR operations on some of the hashes to get the $h(w)$ hash. If we use the same XORing procedure on the corresponding messages, we can recover the message $w$ as well. The whole process is computationally feasible.