2
$\begingroup$

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?

  • 0
    @tomp: fair as in that's a fair criticism of what I said. It's not obvious that the messages would be different. In any case, part of the definition of a one-way function (as I understand it) is that it should be hard to invert for any choice of element in the range. But this is not true here. More generally if we are in possession of some number of messages and their hashes we can easily take the XOR of any of the messages to get a new message whose hash is known.2010-11-08

2 Answers 2

2

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)

0

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