How does one calculate the cryptoperiod?

Question

NIST Special Publication 800-57 defines a cryptoperiod as

the time span during which a specific key is authorized for use by legitimate entities, or the keys for a given system will remain in effect. A suitably defined cryptoperiod:

1. Limits the amount of information protected by a given key that is available for cryptanalysis,
2. Limits the amount of exposure if a single key is compromised,
3. Limits the use of a particular algorithm to its estimated effective lifetime,
4. Limits the time available for attempts to penetrate physical, procedural, and logical access mechanisms that protect a key from unauthorized disclosure
5. Limits the period within which information may be compromised by inadvertent disclosure of keying material to unauthorized entities, and
6. Limits the time available for computationally intensive cryptanalytic attacks (in applications where long-term key protection is not required).

The standard goes on to describe risk factors affecting cryptoperiods:

Among the factors affecting the risk of exposure are:

1. The strength of the cryptographic mechanisms (e.g., the algorithm, key length, block size, and mode of operation),
2. The embodiment of the mechanisms (e.g., FIPS 140-2 Level 4 implementation, or software implementation on a personal computer),
3. The operating environment (e.g., secure limited access facility, open office environment, or publicly accessible terminal),
4. The volume of information flow or the number of transactions,
5. The security life of the data,
6. The security function (e.g., data encryption, digital signature, key production or derivation, key protection),
7. The re-keying method (e.g., keyboard entry, re-keying using a key loading device where humans have no direct access to key information, remote re-keying within a PKI),
8. The key update or key derivation process,
9. The number of nodes in a network that share a common key,
10. The number of copies of a key and the distribution of those copies, and
11. The threat to the information (e.g., who the information is protected from, and what are their perceived technical capabilities and financial resources to mount an attack).

It then goes on to list other factors that might affect cryptoperiods, such as the consequences of exposure, whether the key is used for communications or storage, and the cost of key revocation and replacement.

Specifically for a symmetric key wrapping key, for example, the standard recommends:

The recommended originator usage period for a symmetric key wrapping key that is used to encrypt very large numbers of keys over a short period of time is on the order of a day or a week. If a relatively small number of keys are to be encrypted under the key wrapping key, the originator usage period of the key wrapping key could be up to a month. In the case of keys used for only a single message or communications session, the cryptoperiod would be limited to a single communication session. Except for the latter, a maximum recipient usage period of 3 years beyond the end of the originator usage period is recommended.

My specific question is what constitutes "very large numbers of keys" and "relatively small number of keys" in the above recommendation? More generally, is there a standard formula to compute the optimal cryptoperiod taking all the risk factors listed above into account?

As a specific example, please consider the following scenario: 1. Protection consists of AES-256 in CBC mode and HMAC based on SHA-256 2. 100,000 keys issued per month with this protection to manufacturers, for personalisation of consumer units 3. Probability of compromise is thought to be "low" 4. Ability to exploit compromise is thought to be "difficult" 5. However, confirmed compromise will entail recall of affected consumer units to their original factory

Answer 1

There is no general way to compute the "cryptoperiod". Usually, the algorithm should specify how often you need to change keys, to achieve a desired level of security against cryptanalysis attacks.

For instance, AES in CBC mode has some weaknesses once you encrypt anywhere close to $2^{64}$ blocks with the same key, so you should change the key long before then. For most real-world applications, you don't need to worry about this, so a good approximation is: you don't need to worry about changing the key.

If you are concerned about resistance to key compromise attacks, you'll need to work out for yourself how often you need to change the key to meet your goals in this area and reduce the risk to a level that is acceptable to you. This is algorithm-independent, but highly domain-specific, so I don't know of any general method for this either.

To get a better answer, I suggest re-asking the question about a specific cryptographic algorithm and a specific application scenario, and we can give you recommendations.

---

On your specific scenario: I am going to assume that these devices are in the consumer's hands; that each device has a different key; and that if the key in a device is compromised, only the one consumer who owns that is harmed, but there is no broader harm. If those assumptions are not valid, we might need to know more about the application.

Based upon those assumptions, there is probably no strong need to change the AES key. When securing communications, it is common practice to generate a new AES key for each connection/session (e.g., this is how TLS works), but that's mostly because it is just as easy to do it as to not. CBC does place some limits on how much data you can safely encrypt with a single key: if you encrypt $n$ blocks, then there is approximately a $n^2/2^{129}$ chance of some partial information about the data leaking. Thus, if you make sure to encrypt no more than $2^{50}$ blocks of data ($2^{57}$ bytes of data) under any one AES key, then there is only about a $1/2^{29}$ chance of a little bit of information leaking. Even with the number of devices you ship, that's still a very low risk, so probably acceptable. (It seems unlikely that any consumer device will ever encrypt more than $2^{57}$ bytes of data.) In short, you can basically ignore the likelihood of cryptanalytic attacks.

For key-compromise attack, that's something you'll need to evaluate on your own. My guess is that the risk of key-compromise attack is minor. If each consumer owns their own device, and the keys in that device don't give them access to any other information, they probably won't have much incentive to try to compromise their own device, so the likelihood of that kind of key-compromise seems small. And if their key can't be used to cause harm to anyone else, then the impact of such a key-compromise seems low. The only significant risk I can think of, without details about what the devices are used for, is that if the device changes hand, it's possible that the new owner could find themselves with access to a key that was used to encrypt the prior owner's data. If that sounds problematic, one possible mitigation might be to change the key periodically (say, on every boot).

In general, choosing a cryptoperiod is really about risk management. You look at all of the risks related to key exposure (cryptanalysis, key compromise, etc.). If the risk is unacceptable, then you look for mitigations that either lower the likelihood of key exposure or that lower the impact of key exposure. Changing the key frequently is one mitigation you can consider, among your arsenal of tools.

Answer 2

This is all about the question of risk assessment. Are you willing to risk all devices together so that if one key is compromised, they all have to be returned? What is the cost of one return, 100 returns, or 100,000 returns? What is the expense of issuing a master key? Of issuing ten master keys? Of issuing a thousand?

Do you have an estimate for how hard it might be for an attacker to compromise a device and extract the key? Is it a year's effort? Is the payout worth it to an attacker to spend a million dollars to obtain your keys? If he breaks it once for a million dollars, does cracking a second key cost him another million, or does it only take him an additional four hours?

Cryptoperiod doesn't enter too much into this discussion, other than you should also consider "time" as one of the factors. If someone hacks the key out after a year of owning it, does that mean all your 2012 model devices are compromised? Or if you don't change the keys every period, that means every device you make from 2012-2017 are all equally at risk from a single compromise.

Where time plays a more important role is in the length of protection needed for your secrets. Consider a DishTV receiver. The session key is only needed as long as the transmission lasts, because most Dish pirates don't record an encrypted stream in hopes of decoding it next year after cracking the keys - they only want their Dish to work right now. Those keys don't need the same duration of protection that a long-term valuable (like a credit card number) requires.

The large number/short period vs. small number/long period idea is one way to help you estimate the overall number of exposure per key. If you're deploying an encrypting radio to 100,000 people, and they're each going to use one session key per radio per day, that's X amount of traffic. If you deploy encrypting radios to 100 people, but each goes through a thousand session keys per day, it's the same amount of traffic. If you think you can only afford to risk one million session keys per primary key, your cryptoperiod would be 10 days.