Techniques and systems for durable encryption and deletion in data storage systems

• US 10,248,793 B1
• Filed: 12/16/2015
• Issued: 04/02/2019
• Est. Priority Date: 12/16/2015
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Kirschner, James Caleb
• Primary Examiner(s): Arani, Taghi T
• Assistant Examiner(s): Champakesan, Badrinarayanan
• Application Number:
  US14/971,722
• Time in Patent Office: 1,203 Days
• Field of Search: 713193
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: G06F 2221/2107 File encryption
• CPC Class Codes: G06F 2221/2143 Clearing memory, e.g. to prevent the data from being stolen
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0623 in relation to content
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• 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/062 for key distribution, e.g. centrally by trusted party cryptographic mechanisms or cryptographic arrangements for key distribution involving a central third party H04L9/0819
• CPC Class Codes: H04L 9/0816 Key establishment, i.e. cryptographic processes or cryptographic protocols whereby a shared secret becomes available to two or more parties, for subsequent use
• 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/0894 Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage

Abstract

A computer system, such as a data storage system, implements techniques for deleting durably stored data without affecting the availability or durability of other data associated therewith. In some embodiments, data is encrypted prior to redundancy coding such that deletion of an encryption key used to encrypt the data renders that data inaccessible, but other data bundled in the same redundancy coded bundle remains available. In such embodiments, a shard containing deleted data may still be usable to regenerate other, non-deleted or live data still extant in the same bundle of shards.

Claims

1. A computer-implemented method, comprising:

in response to receiving a data storage request for data to be stored in a plurality of volumes of durable storage of a data storage system, storing the data by at least;

encrypting the data using an encryption key provided by a key management service to produce encrypted data;

and, redundancy coding, using a redundancy code, at least the encrypted data to generate a bundle of bundle-encoded shards, a quorum quantity of which is sufficient to reconstruct original data associated with the bundle, the bundle of bundle-encoded shards including at least;

an identity shard that contains an original form of the encrypted data, and

encoded shards representing a redundancy coded form of the encrypted data;

and in response to receiving a deletion request to delete the data, rendering the data storage system incapable of producing the data using the identity shards by discarding the encryption key,

wherein other data associated with the bundle is recoverable using the identity shard.

2. The computer-implemented method of claim 1, further comprising, in further response to receiving the deletion request, copying other data not subject to the deletion request in the identity shard to another shard in a different bundle prior to discarding the encryption key.

3. The computer-implemented method of claim 1, further comprising, in further response to receiving the deletion request, discarding the encryption key after a period of time after receiving the deletion request, so as to allow receipt of another deletion request that is associated with other data associated with the identity shard.

4. The computer-implemented method of claim 1, wherein the bundle is associated with a grid of grid-encoded shards.

21. The computer-implemented method of claim 2, wherein the other shard in the different bundle is another identity shard.

22. The computer-implemented method of claim 2, further comprising regenerating the bundle-encoded shards of the bundle in response to copying the other data.

5. A system, comprising:

at least one computing device having one or more processors and memory including executable instructions that, as a result of being executed, implements one or more services to at least;

process a data storage request by at least;

encrypting data associated with the data storage request using an encryption key to produce encrypted data; and

using a redundancy code, associating the encrypted data with a bundle of shards that includes sufficient information to regenerate data represented by the bundle of shards using a quantity of member shards that is less than a quantity of shards in the bundle, the bundle of shards including an identity shard that includes an original form of a portion of the encrypted data; and

process a deletion request to delete the portion of the encrypted data by at least discarding the encryption key, wherein the identity shard is usable at least in part after the encryption key has been discarded to regenerate other data in the bundle than the portion.

6. The system of claim 5, wherein:

the bundle of shards further includes at least;

other identity shards, and

encoded shards representing a redundancy coded form of the encrypted data, and

discarding the encryption key renders the bundle capable of regenerating other data in the bundle using one or more of the other identity shards with which the encryption key is associated.

7. The system of claim 5, wherein the encryption key is generated by a key management service associated with the at least one computing device.

8. The system of claim 5, wherein the bundle of shards includes at least one identity shard that includes the encrypted data.

9. The system of claim 5, wherein the bundle is part of a grid of grid encoded shards.

10. The system of claim 5, wherein the bundle includes data for a plurality of objects.

11. The system of claim 10, wherein some objects of the plurality of objects share the encryption key.

12. The system of claim 11, wherein the services further move other data not subject to the deletion request to a different bundle prior to discarding the encryption key.

13. A non-transitory computer-readable storage medium having stored thereon executable instructions that, if executed by one or more processors of a computer system, cause the computer system to at least:

store data associated with an incoming data storage request by at least;

encrypting the data using at least one encryption key to produce encrypted data;

generating shards from the encrypted data, using a redundancy code; and

associating the shards into a bundle of shards that contains a quantity of members such that fewer shards than the quantity of members is sufficient to regenerate data associated with the bundle, the bundle of shards including an identity shard that includes an original form of a portion of the encrypted data;

in response to a deletion request, delete the portion of the encrypted data associated with the deletion request by at least discarding the at least one encryption key; and

regenerate, at least in part using the identity shard after the at least one encryption key has been discarded, other data in an associated bundle.

14. The non-transitory computer-readable storage medium of claim 13, wherein at least some of the bundles of shards include identity shards.

15. The non-transitory computer-readable storage medium of claim 13, wherein the executable instructions further comprise instructions that cause the computer system to store the data by at least allocating the shards to volumes of the computer system.

16. The non-transitory computer-readable storage medium of claim 13, wherein the data includes a plurality of customer objects associated with the incoming data storage request.

17. The non-transitory computer-readable storage medium of claim 13, wherein the redundancy code is an erasure code.

18. The non-transitory computer-readable storage medium of claim 13, wherein the executable instructions further comprise instructions that encrypt the data by using a first encryption key for a first data object and a different second encryption key for a second data object associated with the data.

19. The non-transitory computer-readable storage medium of claim 13, wherein the deletion request is associated with a garbage collection routine of the computer system.

20. The non-transitory computer-readable storage medium of claim 13, wherein the at least one encryption key is stored by the computer system at a level of durability that is equal to or greater than the stored data.