Should AES-CMAC key cryptoperiod be affected by MAC truncation to avoid birthday-attacks?

Given a 128-bit key used for authentication based on AES-CMAC, the NIST 800-38B recommendations suggest at least two criteria for a good key cryptoperiod:

1. after 'MaxInvalids' error messages the key should be retired (considering the MAC truncation and the accepted Risk in appendix A);
2. the key should be changed to limit its message span (e.g. $2^{48}$ usages for AES-128).

My question is: should the second criterion be considered if I have MAC truncation? In my scenario, I'm assuming that the attacker can only see truncated MACs (suppose $30$ bits after truncation). Since I'm using truncation, and this criterion is made to avoid attacks based on detection of a pair of distinct messages with the same MAC before its truncation, should I still consider this criterion? If yes, should the limit still be $2^{48}$ or is it affected by the truncation?

UPDATE

The scenario is: only truncated MACs are sent to a limited-bandwidth network, and the attacker has access to the network. Considering Elias answer I removed the assumption that the attacker sees only truncated MACs, which is not meaningful. So, if we remove this assumption, do I have to shorten the cryptoperiod to consider $2^{15}$ (truncated MAC), or I can just consider $2^{64}$ (entire MAC)?

Yes, truncated MACs influence the cryptoperiod.

First of all, I cannot really think of any case where it makes sense to assume that the attacker only sees a truncation of the MAC if that isn't what is actually used in the system! And if you actually truncate your MACs to 30 bits you will probably have collisions after $2^{15}$ message blocks. So you definitely need to reduce the cryptoperiod.

On the other hand you're saying an attacker can only see 30 bits of the MAC because you are truncating it. Let us assume that you are still using the full MAC and that this makes sense in your scenario for some reason.

This in itself doesn't change the attackers position significantly:

• Exhaustively searching for the correct key becomes more complicated because now the given 30 bits of the MAC might match but it might still be the wrong key. However there are $2^{128}$ possible keys and by the birthday paradox a MAC collision will probably occur after about $2^{64}$ message block. So this is the more plausible target anyway.
• When a collision occurs the attacker can now not readily detect it anymore because only parts of the MAC are visible to him. On the other hand it will potentially be easy to submit fake queries to validate potential collisions and the probability for a collision doesn't change when the attackers view is truncated.

So in this case it would be fine to keep the values but I would love to hear how this makes sense.

• So what you are saying is that even if the attacker only sees truncated MACs, it does not affect the 'birthday attack', but it just adds a 'check' phase. That is, when the attacker sees a 30-bit collision, he only has to check (by querying) if the collision extends to 128 bits. If not, he can just keep on looking for another collision. I agree, I updated the question removing the assumption. – gentooise Jun 28 '17 at 10:16
• I think I already answered your question. If you actually truncate your MAC it does affect the cryptoperiod. – Elias Jun 28 '17 at 10:56
• I didn't understand why. If the attacker still has to find a whole "128-bit collision", why I have to consider 30 bits for the birthday attack? I mean, a collision of 30 bits does not mean anything. Also, consider that I'm applying the first criterion (point 1. in my question), so if the attacker tries to query for more than 'MaxInvalids' times, the key will get updated as well. – gentooise Jun 28 '17 at 13:00
• But if you only transmit 30 bits that means your system only uses 30 bits which means only those 30 bits have to collide and the attacker wins. The other 98 bits aren't really used anywhere anymore and are now irrelevant. – Elias Jun 28 '17 at 13:21
• But collisions can be exploited by the attacker because of the following property (that can allow MAC forgery): $MAC(M_1) = MAC(M_2) \implies MAC(M_1 || x) = MAC(M_2 || x)$. If an attacker discovers a 30 bit collision which is not a 128 bit collision, what he can do is just 'exchange the collided messages'. He cannot forge a MAC for any other message because the property does not hold. Thus, if in my scenario an exchange of two old messages is not a risk, a 30 bit collision is not relevant. Am I missing something? Are there other possible attacks which are not based on that property? – gentooise Jun 29 '17 at 7:06