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?

  • $\begingroup$ sounds like it would be easier (although infeasible) to brute force the key and forge ANY message with probability of 1 $\endgroup$ – Richie Frame Nov 1 '19 at 3:37
  • $\begingroup$ 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. $\endgroup$ – Squeamish Ossifrage Nov 1 '19 at 4:02
  • $\begingroup$ 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? $\endgroup$ – Squeamish Ossifrage Nov 1 '19 at 4:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.