Does key renewal increase complexity of MAC forgery?

Question

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?

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.