CCM for IoT - choosing L and M
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 106 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.
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).