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$ – CodesInChaos Aug 10 '16 at 16:39
  • $\begingroup$ Just as MAC not as PRF $\endgroup$ – sashank Aug 10 '16 at 17:35
  • $\begingroup$ @CodesInChaos am curious will the answer change if HMAC was used as a PRF ? $\endgroup$ – sashank Aug 11 '16 at 4:34
  • $\begingroup$ No, but it'd change if you used it without a key. $\endgroup$ – CodesInChaos Aug 11 '16 at 5:49

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, privacy policy and cookie policy

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