Redundant key management

Patent metadata

Field	Value
Publication number	US-9904788-B2
Application number	US-201615004592-A
Country	US
Kind code	B2
Filing date	Jan 22, 2016
Priority date	Aug 8, 2012
Publication date	Feb 27, 2018
Grant date	Feb 27, 2018

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:
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.

Assignees

• Amazon Tech Inc

Inventors

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

Classifications

• G06F21/6209 Primary

  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

• H04L9/14

  using a plurality of keys or algorithms · CPC title

• G06F12/1408

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

• G06F11/1076

  Parity data used in redundant arrays of independent storages, e.g. in RAID systems · CPC title

• G06F11/1469

  Backup restoration techniques · CPC title