Doubt about the possible attacks on HMAC

I have a question about the security of HMAC:

• If I know the value of the seed and the value of the HMAC but I don't know the key then I can't do the birthday attack because I can't generate an authentic message. I must see at least $2^{\frac{n}{2}+1}$ messages to have 50% of probability to find a collision.
• But what happens if I have the seed, the value of HMAC, and the key?
• HMAC has two inputs: key and message. What's the question's "seed"? What's the attacker goal: generate an authentic message (the usual goal against a MAC, including HMAC) , or generate two distinct messages with the same HMAC? – fgrieu Feb 10 '18 at 9:42
• Hi! [image.slidesharecdn.com/… the seed is the "IV" in this image! For the second question: I think the attacker wants to generate another fraudolent message so HMAC(original message)=HMAC(fraudolent message) – Serena89 Feb 10 '18 at 10:16

1 Answer

The standard attack model for a MAC is that the attacker, not knowing the key, is allowed to ask the MAC for any messages s/he wants, and succeeds if later exhibiting a different message and its MAC that have probability sizably better than $2^{-n}$ to be correct.

Studying the birthday problem tells that that after $2^{\frac{n}{2}+1}$ random messages, probability is good (better than 86%) that two messages have the same MAC. But, for an ideal MAC, this is of no help to the attacker, because s/he has no clue about which messages collide before having asked the MAC of both, which invalidates these message as contributing to a successful attack. We have proof that this applies to HMAC, if the underlying hash function has suitable properties; see Mihir Bellare, New Proofs for NMAC and HMAC: Security without Collision Resistance, in Journal of Cryptology, 2015 (originally in proceedings Crypto 2006).

With the key, attacking any MAC is trivial: it's only a matter of computing the right MAC.

If for some reason we change the attack model and consider than the adversary wants to exhibit distinct messages with the same (H)MAC, knowledge of the key helps doubly:

• The attacker no longer needs to ask MACs; s/he can compute them, presumably at a higher rate and without raising suspicion.
• In the particular case of HMAC, that is likely to allow exploiting weaknesses (if any) of the underlying hash $\operatorname H$; specifically, with knowledge of the key $K$, it might be possible to find $M$ and $M'\ne M$ with $\operatorname H\big((K\oplus\text{ipad})\|M\big)=\operatorname H\big((K\oplus\text{ipad})\|M'\big)$, and it will follow that $\operatorname{HMAC-H}(K,M)=\operatorname{HMAC-H}(K,M')$. That would be trivial for $\operatorname H=\operatorname{MD5}$, and possible for $\operatorname H=\operatorname{SHA-1}$, given the weaknesses of these hashes (which include allowing to find colliding messages starting with any known prefix, very quickly for $\operatorname{MD5}$, feasibly for $\operatorname{SHA-1}$).
• Perfect! if the attacker knows k, he will have to make a brute-force attack by computing the hash function on every possible message he generates until he finds a collision! – Serena89 Feb 10 '18 at 15:24
• If the attacker knows $K$ and is after collisions for some mysterious reason, he can make a brute-force attack by computing the hash function on messages he generates until he finds a collision. Further, for some hashes including MD5, he has a much better option, as stated in the last point. – fgrieu Feb 10 '18 at 15:53