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?

$\endgroup$
  • 3
    $\begingroup$ Look at the criteria for a cryptographically good hash function and test whether h satisfies them. $\endgroup$ – Qiaochu Yuan Nov 8 '10 at 13:41
  • 1
    $\begingroup$ As an aside, this is the sort of "hash" function used in WEP. $\endgroup$ – Yuval Filmus Nov 8 '10 at 13:43
  • $\begingroup$ @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. $\endgroup$ – Tom Pažourek Nov 8 '10 at 17:37
  • 1
    $\begingroup$ @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. $\endgroup$ – Qiaochu Yuan Nov 8 '10 at 17:45
  • 1
    $\begingroup$ @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. $\endgroup$ – Qiaochu Yuan Nov 8 '10 at 19:00
2
$\begingroup$

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)

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.