How does one calculate the cryptoperiod? 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:
  
  
  Limits the amount of information protected by a given key that is available for cryptanalysis,
  Limits the amount of exposure if a single key is compromised,
  Limits the use of a particular algorithm to its estimated effective lifetime,
  Limits the time available for attempts to penetrate physical, procedural, and logical access mechanisms that protect a key from unauthorized disclosure
  Limits the period within which information may be compromised by inadvertent disclosure of keying material to unauthorized entities, and
  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:
  
  
  The strength of the cryptographic mechanisms (e.g., the algorithm, key length, block size, and mode of operation),
  The embodiment of the mechanisms (e.g., FIPS 140-2 Level 4 implementation, or software implementation on a personal computer),
  The operating environment (e.g., secure limited access facility, open office environment, or publicly accessible terminal),
  The volume of information flow or the number of transactions,
  The security life of the data,
  The security function (e.g., data encryption, digital signature, key production or derivation, key protection),
  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),
  The key update or key derivation process,
  The number of nodes in a network that share a common key,
  The number of copies of a key and the distribution of those copies, and
  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
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.