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?
2
-
$\begingroup$ crypto.stackexchange.com/questions/1070/… for $H(k||m)$ might also be of interest. $\endgroup$– archieCommented Nov 11, 2013 at 20:49
-
$\begingroup$ 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. $\endgroup$– user979616Commented Nov 12, 2013 at 2:01
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
