# 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. –  tomp 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.

Kudos to Qiaochu Yuan for the help.

(be free to comment or edit)

-

In WEP, encryption is done by XORing some stream cipher (RC4), and CRC is used as a signature (can't remember if CRC is applied before or after encryption). Since both operations commute, you can modify a packet by XORing and then fix the signature, without ever knowing the key (or the parts of the packet you didn't modify).

CRC is often used as a hash function, although nowadays MD5 is more common. CRC is linear, and WEP is a case where that's a problem (even checksum would've been better).

-