# With HMAC, can an attacker recover the key, given many known plaintext/tag pairs?

Given many pairs of $(m, t)$, can the attacker compute the key $k$ satisfying $\text{HMAC}(k,m) = t$? (Assume that $k$ was chosen at random.)

-
No, since HMAC is believed to be secure. $\;$ –  Ricky Demer May 30 at 20:27
Anyone cares to comment on the downvotes? –  Eugen May 31 at 11:38
@Eugen, people expect you to do some independent research of your own to try to answer your own question, and show your work (show what you've tried so far). In this case, reading an elementary textbook that describes chosen-plaintext attacks and describes the theory of message authentication codes should be enough for you to work out the answer on your own. –  D.W. Jun 2 at 4:20
Well, I did read some elementary work on MAC and HMAC. However I couldn't find somewhere an analysis of the question I am asking. Note I am not asking the recoverability of the input message. Nor I am asking about the probability of tag collisions (which in case of HMAC is given by the generic birthday attack). I wonder why some users make so many assumptions about the people that ask questions.. In any case @D.W. thank you for at least commenting on the question. –  Eugen Jun 2 at 9:00
Another reason for my downvote is that the title does not match the body of the question. I fully agree to this answer, and that it answers the question as worded in its body. But I would not be so sure the question in the title can be answered with no, or at all. Revealing one $m$ and even the low-order bit of $HMAC(k,m)$ "leak information" on $k$ in some sense, for about half the $k$ can be eliminated. –  fgrieu Jun 3 at 7:03

No. Assuming HMAC is secure against known-plaintext attacks (which is a plausible assumption), the key cannot be recovered. This follows directly from the definition of a known-plaintext attack; if you could recover the key, you would have a successful known-plaintext attack on HMAC.

-
This is only true if the effective key space is actually large enough to avoid brute-forcing, though. –  Paŭlo Ebermann Jun 3 at 18:43
@PaŭloEbermann, I don't think that's right. If the key space is too small, then it's not secure against known-plaintext attacks. If you know that it is secure against known-plaintext attacks, then you know that the key space has to be large enough to avoid brute-forcing. –  D.W. Jun 3 at 18:59
Yes, my comment was meant as "your assumption is only true if ...". Sorry for the confusion. –  Paŭlo Ebermann Jun 3 at 19:10