Key rotation techniques

• US 9,608,813 B1
• Filed: 06/13/2013
• Issued: 03/28/2017
• Est. Priority Date: 06/13/2013
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Roth, Gregory Branchek, Wren, Matthew James, Brandwine, Eric Jason, Pratt, Brian Irl
• Primary Examiner(s): Lewis, Lisa
• Assistant Examiner(s): Tsang, Henry
• Application Number:
  US13/916,999
• Time in Patent Office: 1,384 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 63/0435 wherein the sending and receiving network entities apply symmetric encryption, i.e. same key used for encryption and decryption cryptographic mechanisms or cryptographic arrangements for symmetric key encryption H04L9/06
• CPC Class Codes: H04L 63/0807 using tickets, e.g. Kerberos cryptographic mechanisms or cryptographic arrangements for entity authentication using tickets or tokens H04L9/3213
• CPC Class Codes: H04L 9/0822 using key encryption key
• CPC Class Codes: H04L 9/0825 using asymmetric-key encryption or public key infrastructure [PKI], e.g. key signature or public key certificates
• CPC Class Codes: H04L 9/083 involving central third party, e.g. key distribution center [KDC] or trusted third party [TTP]
• CPC Class Codes: H04L 9/0891 Revocation or update of secret information, e.g. encryption key update or rekeying
• CPC Class Codes: H04L 9/0894 Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage
• CPC Class Codes: H04L 9/14 using a plurality of keys or algorithms
• CPC Class Codes: H04L 9/16 the keys or algorithms being changed during operation
• CPC Class Codes: H04L 9/3213 using tickets or tokens, e.g. Kerberos network architectures or network communication protocols for entities authentication using tickets in a packet data network H04L63/0807
• CPC Class Codes: H04L 9/3234 involving additional secure or trusted devices, e.g. TPM, smartcard, USB or software token network architectures or network communication protocols for supporting authentication of entities using an additional device in a packet data network H04L63/0853
• CPC Class Codes: H04L 9/3247 involving digital signatures

Abstract

A plurality of devices have common access to a cryptographic key. The cryptographic key is rotated by providing the devices simultaneous access to both the cryptographic key and a new cryptographic key and then revoking access to the cryptographic key. Keys stored externally and encrypted under the cryptographic key can be reencrypted under the new cryptographic key. Keys intended for electronic shredding can be left encrypted under the old cryptographic key.

Claims

1. A computer-implemented method, comprising:

under the control of one or more computer systems having executable instructions,

receiving a first request to electronically shred a first subset of a plurality of customer keys encrypted under a first cryptographic key;

performing a first process that results in each security module in a plurality of security modules being able to perform cryptographic operations with a customer key of the plurality of customer keys regardless of whether the customer key is encrypted using the first cryptographic key or a second cryptographic key at least by;

submitting a second request to a selected security module of the plurality of security modules;

receiving, from the selected security module, a response to the second request that includes the second cryptographic key, in a form of an encrypted second cryptographic key, encrypted in a manner decryptable by the plurality of security modules; and

providing at least the encrypted second cryptographic key to each other security module from the plurality of security modules;

for each customer key of a second subset of the plurality of customer keys encrypted under the first cryptographic key, the second subset being disjoint from the first subset as a result of having received the first request;

accessing, from a data storage system, the customer key;

instructing a security module from the plurality of security modules to;

use the first cryptographic key to decrypt the customer key to form a decrypted customer key;

use the second cryptographic key to encrypt the decrypted customer key; and

provide the customer key encrypted under the second cryptographic key; and

storing the customer key encrypted under the second cryptographic key in the data storage system; and

at a time after each customer key of the plurality of customer keys is encrypted under the second cryptographic key and stored in the data storage system;

determining that the first process was successful; and

performing a second process that results in each security module in the plurality of security modules losing access to the first cryptographic key but maintaining access to the second cryptographic key.

2. The computer-implemented method of claim 1, further comprising selecting the second subset of the plurality of customer keys by excluding, from the plurality of customer keys, the first subset of the plurality of customer keys.

