# 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

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