Redundant key management

Patent metadata

Field	Value
Publication number	US-9251097-B1
Application number	US-201313919701-A
Country	US
Kind code	B1
Filing date	Jun 17, 2013
Priority date	Mar 22, 2011
Publication date	Feb 2, 2016
Grant date	Feb 2, 2016

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.

First claim

What is claimed is:

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 , furth

Assignees

• Amazon Tech Inc

Inventors

• Kumar Sandeep
• Roth Gregory Branchek
• Rubin Gregory Alan
• Seigle Mark Christopher
• Tirdad Kamran

Classifications

• G06F12/1408 Primary

  by using cryptography (for digital transmission H04L9/00) · CPC title

• G06F11/1464

  for networked environments · CPC title

• H04L9/14 Primary

  using a plurality of keys or algorithms · CPC title

• H04L2209/24

  Key scheduling, i.e. generating round keys or sub-keys for block encryption · CPC title

• G06F21/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 title