2
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ If you don't have the key, how can you make sure that a t-bit tag is the correct one? $\endgroup$ – M.S. Dousti Feb 25 '11 at 20:18
  • $\begingroup$ 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. $\endgroup$ – Conrado Feb 26 '11 at 2:25
2
$\begingroup$

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!)

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Conrado Feb 28 '11 at 17:35
  • $\begingroup$ 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. $\endgroup$ – user686 Aug 3 '11 at 0:32
  • $\begingroup$ @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). $\endgroup$ – M.S. Dousti Aug 3 '11 at 10:45
  • $\begingroup$ 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. $\endgroup$ – user686 Oct 12 '11 at 3:42

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.