Popular attacks on cryptographic hash algorithms are "birthday attacks" . At high level ,

if a hash function produces $n$ bits of output, an attacker who computes only $2^{n/2}$ hash operations on random input is likely to find two matching outputs

Is the same true for HMAC ? Or are HMAC with any underlying Hashing (like MD5/SHA-2) prone to birthday attacks ? If not why not ?

Note : this question is not a duplicate of What are the implications of a birthday attack on a HMAC?

  • $\begingroup$ How are you using HMAC? Just as a PRF/MAC? $\endgroup$ Commented Aug 10, 2016 at 16:39
  • $\begingroup$ Just as MAC not as PRF $\endgroup$
    – sashank
    Commented Aug 10, 2016 at 17:35
  • $\begingroup$ @CodesInChaos am curious will the answer change if HMAC was used as a PRF ? $\endgroup$
    – sashank
    Commented Aug 11, 2016 at 4:34
  • $\begingroup$ No, but it'd change if you used it without a key. $\endgroup$ Commented Aug 11, 2016 at 5:49

1 Answer 1


Is the same true for HMAC ?

Yes, HMAC outputs are hashes of something so after $2^{n/2}$ you expect two to match.

However, this alone does not help the attacker. The attacker cannot compute the MAC value themselves, so they need to wait for the user to generate that many values. And it does not amount to a forgery attack because the attacker cannot produce a MAC value for any other message than the ones for which they have already seen them.

Even if the attacker had a collision attack on the underlying hash that alone would not help. HMAC is provably secure under some lesser assumptions (second preimage resistance and pseudorandomness, say).

So yes the "birthday paradox" applies to HMAC, but no that does not mean an attack.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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