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

Question

Suppose $h$ is a hash function, $h \colon \{ 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?

Answer 1

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)}

Answer 2

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).

Answer 3

There are some other interesting properties of such a hash function.

• $h(\{0\}^t) = 0$ for any $t$; let $w_2$ be be a string of lenght $t$, then

  \begin{align} h(\{0\}^t \oplus w_2) &= h(\{0\}^t) \oplus h(w_2)\\ h(w_2) &= h(\{0\}^t) \oplus h(w_2)\\ 0 &= h(\{0\}^t) \end{align}

  simple collision exists.

• Generic collision resistance has $\mathcal{O}(2^{n/2})$-time with 50% probability by the birthday attack. What described in the comment and in the aswer for finding collisions is far more costly than the generic collision attack. It has $\mathcal{O}(2^n)$-time.

• Direct collisions exist; let $w_1$ and $w_2$ be two random $t$ length strings then any bit flipping on both strings will have the same hash. Let represent the bit flipping at the position $a$ as $w_1^a$. Then

  $$h(w_1^a) \oplus h(w_2^a) =h(w_1^a \oplus w_2^a) = h(w_1 \oplus w_2) = h(w_1) \oplus h(w_2).$$

  This provides a tremendous number of collisions. For Cryptographical signatures, this is a complete failure to be a good cryptographic hash function.