Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
Look at the criteria for a cryptographically good hash function and test whether h satisfies them. –  Qiaochu Yuan Nov 8 '10 at 13:41
1  
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
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. –  Qiaochu Yuan Nov 8 '10 at 17:45
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. –  Qiaochu Yuan Nov 8 '10 at 19:00

2 Answers 2

up vote 2 down vote accepted

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)

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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