Redundant key management

• US 9,251,097 B1
• Filed: 06/17/2013
• Issued: 02/02/2016
• Est. Priority Date: 03/22/2011
• 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
• Primary Examiner(s): Mehedi, Morshed
• Application Number:
  US13/919,701
• Time in Patent Office: 960 Days
• US Class Current: 1/1
• 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,

receiving data objects from customers of a data storage service;

for each data object of at least a plurality of the data objects;

storing the data object in an intermediate data storage subsystem;

prior to removing the data object from the intermediate data storage subsystem to a persistent data storage subsystem, providing, to a customer associated with the data object, an identifier for the data object that includes, in encrypted form, information usable to retrieve the data object after the data object is removed from the intermediate data storage subsystem;

generating a first cryptographic key for the data object;

encrypting the data object using the first cryptographic key;

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

redundantly storing, in the persistent data storage subsystem, the encrypted data object and the encrypted first cryptographic key using a plurality of data storage devices used by the data storage service to persistently store the received data objects, 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 of the plurality of data storage devices, the plurality of 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;

encrypting the second cryptographic key using a third cryptographic key; and

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

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

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

encrypting the data object includes encrypting the plurality of shards; and

redundantly storing the encrypted data object includes distributing the plurality of shards among the plurality of data storage devices.

3. The computer-implemented method of claim 1, wherein encrypting the data object and encrypting the first cryptographic key are each performed using a symmetric key cryptographic algorithm.

4. The computer-implemented method of claim 1, wherein encrypting the third key is performed using a public key cryptographic algorithm.

5. The computer-implemented method of claim 1, wherein encrypting the first cryptographic key using the second cryptographic key is performed for multiple different first cryptographic keys using the same second cryptographic key.

6. The computer-implemented method of claim 1, further comprising storing, with the data object, information that associates the first cryptographic key with an identifier for the second cryptographic key that distinguishes the second cryptographic key from one or more other second cryptographic keys.

7. The computer-implemented method of claim 1, wherein redundantly storing the encrypted second cryptographic key includes redundantly storing with the encrypted second cryptographic key one or more encrypted other second cryptographic keys.

8. A system, comprising:

a second data store comprising a plurality of data storage devices;

a first data store configured to store data until the data is removed for storage in the second data store; and

a subsystem configured to;

obtain data objects to be stored among the plurality of data storage devices; and

for each data object of at least a plurality of the data objects;

while the data object is in the first data store, provide an identifier that is usable to obtain the data object after the data object is removed from the first data store;

encrypt the data object with a first cryptographic key;

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

redundantly store, in the second data store, the encrypted data object and the encrypted first cryptographic key among the plurality of data storage devices, wherein the subsystem redundantly stores the encrypted data object by at least storing a plurality of shards such that each shard of the plurality of shards is stored in a different data storage device, the plurality of 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.

9. The system of claim 8, wherein each data object of the plurality of the data objects is encrypted with a different first cryptographic key.

10. The system of claim 8, wherein the subsystem comprises a web interface system that provides asynchronous access to the data objects via web service calls that include corresponding identifiers for the data objects.

11. The system of claim 8, wherein:

encrypting the data object includes applying a redundancy encoding scheme to the encrypted data object to generate the plurality of shards.

12. The system of claim 8, wherein redundantly storing the encrypted first cryptographic key includes storing replicas of the encrypted first cryptographic key.

13. The system of claim 8, wherein the subsystem is further configured to:

obtain a new second cryptographic key; and

redundantly store, among the plurality of data storage devices, the second cryptographic key and the new second cryptographic key, each of the second cryptographic key and the new second cryptographic key encrypted under a third key.

14. A computer-implemented method, comprising:

obtaining data objects to be stored among a plurality of data storage devices of a second data store; and

for each data object of at least a plurality of the data objects;

while the data object is in a first data store configured to store data until the data is remove for storage in the second data store, providing an identifier that is usable to obtain the data object after the data object is removed from the first data store;

encrypting the data object with a first cryptographic key;

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

redundantly storing, in the second data store, the encrypted data object and the encrypted first cryptographic key among the plurality of data storage devices, wherein redundantly storing the encrypted data object comprises storing a plurality of shards such that each shard of the plurality of shards is stored in a different data storage device, the plurality of 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.

15. The computer-implemented method of claim 14, wherein each data object of the plurality of the data objects is encrypted with a different first cryptographic key.

16. The computer-implemented method of claim 14, further comprising providing a web interface that provides asynchronous access to the data objects via web service calls that include corresponding identifiers for the data objects.

17. The computer-implemented method of claim 14, further comprising applying a redundancy encoding scheme to the encrypted data object to generate the plurality of shards.

18. The computer-implemented method of claim 14, wherein redundantly storing the encrypted first cryptographic key includes storing replicas of the encrypted first cryptographic key.

19. The computer-implemented method of claim 14, further comprising:

obtaining a new second cryptographic key; and

redundantly storing, among the plurality of data storage devices, the second cryptographic key and the new second cryptographic key, each of the second cryptographic key and the new second cryptographic key encrypted under a third key.

20. The computer-implemented method of claim 14, further comprising:

encrypting the second cryptographic key using a third cryptographic key; and

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

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

obtain data objects to be stored among a plurality of data storage devices of a second data store; and

for each data object of at least a plurality of the data objects;

while the data object is in a first data store configured to store data until the data is remove for storage in the second data store, provide an identifier that is usable to obtain the data object after the data object is removed from the first data store;

encrypt the data object with a first cryptographic key;

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

redundantly store, in the second data store, the encrypted data object and the encrypted first cryptographic key among the plurality of data storage devices, wherein redundantly storing the encrypted data object comprises storing a plurality of shards such that each shard of the plurality of shards is stored in a different data storage device, the plurality of 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.

22. The non-transitory computer-readable storage medium of claim 21, wherein each data object of the plurality of the data objects is encrypted with a different first cryptographic key.

23. The non-transitory computer-readable storage medium of claim 21, further storing instructions that, as a result of being executed by the one or more processors, cause the computer system to provide an interface that provides asynchronous access to the data objects via service calls that include corresponding identifiers for the data objects.

24. The non-transitory computer-readable storage medium of claim 21, further storing instructions that, as a result of being executed by the one or more processors, cause the computer system to apply a redundancy encoding scheme to the encrypted data object to generate the plurality of shards.

25. The non-transitory computer-readable storage medium of claim 21, wherein the instructions that cause the computer system to redundantly store the encrypted data object and the encrypted first cryptographic key cause the computer system to store replicas of the encrypted first cryptographic key.

26. The non-transitory computer-readable storage medium of claim 21, further storing instructions that, as a result of being executed by the one or more processors, cause the computer system to:

obtain a new second cryptographic key; and

redundantly store, among the plurality of data storage devices, the second cryptographic key and the new second cryptographic key, each of the second cryptographic key and the new second cryptographic key encrypted under a third key.