Key rotation techniques

• US 10,313,312 B2
• Filed: 03/17/2017
• Issued: 06/04/2019
• 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): Tsang, Henry
• Application Number:
  US15/462,604
• Publication Number:
  US 20170195119A1
• Time in Patent Office: 809 Days
• Field of Search: None
• 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, having common access to a first key under which a set of data objects used by the plurality of devices are encrypted, is caused to replace the first key with a second key by at least causing a device of the plurality of devices to encrypt a subset of the set of data objects that are not selected for electronic shredding, allow access to a data object of the subset regardless of whether the data object is encrypted using the first key or the second key. At a time after the data object becomes accessible by using the second key, each of the plurality of devices is verified have common access to the second key, and the plurality of devices is caused to lose access to the first key.

Claims

1. A computer-implemented method, comprising:

for a set of data objects encrypted with a first key that is accessible to a plurality of devices, terminating access to a first subset of the set of data objects by;

transmitting a second key to the plurality of devices, the second key usable for reencrypting a second subset of the set of data objects; and

causing, until the plurality of devices complete reencryption of the second subset of the set of data objects, the first key to be usable to perform a first cryptographic operation on individual data objects of the set of data objects and to be unusable to perform a second cryptographic operation on the individual data objects; and

at a time after the second subset becomes accessible by using the second key;

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

causing the plurality of devices to lose access to the first key.

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

the set of data objects is associated with a customer of a service provider; and

the method further comprises receiving a selection, from the customer, of the first subset for electronic shredding.

3. The computer-implemented method of claim 1, further comprising selecting the second subset to exclude data objects of the set of data objects that are marked for electronic shredding.

4. The computer-implemented method of claim 1, wherein reencrypting the second subset includes accessing, based at least in part on the second subset being associated with the first key, a data object of the second subset from a data storage system.

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

6. The computer-implemented method of claim 1, further comprising determining, based at least in part on a lack of a request to mark a particular data object of the set of data objects for electronic shredding, that the particular data object of the set of data objects is not selected for electronic shredding.

7. The computer-implemented method of claim 1, wherein a data object of the set of data objects is a cryptographic key used by the plurality of devices to perform cryptographic operations.

8. A system, comprising memory to store instructions that, as a result of execution by one or more processors, cause the system to, for a set of data objects encrypted with a first key that is accessible to a plurality of devices:

initiate reencryption of a second subset of the set of data objects by providing tho a second key to the plurality of devices;

during reencryption of the second subset, allow the plurality of devices to perform a first cryptographic operation and not to perform a second cryptographic operation on a first subset of the set of data objects using the first key; and

at a time after the individual data object of the second subset becomes accessible by using the second key, cause the plurality of devices to lose access to the first key.

9. The system of claim 8, wherein the set of data objects is a plurality of cryptographic keys.

10. The system of claim 8, wherein the instructions further include instructions that, as the result of execution by the one or more processors, cause the system to:

receive an identifier associated with the individual data object; and

select one of the first key or the second key based at least in part on the identifier.

11. The system of claim 8, wherein:

the instructions further include instructions that, as the result of execution by the one or more processors, cause the system to associate the first subset with a first status indicating that electronic shredding is pending; and

the instructions include instructions that, as the result of execution by the one or more processors, cause the device to, further at the time after an individual data object of the second subset is reencrypted, associate the first subset with a second status that indicates that electronic shredding of the first subset has been completed.

12. The system of claim 8, wherein the instructions include instructions that, as the result of execution by the one or more processors, cause the system to receive a request to replace the first key with the second key in accordance with a rotation schedule for the set of data objects.

13. The system of claim 8, wherein the instructions include instructions that, as the result of execution by the one or more processors, cause the system to cause the plurality of devices to use at least a third subset of the set of data objects to perform cryptographic operations as a service to a customer of the service.

14. The system of claim 8, wherein:

the first subset is a proper subset of the set of data objects; and

the second subset is mutually exclusive of the first subset.

15. A non-transitory computer-readable storage medium that stores executable instructions which, when executed by one or more processors of a computer system, cause the computer system to, for a set of data objects encrypted with a first key that is accessible to a plurality of devices, at least:

provide a second key to allow the plurality of devices to reencrypt, using a second key, a second subset of the set of data objects different from a first subset;

until the reencryption of the second subset is completed, allow the plurality of devices to perform a first cryptographic operation and not to perform a second cryptographic operation on a first subset of the set of data objects using the first key; and

at a time after the second subset becomes accessible by using the second key, cause the plurality of devices to lose access to the first key.

16. The non-transitory computer-readable storage medium of claim 15, wherein an individual data object of the second subset is a cryptographic key used by the plurality of devices to perform cryptographic operations.

17. The non-transitory computer-readable storage medium of claim 15, wherein the executable instructions, when executed by the one or more processors of the computer system, further cause the computer system to transmit the second subset to a data storage service.

18. The non-transitory computer-readable storage medium of claim 15, wherein the executable instructions that, when executed by the one or more processors of the computer system, cause the computer system to:

provide, to a selected device from the plurality of devices, a request that includes the first key and the second key;

receive a response that includes an encrypted first key and an encrypted second key, the encrypted first key and the encrypted second key being decryptable by individual devices of the plurality of devices to obtain the first key and second key; and

provide the encrypted first key and the encrypted second key to the individual devices of the plurality of devices.

19. The non-transitory computer-readable storage medium of claim 15, wherein the executable instructions that, when executed by the one or more processors of the computer system, cause the computer system to cause the plurality of devices to lose access to the first key include instructions that cause the computer system to:

provide a request, to a selected device from the plurality of devices, for a set of operational parameters for the plurality of devices for which the first key has been replaced by the second key;

receive a response that includes the set of operational parameters; and

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

20. The non-transitory computer-readable storage medium of claim 15, wherein:

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

the executable instructions include instructions that, when executed by the one or more processors of the computer system, further cause the computer system to select the second subset based at least in part on an individual data object of the second subset lacking an association with information indicating an instruction for electronically shredding.