Suppose I have encrypted messages sent to a device authenticated with a MAC keyed with a strong shared cryptographic key. This device can only process so many messages per unit of time. This cryptographic key is renewed every few seconds: a new key is independently created and the previously one is destroyed.

Does this actually have any effect on the difficulty of an attacker to forge a message with a valid MAC? I originally thought it did since any computational effort spent for a key would be wasted once the key is renewed, but it occurred to me that it's not really possible to attack a MAC in a structured way (otherwise it would be broken); tags are just tried at random until a valid one is found, independently of the key.

Am I right in saying that constantly changing the key does not help with increasing the strength of a MAC? If not, can I shorten the MAC for these messages and achieve equivalent security against forgery to a larger MAC length due to the use of short-lived keys?

  • $\begingroup$ time, data processed per message, and message count can all make a difference in MAC key recovery, and the amounts vary with the MAC construction, the key size, and the tag size $\endgroup$ Jan 29, 2016 at 7:59

1 Answer 1


This depends on the MAC because there are different kinds of attacks to consider.

  1. If the best attack is randomly trying authentication tags, then the key does not matter.
  2. If the best attack is brute forcing the key, then key renewal does mean that the attacker has to "start anew", but as long as the key space is large enough that the probability of finding the key is small, that probability does not decrease all that much.
  3. If the MAC is broken and admits other attacks, then key renewal may make attacks more difficult (e.g. if a large number of known MACs are needed) or easier (e.g. if some keys are weak).

MACs such as SipHash or many AES-256-based MACs fall under the first case. It is much faster to randomly guess a correct MAC value than guess a correct key, because the key space is larger than the tag space.

On the other hand, HMAC is sometimes used with a key that is shorter than the output (e.g. 128-bit key and HMAC-SHA-256). If the MAC tag is not truncated, then the fastest known attack is brute forcing the key. This is the second case.

Regarding the third case, one example is MAC misuse, such as CBC-MAC with variable length messages, which becomes secure if you renew the key on every message. A short AES-GCM tag is also secure as long as you do not reuse the key too many times.

  • $\begingroup$ Thanks for the answer! So assuming the MAC is not broken, are (1) and (2) the only possible best attacks, depending on whether or not the tag is shorter than the key? $\endgroup$
    – Thomas
    Feb 7, 2016 at 0:51
  • $\begingroup$ @Thomas, basically, yes, though like the GCM MAC I mentioned in the answer, many MACs (that are not considered "broken") have limits on key use which you must follow to not allow other attacks $\endgroup$
    – otus
    Feb 7, 2016 at 8:22

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.