<p>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.</p>

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

CC BY-SA 2.5
2011-02-28T17:35:27.677Z
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
CC BY-SA 3.0
2011-08-03T00:32:49.790Z
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.
user6584
CC BY-SA 3.0
2011-08-03T10:45:53.400Z
@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).
Sadeq Dousti
CC BY-SA 3.0
2011-10-12T03:42:35.560Z
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.
user6584
CC BY-SA 2.5
2011-02-26T03:25:04.260Z
2011-02-26T03:25:04.260Z
Sadeq Dousti
<p>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.</p>

<p>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.</p>

<p>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?</p>

CC BY-SA 2.5
2011-02-25T20:18:34.133Z
If you don't have the key, how can you make sure that a t-bit tag is the correct one?
Sadeq Dousti
CC BY-SA 2.5
2011-02-26T02:25:44.937Z
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
<cr.crypto-security>
Security of message authentication codes and tag size
Conrado
# Security of message authentication codes and tag size

(Asked by: username_0 on 2011-02-25)

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?

**Tags:** cr.crypto-security
> **Comments:**
> **username_1**: If you don't have the key, how can you make sure that a t-bit tag is the correct one?  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_1 on 2011-02-26. Score: 2 | Accepted 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!)

> **Comments:**
> **username_0**: 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.  
> **username_2**: 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.  
> **username_1**: @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).  
> **username_2**: 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.  

---

