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.

  • 2
    $\begingroup$ Hint: Is finding pre-images a problem for the security of a MAC (ie can you use it to break the security definition)? $\endgroup$ – SEJPM Jun 22 '17 at 15:53
  • 1
    $\begingroup$ 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. $\endgroup$ – Maeher May 18 '19 at 9:13

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.

| improve this answer | |

Your Answer

