Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose I have H(M|K) and that H is not weakly collision resistant. If I have a message mac pair (M,MAC), how is it possible to find another message mac pair (M2,MAC2)? My thinking for this problem is that if the hash isn't weakly collision resistant, then I can find another message M2 such that H(M|K)=H(M2|K) and thus, I have a new pair (M2,MAC2). Is this a sufficient explanation for explaining why H(M|K) is insecure if the underlying hash function is weak?

share|improve this question

marked as duplicate by archie, e-sushi, Gilles, rath, Ilmari Karonen Dec 2 '13 at 17:19

This question was marked as an exact duplicate of an existing question.… for $H(k||m)$ might also be of interest. – archie Nov 11 '13 at 20:49
Yes, I am indeed asking the same thing. However, I just wanted to make sure I'm correct in my understanding of what is mentioned there. – user979616 Nov 12 '13 at 2:01
up vote 0 down vote accepted

It's a question about how actual hash functions work. So in the scheme where MAC=H(m||k) in practical terms that's equivalent to doing M=H(m) and then, with the resulting state of the hash function do H(k) starting with the state resulting of doing H(M), so you can see that's possible to find a collision, a m' such that H(m')=H(m), then H(m'|k)=H(m|k) with a cost n/2 bits. HMAC construction reduces substantially (according to wikipedia) the chances of finding such a collision, in fact a collision H(m')=H(m) is useless, so the weakness in this sense of the used hash function has no use.

Note: If $M_i$ are hash function's input blocks and $S_i$ are successive states most hash functions do just $S_i=F(S_{i-1},M_i)$, and the hash result is the last state, making length extension and collision attacks possible.

PD: Let me apologize if the answer is not clear enough. The answer is yes, HMAC can improve a collision weakly hash where H(m|k) does not.

share|improve this answer

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