CCM for IoT - choosing L and M

Question

Other developers have developed a custom in-house RF protocol for our upcoming IoT devices. I would like to replace our use of AES-CTR with AE - our encryption library supports CCM which should therefore have the lowest barriers to implementation.

CCM requires two tunable parameters - L and M, with corresponding security tradeoffs. Given a preference for single key negotiation and short transactional messages, what are good values to choose for L and M?

As the devices support scheduling, I estimate an upper limit of roughly 100 messages per day over installed lifespan, which I might generously estimate at 30 years. Messages are typically under 10 bytes (the protocol supports up to 64kib). We wouldn't be using associated data.

I would also like to choose nonces at random, in part to save on storage synchronization and in part because I'm not 100% confident I understand the statement at Wikipedia: "One key insight is that the same encryption key can be used for both, provided that the counter values used in the encryption do not collide with the (pre-)initialization vector used in the authentication." clearly. This should then lower the expected lifetime of the key due to the birthday paradox.

Will this provide adequate security if I pick L=2 and M=8? Or would I need to add key renegotiation if we expect a lifetime of 30 years?

Edit: please note that I am much more concerned about the choice of L, which appears to create a security tradeoff (nonce length vs message length), than of M which is a more typical performance/security tradeoff.

Answer 1

The authenticate tag (M) should be as large as possible. The larger it is though, the more overhead for transmitting a single message. Generally you would want the tag to be at least 80 bits, which is 10 octets. Ideally, you should have a tag of 128 bits, or 16 octets, or M=16. A larger tag makes it more difficult for an attacker to forge messages without being caught. A 128 bit tag results in each forged message having a probability of 2^-128 of being accepted, resisting a computationally-bound attacker.

The message size (L) specifies how small the nonce will be (nonce size is 15-L octets). You want a random nonce to be large enough the birthday paradox is not an issue. For this, 96 bits, or L=3, should suffice. This size is the standard used for GCM under a random nonce, which has proven to be quite secure. Since 100 messages per day over 30 years results in only a little over a 10⁶ messages, it would also be safe to use a 64 bit nonce in theory, but 96 bits will prove safer if more messages are sent.

You should be generating a new session key using asymmetric cryptography each time the device is turned on. This will prevent an attacker who records messages from being able to retroactively decrypt them after obtaining a single master key as can be done with WPA and WPA2. This is referred to as forward secrecy, and ensures that an attacker cannot retroactively decrypt old sessions. Forward secrecy requires the use of ephemeral DH or ECDH for key exchange, rather than plain RSA.

Answer 2

The accepted answer is good, but I'm not sure if it addressed the statement that:

I would also like to choose nonces at random

From RFC 3610: "Within the scope of any encryption key K, the nonce value MUST be unique. That is, the set of nonce values used with any given key MUST NOT contain any duplicate values."

In other words, don't reuse the same nonce with the same key.

So, it would be good to consider whether there might be a non-negligible probability of randomly choosing the same nonce before the key is changed.

If you go with the above recommendation of L=3, which seems reasonable. Then you will be using a 96-bit nonce. If I assume there will be at worst 10^6 messages with the same key, then we should look at the probability that for n = 10^6 random throws I never generate the same nonce out of m = 2^96 possible nonces.

The probability that I don't choose a previously chosen nonce on the first random throw is 1. The probability that I don't choose a previously chosen nonce on the second random throw (given that I didn't on the first throw, which is certain) is (1-1/m). The probability that I don't choose a previously chosen nonce on the third random throw given that I haven't on any of the previous throws is (1-2/m)... and so on.

So, the probability that, in a total of n random throws, I never choose the same nonce is:

P(n) = 1(1-1/m)(1-2/m)(1-3/m)...(1-(n-1)/m)

For n much much less than m, this could be approximated by first taking the log to get a sum and then expanding the log to first order in x/m (i.e., set ln(1-x/n) ~ -x/n):

ln(P(n)) ~ ( 0 + -1/m + -2/m +... + -(n-1)/m ) = ( -n(n-1)/2m )

Or:

P(n) ~ e^{-n(n-1)/2m}

Or, given that n=10^6 and m=2^96:

P(n) ~ e^{-1/100000000000000000} ~ 1

In other words, you should be good to go with using random nonces (given the postulated 10^6 messages for a single key).