What is the best way to forge a tag for a determined message? Assume a PPT adversary wants to forge a tag for a message. The adversary has oracle access to a verification function. The adversary knows that tags are generated by HMAC-SHA-256 with 128-bit key. I think the best way for the adversary is to randomly choose a key, calculate the HMAC of the message with the chosen key , and check the result with its oracle. Am I right? If so, what is the probability of his success if he tries $m$ different keys? I think it must be:
$$\Pr[forgery]=\sum_{n=0}^{m-1} \frac{1}{2^{128}-n} $$
if I am right, can anyone simplify the sigma better than the following?
$$\Pr[forgery]=\sum_{n=0}^{m-1} \frac{1}{2^{128}-n} &lt; \frac{m}{2^{128}-m} $$
I think it must be:


$$\Pr[forgery]=\sum_{n=0}^{m-1} \frac{1}{2^{128}-n} $$

This is not correct; this can be seen in the simple case where there are four possible keys and you get three guesses.  By the above logic, the probability of guessing the correct key would be $1/4 + 1/3 + 1/2 = 13/12 &gt; 1$, which is absurd (as probability are never greater than 1).  The subtle error you make here is that you can add probabilities only when they are disjoint (and refer to the same event), and in the $m=2$ case (which is the easiest), you're adding a normal probability that the first key is correct ($1/2^{128}$) to the conditional probability that the second key is correct (assuming that the first key is not) ($1/(2^{128}-1)$.

Instead, the correct probability of guesses the correct value (given $m$ guesses), assuming that you will always make $m$ distinct guesses, is:

$$\Pr[forgery] = m / 2^{128}$$

In addition, to be precise, there are actually two ways that the attacker can win.  The first is that, in one of his $m$ guesses of the key, which is what you covered.

The other way he can win is if he selects an incorrect key, however the HMAC of that key just happens to be the right one (by shear chance).  If we assume that HMAC acts like a random oracle, and that we using an untruncated (256 bit) HMAC (I say this because it is quite common to truncate the HMAC output when transmitting it), then (assuming that all the guessed keys are incorrect, and that the adversary checks to see if two of his guesses just happen to be the same, and if so, selects a different key) the probability that we win this way is:

$$m/2^{256}$$

So, the probability that either one of these events occur (and so the attacker wins) is:

$$Pr[forgery] = 1 - (1 - m/2^{128})(1 - m/2^{256})$$

If you want to ignore this second case (which is, in fact, a quite low probability event), and say that it's $m/2^{128}$, well, that's reasonable...