3
$\begingroup$

Many sources claim that (if possible) a length of MAC should be as long as possible. So it should have the same size as size of the block of used cipher.

However there is the following note in Bouncy Castle source codes (CMac.java):

"Note: the size of the MAC must be at least 24 bits (FIPS Publication 81), or 16 bits if being used as a data authenticator (FIPS Publication 113), and in general should be less than the size of the block cipher as it reduces the chance of an exhaustive attack (see Handbook of Applied Cryptography)."

Should MAC really be shorter, and if so, what is the "sweet spot"?

Or is that true only under some special circumstances?

$\endgroup$
6
$\begingroup$

Or is that true only under some special circumstances?

This statement is based off of Remark 9.60 of the Handbook of Applied Cryptography (PDF of chapter 9) which reads as when talking about the strongly related CBC-MAC:

Remark (truncated MAC outputs) Exhaustive attack may, depending on the unicity distance of the MAC, be precluded (information-theoretically) by using less than $n$ bits of the final output as the m-bit MAC. (This must be traded off against an increase in the probability of randomly guessing the MAC: $2^{−m}$.) For $m = 32$ and $E = \operatorname{DES}$, an exhaustive attack reduces the key space to about $2^{24}$ possibilities. However, even for $m < n$, a second text-MAC pair almost certainly determines a unique MAC key.

So the idea behind this remark seems to be: If you are given only a single message-tag pair, and you truncate the tag, you cannot possibly find the the right key that produced this tag, because many keys will produce this truncated tag. However as you see more message-tag pairs, this advantage fades away as there are lesser and lesser keys producing the right tags on all these pairs. Also note that assuming you filter the entire keyspace for the first tag to get candidates for the second run, you have to perform $2^k$ operations and will get significantly less than $2^k$ keys in return on which another brute-force attack should take negligible time as the time is dominated by the primary brute-force and that stays true for truncated and non-truncated MACs.

TL;DR: Truncating tags in this case can make brute-force a little bit harder, but it's a case of "infeasible" versus "infeasible", so rather don't truncate and enjoy the ideal anti-forgery probability.

$\endgroup$
  • 2
    $\begingroup$ To add to this correct answer, the correct way to protect the MAC key is to use one that is sufficiently long (e.g. at least 128 bits) that guessing it is infeasible to do a brute-force search, even if the attacker can easily recognize the right one should he happen to stumble onto it. $\endgroup$ – poncho Mar 28 '18 at 17:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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