1. Is the probability of distinguishing HMAC from a random oracle is the same as the probability of forging HMAC?

2. Can we say that the following statement is trivial?

$$\Pr[\text{Forging \operatorname{HMAC}_k(m)}] \geq \Pr[\text{Forging \operatorname{HMAC}_{f(m)}(m)}]$$

where $$f(\cdot)$$ is a random oracle and $$k$$ is a random number.

3. Can we use equality in the above statement?

This is not a homework exercise. I think they are trivial but I am afraid if I am wrong.

• Depends on the properties of $m$ and if $m$ could be known, of course. Nov 18 '19 at 4:00
• When you use the technical term ‘random oracle’, that suggests you are modeling an adversary as an algorithm with access to the random oracle. But in that case, part (2) of your question doesn't make sense, because forgery is trivial for such an adversary: there are no secrets from the adversary in computing $\operatorname{HMAC}_{f(m)}(m)$. Maybe you meant where $f$ is a uniform random function known only to the user, in which case the equation is obviously true—it's as if the user has a secret key for every message, so it can't be easier to forge than for just one secret key. Nov 18 '19 at 6:07
• For part (1), it sounds like you might really mean to ask whether PRF security is the same as MAC security, if I read ‘random oracle’ as ‘uniform random function’. In general, the answer is no: if $m \mapsto F_k(m)$ is a good MAC or a good PRF, then $m \mapsto F_k(m) \mathbin\| 1$ is still a good MAC because it resists forgery but it's a bad PRF because it's trivially distinguishable from a uniform random function. But we conjecture that HMAC (with a reasonable choice of hash function) is a good PRF and so it must also be a good MAC—its PRF security can't be higher than its MAC security. Nov 18 '19 at 6:11
• On the other hand, maybe I guessed wrong, and maybe you're actually asking about the HMAC construction's random oracle indifferentiability, which is a slightly different kettle of fish. (Obviously, all this depends on instantiating HMAC with a reasonable choice of hash function like SHA-256, and not, say, 2-pass Snefru.) Nov 18 '19 at 6:14
• @SqueamishOssifrage. Thanks for the comments. Do you know what the probability of forging HMAC-SHA256 with 128 key is?
– Reza
Nov 18 '19 at 13:50