Automatic key rotation

1. A computer-implemented method, under control of one or more electronic computer systems configured with one or more processors and memory including executable instructions, comprising:

tracking use in cryptographic operations of a cryptographic key identified by a key identifier;

as a result of one or more conditions on the tracked use being fulfilled, at least one of the one or more conditions being that a number of cryptographic operations associated with the cryptographic key exceeds a threshold, and value of the threshold corresponding to the cryptographic key being different from value of threshold corresponding to another cryptographic key:

obtaining an encrypted object from a security module, the encrypted object encrypted using a symmetric key;

decrypting the encrypted object using the symmetric key to obtain a new cryptographic key;

replacing the cryptographic key with the new cryptographic key by associating the new cryptographic key with the key identifier; and

marking the new cryptographic key as active by updating at least one value stored in the security module; and

responding to requests specifying the key identifier using the replaced cryptographic key in at least one decryption operation in response to a decryption request specifying the key identifier.

2. The computer-implemented method of claim 1 , wherein tracking the use in cryptographic operations of the cryptographic key includes tracking allocations of operations to computing devices that perform the cryptographic operations.

3. The computer-implemented method of claim 1 , further comprising:

using the replaced cryptographic key in at least one decryption operation in response to a decryption request specifying the key identifier; and

using the new cryptographic key in at least one encryption operation in response to an encryption request specifying the key identifier.

4. The computer-implemented method of claim 1 , wherein:

at least some of the information generated based at least in part on the new cryptographic key is generated by a computing device different from the one or more computer systems that replaced the cryptographic key; and

replacing the cryptographic key includes causing the computing device to replace the cryptographic key.

5. The computer-implemented method of claim 1 , wherein tracking the use in cryptographic operations of the cryptographic key includes treating a number of cryptographic operations allocated to another computing device as used independent of whether the other computing device performs the allocated number of operations.

6. The computer-implemented method of claim 1 , wherein:

the one or more computer systems are hosted by a service provider; and

the cryptographic operations are performed in connection with responding to requests submitted by customers of the service provider.

7. One or more non-transitory computer-readable storage media comprising instructions that, when executed by one or more processors of a computer system, cause the computer system to:

track usage of a key repeatedly used in cryptographic operations involved in responding to requests specifying a key identifier that identifies the key;

detect when one or more conditions on the tracked usage require retirement of the key, at least one of the one or more conditions being that the key is associated with exceeding a threshold number of cryptographic operations, and the threshold number allocated to the key indicating a different number from threshold numbers allocated to another set of keys;

as a result of detecting the one or more conditions requiring retirement of the key:

obtain an encrypted key from a security module, the encrypted key encrypted using a symmetric key;

decrypt the encrypted key using the symmetric key to obtain a different key; and

indicate the key as retired by causing the key to be unusable for encryption operations though usable for decryption operations;

cause the different key to be associated with the key identifier and used in the cryptographic operations involved in responding to the requests that specify the key identifier; and

use the key in the decryption operations in response to a decryption request specifying the key identifier.

8. The one or more non-transitory computer-readable storage media of claim 7 , wherein tracking usage of the key includes allocating operations to other computer systems.

9. The one or more non-transitory computer-readable storage media of claim 7 , wherein detecting when one or more conditions require retirement of the key is based at least in part on a counter.

10. The one or more non-transitory computer-readable storage media of claim 7 , wherein at a time after detecting that the one or more conditions require retirement of the key, the instructions further cause the computer system to use the key for decrypting at least one ciphertext generated based at least in part on the key.

11. The one or more non-transitory computer-readable storage media of claim 7 , wherein the key is from a plurality of keys for which the instructions cause the computer system to track usage.

12. The one or more non-transitory computer-readable storage media of claim 11 , wherein the key is managed by the computer system on behalf of a customer of a computing resource provider and the plurality of keys include at least one other key managed on behalf of another customer of the computing resource provider.

13. The one or more non-transitory computer-readable storage media of claim 7 , wherein causing the different key to be used includes changing a status identifier for the key and persisting the key in association with the changed status identifier.

14. The one or more non-transitory computer-readable storage media of claim 7 , the requests are web service requests.