# Security of HMAC against an eavesdropper

Assume we are using HMAC-SHA-256 with 128-bit key for authenticating our messages, and an adversary has eavesdropped $$n$$ (message, tag) pairs.

If the adversary wants to forge a tag for a message $$m'$$, (I think) he has two options:

1. Output a random number;
2. Output one of the eavesdropped tags

I think the probability of success in the first option is $$1^{-256}$$. In the second option, the probability of success is $$1^{-128}$$ (birthday paradox).

Am I correct?

• sounds like it would be easier (although infeasible) to brute force the key and forge ANY message with probability of 1 – Richie Frame Nov 1 at 3:37
• There is a birthday issue involved here because of HMAC, but it involves an imperial turdload of queries to the oracle—that is, $n$ has to be near $2^{128}$ for it to matter; the advantage has an $n^2\!/2^{256}$ term in it from the birthday issue here. – Squeamish Ossifrage Nov 1 at 4:02
• Aside from that issue with HMAC, hint: model HMAC-SHA256 as a uniform random choice of $2^{128}$ different independent uniform random functions. The adversary might guess the choice of function correctly (with probability $1/2^{128}$), or might not (with probability $1 - 1/2^{128}$). If not, what's the probability that the tag on a message $m$ coincides with (a) the tag on a message $m'$, or (b) an independent uniform random 256-bit string? – Squeamish Ossifrage Nov 1 at 4:04