3. The computer-implemented method of claim 1, further comprising, causing the security modules to use at least a third subset of the plurality of customer keys to perform cryptographic operations as a service to a customer of the service.

4. The computer-implemented method of claim 1, wherein the first request is received in accordance with a rotation schedule for the plurality of customer keys.

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

associating, for one or more customer keys outside of the plurality of customer keys, the one or more customer keys with a first status indicating pending electronic shredding; and

associating, as a result of the plurality of security modules losing access to the first cryptographic key, the one or more customer keys with a second status indicating completed electronic shredding.

6. The computer-implemented method of claim 1, wherein being able to perform cryptographic operations with the customer key regardless of whether the customer key is encrypted using the first cryptographic key or the second cryptographic key includes being able to select between the first cryptographic key and the second cryptographic key based at least in part on an identifier associated with the customer key provided to the security module.

7. A computer-implemented method, comprising:

under the control of one or more computer systems having executable instructions,

selecting a subset of data objects from a set of data objects encrypted under a first cryptographic key;

providing, to a plurality of devices, access to both a first cryptographic key and a second cryptographic key such that the plurality of devices are able, in response to receiving a first request, to utilize either the first cryptographic key or the second cryptographic key to perform a cryptographic operation, at least by;

submitting a second request to a selected device of the plurality of devices;

receiving, from the selected device, a response to the second request that includes the second cryptographic key, in a form of an encrypted second cryptographic key, encrypted in a manner decryptable by the plurality of devices; and

providing at least the encrypted second cryptographic key to each other device from the plurality of devices; and

for each data object of the subset of data objects encrypted under the first cryptographic key;

causing a device from the plurality of devices to decrypt the data object using the first cryptographic key;

causing the device to encrypt the data object under the second cryptographic key; and

at a time after each data object of the subset of data objects is encrypted under the second cryptographic key;

determining that each security module in the plurality of devices has access to the second cryptographic key; and

causing each security module in the plurality of devices to lose access to the first cryptographic key but maintain access to the second cryptographic key.

8. The computer-implemented method of claim 7, wherein:

the subset of data objects is a first subset;

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

selecting the subset of data objects is a result of having received, from a customer of the service provider on behalf of whom the set of data objects are managed by the service provider, a request to electronically shred a second subset of the set of data objects that is disjoint from the first subset.

9. The computer-implemented method of claim 7, wherein:

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

the subset of data objects comprises cryptographic keys managed on behalf of customers of the service provider.

10. The computer-implemented method of claim 7, wherein selecting the subset of data objects is based at least in part on the subset of data objects lacking an association with information indicating an instruction for electronically shredding.

11. The computer-implemented method of claim 7, wherein the plurality of devices are security modules.

12. The computer-implemented method of claim 7, wherein the data objects are cryptographic keys used by the devices to perform cryptographic operations.

13. The computer-implemented method of claim 7, wherein:

the second request further includes the first cryptographic key;

the response to the second request further includes an encrypted first cryptographic key; and

the instructions that provide the encrypted second cryptographic key include instructions to provide the encrypted first cryptographic key to each other device of the plurality of devices.

14. A system, comprising:

one or more processors; and

memory including instructions that, as a result of execution by the one or more processors, cause the system to;

store data objects usable by a plurality of devices in providing a service, the data objects encrypted under a first cryptographic key;

cause the plurality of devices to have simultaneous access to the first cryptographic key and a second cryptographic key such that the plurality of devices are able, in response to receiving a first request to access a data object, to utilize either the first cryptographic key or the second cryptographic key to perform a cryptographic operation, by causing the system to at least;

provide a second request, to a selected device from the plurality of devices, the second request including the second cryptographic key;

receive a response to the second request, the response including an encrypted second cryptographic key; and

provide the encrypted second cryptographic key to each other device of the plurality of devices such that each device from the plurality of devices can decrypt the encrypted second cryptographic key to obtain the second cryptographic key;

cause the plurality of devices to decrypt a selected subset of the data objects using the first cryptographic key;

cause the plurality of devices to encrypt the selected subset of the data objects under the second cryptographic key, the selected subset excluding data objects selected for electronic shredding;

check that each of the plurality of devices has access to the second cryptographic key; and

