# Security of message authentication codes and tag size

The obvious way to attack a MAC is to try every key; therefore, if we use an n-bit key we need $2^n$ steps to break it.

But we can also try every tag in order to find the correct one, and in some concrete scenarios (e.g. CBC-MAC with AES-256) the tag is smaller than the key.

Does this mean that a MAC with n-bit keys and t-bit tags will offer $\min(n,t)$ bits of security, or is there something wrong with this reasoning?

• If you don't have the key, how can you make sure that a t-bit tag is the correct one? – M.S. Dousti Feb 25 '11 at 20:18
• I'm assuming the attacker can send many (message,tag) pairs to be checked by the victim. I'm aware that this isn't normally covered by the usual definition of a secure MAC but it doesn't seem too far-fetched. – Conrado Feb 26 '11 at 2:25

## 1 Answer

Theoretically, that is correct. Given your approach, the attacker needs to try $2^t/2$ tags on average, while to find the key, he needs to try $2^n/2$ keys on average. In CBC-MAC with AES-256, we have $t=128$. Therefore, the adversary needs to try about $2^{128}/2=2^{127}$ tags to find the correct one. While in this case the brute force needs much less effort than trying to break the key itself (which amounts to $2^{255}$ trial-and-errors), it is still far beyond the current computing power of supercomputers.

It is worth noting that, we usually take any scheme whose best attack needs at least $2^{80}$ operations as secure. (I read this somewhere, but forgot the reference. Sorry!)

• I agree that in the practical sense they are secure, but theoretically speaking this means that it does not make any sense to use CBC-MAC with AES-256 instead of AES-128. Interesting... thanks for the answer. – Conrado Feb 28 '11 at 17:35
• I don't think this is quite right. With AES-128 an attacker can get a few message/tag pairs, do $2^{128}$ work, find the key, and output an almost guaranteed forgery. With AES-256 an attacker can output a random tag that will be a correct forgery with probability $2^{-128}$ (or invest $2^{256}$ work to search for the key). These are not comparable. – user686 Aug 3 '11 at 0:32
• @user686: I'm afraid I didn't get you, but I comment on what I "suspect" to be what you meant: I wasn't comparing AES-128 and AES-256; rather, I just mentioned AES-256. (Note that while the key-size for AES-256 is 256 bits, its block-size is 128 bits and not 256 bits). – M.S. Dousti Aug 3 '11 at 10:45
• To be more clear: in a MAC with $t$-bit tags and $n$-bit keys there are two attacks: (1) Exhaustive key search. This takes time $2^n$ and succeeds with probability (essentially) 1. (2) Guess a random tag. This takes $O(1)$ time but succeeds with probability $2^{-t}$. These are incomparable. – user686 Oct 12 '11 at 3:42