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?
Security of message authentication codes and tag size
cr.crypto security
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!)