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?

  • 3
    Look at the criteria for a cryptographically good hash function and test whether h satisfies them.2010-11-08
  • 1
    As an aside, this is the sort of "hash" function used in WEP.2010-11-08
  • 0
    @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: http://mathworld.wolfram.com/Collision-FreeHashFunction.html Any advice? I'd be glad to answer my question by myself, but I'm still stuck.2010-11-08
  • 1
    @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.2010-11-08
  • 0
    @Qiaochu Yuan: Thank you for your help. I suppose I can use XOR on $n$ hashes to get the same hash as the one remaining message I didn't use. Then I would have two messages with the same hash, but how can I be sure that the two messages aren't the same message? Or is this sufficient argument that the function is not weak collision-free? I'm not sure that I understand it well.2010-11-08
  • 1
    @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.2010-11-08
  • 0
    @Qiaochu Yuan: "Fair" as an satisfying answer to the question? I'll try later to formulate it as my answer. Anyway, I'm still interested in the violation of the one-wayness property. Could you explain your reasoning? Why is h not one-way simply because we can easily find a zero hash?2010-11-08
  • 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).