REDUNDANT KEY MANAGEMENT

• US 20160154963A1
• Filed: 01/22/2016
• Published: 06/02/2016
• Est. Priority Date: 08/08/2012
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Kumar, Sandeep, Roth, Gregory Branchek, Rubin, Gregory Alan, Seigle, Mark Christopher, Tirdad, Kamran
• Granted Patent: US 9,904,788 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• CPC Class Codes: G06F 12/1408 by using cryptography for digital transmission H04L9/00
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: G06F 21/6209 to a single file or object, e.g. in a secure envelope, encrypted and accessed using a key, or with access control rules appended to the object itself
• CPC Class Codes: H04L 2209/24 Key scheduling, i.e. generating round keys or sub-keys for block encryption
• 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/14 using a plurality of keys or algorithms

Abstract

A data storage service redundantly stores data and keys used to encrypt the data. Data objects are encrypted with first cryptographic keys. The first cryptographic keys are encrypted by second cryptographic keys. The first cryptographic keys and second cryptographic keys are redundantly stored in a data storage system to enable access of the data objects, such as to respond to requests to retrieve the data objects. The second cryptographic keys may be encrypted by third keys and redundantly stored in the event access to a second cryptographic key is lost.

Claims

1. A computer-implemented method, comprising:

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

for each set of data objects of at least a plurality of sets of data objects;

for each data object in the set of data objects;

storing the data object in a first data store; and

while the data object is stored in the first data store, providing an identifier for the data object that is usable to retrieve the data object after removal of the data object from the first data store;

generating a first cryptographic key for the set of data objects;

encrypting one or more data objects in the set using the first cryptographic key to generate one or more encrypted data objects;

causing the first cryptographic key to be encrypted using a second cryptographic key, thereby resulting in an encrypted first cryptographic key; and

redundantly storing the one or more encrypted data objects and the encrypted first cryptographic key, to achieve a first durability for the data object and a second durability for the encrypted first cryptographic key, using a plurality of data storage devices used by a second data storage system to persistently store the data objects, the second durability being greater than the first durability.

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

the method further comprises deconstructing the data object into a plurality of shards;

encrypting the one or more data objects includes encrypting the plurality of shards comprising the data object; and

redundantly storing the one or more encrypted data objects includes distributing the plurality of shards for each data object among the plurality of data storage devices.

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

encrypting the second cryptographic key using a third cryptographic key to generate an encrypted second cryptographic key; and

redundantly storing the encrypted second cryptographic key using the plurality of data storage devices.

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

the first cryptographic key is from a set of multiple cryptographic keys that are encrypted by the second cryptographic key; and

the method further comprises replacing the second cryptographic key with another second cryptographic key for encryption of additional cryptographic keys.

5. The computer-implemented method of claim 1, further comprising storing, among the plurality of data storage devices, a plurality of encrypted second cryptographic keys that includes the second cryptographic key in encrypted form.

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

detecting a security breach involving the second cryptographic key;

obtaining a new second cryptographic key; and

using the new second cryptographic key to encrypt the first cryptographic key without reencrypting the one or more data objects in the set.

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

detecting a security breach involving the second cryptographic key; and

updating an anti-entropy process to locate, in the second data storage system, cryptographic keys that are encrypted under the second cryptographic key and reencrypt the cryptographic keys with another second cryptographic key.

8. A system, comprising:

one or more processors; and

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

obtain a first cryptographic key for a set of data objects, the set of data objects comprising a data object stored in a first data store, the data object having an identifier for the data object that is usable to retrieve the data object after removal of the data object from the first data store;

encrypt the data object using the first cryptographic key;

cause the first cryptographic key to be encrypted using a second cryptographic key, resulting in an encrypted first cryptographic key; and

redundantly store the data object and the encrypted first cryptographic key, to achieve a first durability for the data object and a second durability for the encrypted first cryptographic key, using a plurality of data storage devices used by a second data storage system to persistently store data objects, the second durability being at least the first durability.

9. The system of claim 8, wherein:

the instructions further comprise instructions that, when executed by the one or more processors, cause the system to deconstruct the data object into a plurality of shards; and

the instructions that cause the system to encrypt the data object using, as a result of execution by the one or more processors, cause the system to individually encrypt individual shards of the plurality of shards using the first cryptographic key.

10. The system of claim 8, wherein the instructions further comprise instructions that, as a result of execution by the one or more processors, cause the system to provide the identifier prior to movement of the data object from the first data store to a second data store.

11. The system of claim 8, wherein the instructions further comprise instructions that, as a result of execution by the one or more processors, cause the system to use a new second cryptographic key to encrypt the first cryptographic key while allowing the data object to remain stored encrypted under the first cryptographic key.

12. The system of claim 8, wherein the second cryptographic key is a public cryptographic key of a public-private key pair.

13. The system of claim 12, wherein the system stores a private cryptographic key of the public-private key pair with a durability of at least the second durability.

14. The system of claim 8, wherein the system stores the second cryptographic key with a third durability that is at least the second durability.

15. One or more non-transitory computer-readable storage media having collectively stored thereon instructions that, when executed by one or more processors of a computer system, cause the computer system to:

before a data object is removed from a first data store for storage in a second data store, provide an identifier for the data object that is usable to obtain the data object after removal of the data object from the first data store;

obtain a first cryptographic key;

encrypt a data object using the first cryptographic key to generate an encrypted data object;

cause the first cryptographic key to be encrypted using a second cryptographic key; and

redundantly store the data object, encrypted first cryptographic key and encrypted second cryptographic key among a plurality of data storage devices of a second data store of a data storage system such that the data object is stored at a first durability and the first cryptographic key is stored a second durability that is greater than the first durability.

16. The one or more non-transitory computer-readable storage media of claim 15, wherein the instructions further cause the computer system to encrypt multiple different cryptographic keys using the second cryptographic key, each of the multiple different cryptographic keys used to encrypt a different data object.

17. The one or more non-transitory computer-readable storage media of claim 15, wherein:

encrypting the data object and encrypting the first cryptographic key are each performed using a symmetric key cryptographic algorithm;

the instructions further cause the computer system to encrypt the second cryptographic key using a public key of a public key cryptographic algorithm; and

the encrypted second cryptographic key is decryptable using a private key that the data storage system lacks.

18. The one or more non-transitory computer-readable storage media of claim 15, wherein the instructions further cause the computer system to redundantly store among the plurality of data storage devices, metadata that is usable to identify the second cryptographic key for decrypting the first cryptographic key.

19. The one or more non-transitory computer-readable storage media of claim 15, wherein redundantly storing the encrypted data object includes storing a plurality of shards such that each shard of the plurality of shards is stored in a different data storage device, the shards generated by applying a redundancy encoding scheme to the data object and encrypted using the first cryptographic key after applying the redundancy encoding scheme.

20. The one or more non-transitory computer-readable storage media of claim 15, wherein the second cryptographic key is stored at least the second durability.