cause the plurality of devices to lose access to the first cryptographic key.

15. The system of claim 14, wherein:

the data objects correspond to a customer of a service provider; and

the instructions further cause the system to select the subset based at least in part on an absence of an instruction from the customer to the service provider to refrain from electronically shredding the subset.

16. The system of claim 14, wherein the data objects are cryptographic keys used by the plurality of devices to perform cryptographic operations.

17. The system of claim 14, wherein the instructions that cause the system to store the data objects include instructions that cause the system to transmit the data objects to a data storage service.

18. The system of claim 14, wherein:

the second request further includes the first cryptographic key;

the response to the second request further includes an encrypted first cryptographic key, such that each device from the plurality of devices can decrypt the encrypted first cryptographic key to obtain the first cryptographic key; and

the instructions that provide the encrypted second cryptographic key include instructions to provide the encrypted first cryptographic key to each other device of the plurality of devices.

19. The system of claim 14, wherein the instructions that cause the system to cause the plurality of devices to lose access to the first cryptographic key include instructions that cause the system to:

provide a third request, to a selected device from the plurality of devices, for a set of operational parameters for the plurality of devices that lacks the first key;

receive, a response to the third request that includes the set of operational parameters; and

provide the set of operational parameters received to each device of the plurality of devices.

20. The system of claim 14, wherein:

the selected subset is a proper subset of a set of data objects encrypted under the first cryptographic key; and

the instructions further cause the system to select the subset based at least in part on the data objects lacking an association with information indicating an instruction for electronically shredding.

21. A non-transitory computer-readable storage medium having stored thereon instructions that, as a result of execution by one or more processors of a computer system, cause the computer system to:

cause a plurality of devices, having common access to a first cryptographic key under which a set of data objects used by the plurality of devices are encrypted, to replace the first cryptographic key with a second cryptographic key by at least causing the computer system to;

submit a request to a selected device of the plurality of devices;

receive, from the selected device, a response to the request that includes the second cryptographic key, in a form of an encrypted second cryptographic key, encrypted in a manner decryptable by the plurality of devices;

provide at least the encrypted second cryptographic key to each other device from the plurality of devices;

cause one or more devices of the plurality of devices to decrypt, using the first cryptographic key, a subset of the set of the data objects that are not selected for electronic shredding;

cause the one or more devices of the plurality of devices to encrypt the subset of the set of data objects such that data objects of the subset are accessible regardless of whether the data objects of the subset are encrypted using the first cryptographic key or the second cryptographic key; and

at a time after the data objects of the subset become accessible by using the second cryptographic key;

check that each of the plurality of devices have common access to the second cryptographic key; and

cause the plurality of devices to lose access to the first cryptographic key.

22. The non-transitory computer-readable storage medium of claim 21, wherein the data objects of the set of data objects are cryptographic keys used by the devices to perform cryptographic operations.

23. The non-transitory computer-readable storage medium of claim 21, wherein the data objects of the subset are not selected based at least in part on retention of the data objects of the subset not having been requested.

24. The non-transitory computer-readable storage medium of claim 21, wherein the plurality of devices are security modules.

25. The non-transitory computer-readable storage medium of claim 21, wherein the instructions that cause the computer system to cause the one or more devices to encrypt the subset of the set of data objects include instructions that cause the system to access the data objects of the subset from a data storage system based at least in part on the subset of the set of data objects being associated with the first cryptographic key.

26. The non-transitory computer-readable storage medium of claim 21, wherein the instructions further cause the computer system to select the data objects of the subset so as to exclude one or more data objects marked for electronic shredding.

27. The non-transitory computer-readable storage medium of claim 21, wherein:

the subset of the set of data objects corresponds to a customer of a service provider; and

the instructions that cause the computer system to cause the plurality of devices with common access to replace the first cryptographic key with the second cryptographic key are executed as a result of a request, from the customer, to electronically shred the subset of the set of data objects.

28. The non-transitory computer-readable storage medium of claim 21, wherein, for each data object of the subset of the data objects, the data object is selected as part of the subset as a result of an expiration associated with the data object having passed.