I am using HMAC-SHA256 with a 128-bit key. Assume my key generator leaks some information to an adversary. Hence, the adversary can predict the key with probability $\alpha$. Can I say that the adversary can forge a valid (message,tag) pair with probability $\alpha$?
1 Answer
$\begingroup$
$\endgroup$
7
[Suppose] the adversary can predict the key with probability $\alpha$. Can I say the adversary can forge a valid (message,tag) pair with probability $\alpha$?
It's not quite $\alpha$. Write it out with the chain rule:
\begin{align*} \Pr[\text{forgery}] &= \Pr[\text{forgery} \mathbin\& \text{guessed key}] + \Pr[\text{forgery} \mathbin\& \text{didn't guess key}] \\ &= \Pr[\text{forgery} \mid \text{guessed key}] \Pr[\text{guessed key}] \\ &\qquad + \Pr[\text{forgery} \mid \text{didn't guess key}] \Pr[\text{didn't guess key}]. \end{align*}
Under your premise, $\Pr[\text{guessed key}] = \alpha$, so $\Pr[\text{didn't guess key}] = 1 - \alpha$.
Exercise: Figure out what $\Pr[\text{forgery} \mid \text{guessed key}]$ and $\Pr[\text{forgery} \mid \text{didn't guess key}]$ are. Hint: Model HMAC-SHA256 as a uniform random function. What's the probability any two prescribed inputs $m \ne m'$ collide under a uniform random function? (Then add a term at the end for the distinguishing advantage of the adversary against HMAC-SHA256.)
answered Oct 31, 2019 at 3:51
-
$\begingroup$ Thanks for the response. Is not $\Pr[\text{forgery} \& \text{didn't guess key}]=\operatorname{negl}(1^{128})$ ? If yes, we can assume $\Pr[\text{forgery}\&\text{guessed key}]=\alpha$ and $\Pr[\text{forgery}\mid \text{guessed key}]=1$? $\endgroup$– RezaOct 31, 2019 at 4:01
-
$\begingroup$ Yes. If you're ignoring ‘negligible’ terms then it's fine to say the answer is $\alpha$, but usually it's clearer to write $1/2^{256}$ or $1/2^t$ for a $t$-bit tag (in the random oracle model for HMAC-SHA256), since we're not in an asymptotic regime here, and sometimes the constant factors can bite you in ways you might not have expected if you think of everything asymptotically. Concrete security is what really matters; asymptotic analyses are at best a rough proxy for it. $\endgroup$ Oct 31, 2019 at 4:54
-
$\begingroup$ Thanks, again. Is there any reference for " HMAC-SHA256 is a uniform random function"? $\endgroup$– RezaOct 31, 2019 at 12:17
-
$\begingroup$ @Reza HMAC-SHA256 is (conjectured to be) a pseudorandom function family. That means under a uniform random choice of key, it can't be much different, as far as a computationally bounded adversary can discern, from a uniform random choice of function. It's always easiest to start by reasoning about idealized components, and then just add the PRF advantage at the end when you instantiate them. (In this case that doesn't quite work because the key is not uniform random, but in the random oracle model for SHA-256 in the HMAC construction, it's still a reasonable approximation.) $\endgroup$ Oct 31, 2019 at 14:13
-
$\begingroup$ If adversary has oracle access to Verify function, can we say that the Pr[forgery&didn't guess key] = n/(2^256) where n is the number of times that the adversary queried Verify? $\endgroup$– RezaOct 31, 2019 at 20:21