MAC size: Should MAC be shorter than cipher block size? 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?
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 &lt; 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.