Is there any benefit of changing the AES-CCM encryption key periodically even if the Nonce space is not exhausted yet?

Question

I would like an answer that could be sustained by a mathematical proof.

Let's say I'm using AES-CCM to encrypt a lot of messages, and I always use a different nonce.

I know that when the nonce space gets exhausted, the encryption key needs to be changed.

The question is: even though my encryption key has not been compromised and the nonce space is not exhausted, do I have any benefit from changing the encryption key at random times?

My intuition is that whenever I encrypt some data and someone can see the result of the encryption, I somehow "lose" a tiny bit of entropy, even though I change the nonce every time. So, by changing the encryption key at some point, it feels like I'm gaining because the attacker has never seen messages encrypted with this key before.

Is it really worth the effort of changing the key periodically or is assuring an unique nonce really enough?

Answer 1

CCM mode uses CTR mode the encryption and CBC-MAC for the authentication. For a security proof you can refer to On the Security of CTR + CBC-MAC.

With CTR the fact that AES is a PRP rather than PRF starts to show after $2^{64}$ blocks have been encrypted. In practice this does not lead to a very effective attack even then.

After a similar number of blocks encrypted, collisions could allow MAC forgeries for new messages. This is a much more serious attack, though it of course requires an active adversary to take advantage of it. To keep the probability of collisions low it is sometimes recommended to use similar authentication modes (e.g. CMAC) for only $2^{48}$ blocks.

Note that the above limit is not dependent on the nonce size, which for CCM is usually e.g. 12 bytes, but the block size of the cipher which for AES is 128 bits (16 bytes). (With random nonces a nonce collision would be likely earlier than the above.)

In practice, you can rest easy while using the same key for gigabytes or even terabytes of data. Only if your get into petabyte range does key lifetime become a concern. However, the above attacks are probabilistic and if you can frequently agree on a new key, you get lower probabilities.