# Key size vs output size of a MAC

What is more important, in terms of security, the size of the MAC or the size of the key that it uses? I'm asking this because I have to answer the following homework question:

What is more secure? A MAC with a 12-byte key and 6-byte MAC length, or a MAC with a 8-byte key and 12-byte MAC length?

For the first one, it's easier to find a pre-image of the result. But for the second one, it's easier to find the key.

• Hint: Is finding pre-images a problem for the security of a MAC (ie can you use it to break the security definition)? – SEJPM Jun 22 '17 at 15:53
• The answer to the quoted question is not well defined. It's trivial to construct pairs of MAC schemes, such that either direction is true. – Maeher May 18 at 9:13

## 1 Answer

The obvious issue is the probability of guessing the key, and the probability of guessing the MAC.

But there's also a qualitative difference. Suppose you have learned a message/authenticator pair $$(m, a)$$ where $$a = H_k(m)$$.

• You can test a guess $$k_0$$ for the key offline by testing whether $$a \stackrel?= H_{k_0}(m)$$.

The feasibility of finding the key $$k$$ depends on how much money the adversary has to commit to an offline key search.

• You can test a guess $$a'_0$$ for the authenticator $$a' = H_k(m')$$ of a forged message $$m'$$ only by submitting $$(m', a'_0)$$ online to the legitimate system and seeing how the legitimate system reacts.

The feasibility of forging an authenticator $$a'$$ this way depends on how much bandwidth the legitimate system has to accept online forgery attempts.