Doubt about the possible attacks on HMAC

Question

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?

Answer 1

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