1
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\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
    Commented Nov 1, 2019 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
    Commented Nov 1, 2019 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
    Commented Nov 1, 2019 at 4:04

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.