Cross-region recovery of encrypted, erasure-encoded data

• US 9,158,927 B1
• Filed: 06/24/2013
• Issued: 10/13/2015
• Est. Priority Date: 06/24/2013
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Franklin, Paul David, Donlan, Bryan James
• Primary Examiner(s): SHEHNI, GHAZAL B
• Application Number:
  US13/925,497
• Time in Patent Office: 841 Days
• Field of Search: 713189-194
• US Class Current: 1/1
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services

Abstract

Reliable and efficient storage and reconstruction of secure data files is provided. Encrypted fragments are generated by exclusive-OR (XOR) based erasure-encoding and XOR encryption of data files. At least some of the encrypted fragments, and preferably at least two copies of such encrypted fragments, are stored at two or more locations, such as but not limited to two or more servers in two or more regional storage systems. Fragments are retrieved from one or more of the multiple locations and the original data file is reconstructed, even if different encryption techniques have been used. If not enough valid fragments from that original data file can be identified then hash values, checksums, seeds, and other techniques may be used to distinguish files and to identify related or identical files which may be used to reconstruct the data file.

Claims

1. A computer-implemented method for storing and recovering a data file, the method comprising:

receiving a data file for storage;

producing encrypted, erasure-encoded fragments from the received data file by using first and second exclusive-OR (XOR) encryption techniques, and by using an XOR-based erasure-encoding technique, the second XOR encryption technique being different than the first XOR encryption technique;

storing at least some of the encrypted, erasure-encoded fragments in a plurality of storage devices, each storage device storing at least one of the encrypted, erasure-encoded fragments;

receiving a request to reconstruct the data file;

retrieving a number of encrypted, erasure-encoded fragments adequate to reconstruct the data file; and

reconstructing the data file from the retrieved, encrypted, erasure-encoded fragments.

2. The computer-implemented method of claim 1 wherein at least some of the encrypted, erasure-encoded fragments are produced using the first XOR encryption technique and the XOR-based erasure-encoding technique, and at least some others of the encrypted, erasure-encoded fragments are produced using the second XOR encryption technique and the XOR-based erasure-encoding technique, the first and second XOR encryption techniques using different encryption algorithms, different encryption keys, or both.

3. The computer-implemented method of claim 1 wherein storing the at least some of the encrypted, erasure-encoded fragments in a plurality of storage devices comprises storing at least one of the encrypted, erasure-encoded fragments in a first storage device, and storing another of the encrypted, erasure-encoded fragments in a second storage device, the first storage device and the second storage device being independent with respect to each other.

4. The computer-implemented method of claim 1 wherein producing encrypted, erasure-encoded fragments comprises either:

encrypting the data file using the first XOR encryption technique and erasure-encoding the encrypted data file using the XOR-based erasure-encoding technique to produce the encrypted, erasure-encoded fragments;

or

erasure-encoding the data file using the XOR-based erasure-encoding technique, erasure-encoding an encryption vector from the first XOR encryption technique using the XOR-based erasure-encoding technique, and then XORing the erasure-encoded data file and the erasure-encoded encryption vector to produce the encrypted, erasure-encoded fragments.

5. The computer-implemented method of claim 1 wherein:

receiving the data file for storage comprising receiving the data file a first time and receiving the data file a second time;

producing encrypted, erasure-encoded fragments from the received data file comprises producing first encrypted, erasure-encoded fragments from the data file received the first time by using the first XOR encryption technique and the XOR-based erasure-encoding technique, and producing second encrypted, erasure-encoded fragments from the data file received the second time by using the second XOR encryption technique and the XOR-based erasure-encoding technique; and

storing at least some of the encrypted, erasure-encoded fragments in a plurality of storage devices comprises storing at least one of the first encrypted, erasure-encoded fragments in a first storage device of the plurality of storage devices and storing at least one of the second encrypted, erasure-encoded fragments in a second storage device of the plurality of storage devices.

6. The computer-implemented method of claim 1 wherein storing the at least some of the encrypted, erasure-encoded fragments in a plurality of storage devices comprises storing at least one of the encrypted, erasure-encoded fragments in a first storage device, and storing at least one of the encrypted, erasure-encoded fragments in a second storage device, the first storage device and the second storage device being independent with respect to each other.

7. The computer-implemented method of claim 1 wherein reconstructing the data file from the retrieved, encrypted, erasure-encoded fragments comprises:

(1) combining the retrieved, encrypted, erasure-encoded fragments to produce combined fragments, erasure-decoding the combined fragments to produce erasure-decoded fragments, and decrypting the erasure-decoded fragments;

or

(2) individually decrypting the retrieved, encrypted, erasure-encoded fragments to provide decrypted, erasure-encoded fragments, combining the decrypted fragments, and erasure-decoding the combined decrypted fragments.

8. The computer-implemented method of claim 1 wherein reconstructing the data file from the retrieved, encrypted, erasure-encoded fragments comprises:

decrypting the retrieved, encrypted, erasure-encoded fragments which were produced using the first encryption technique to provide first erasure-encoded fragments;

decrypting the retrieved, encrypted, erasure-encoded fragments which were produced using the second encryption technique to provide second erasure-encoded fragments;

combining the first erasure-encoded fragments and the second erasure-encoded fragments; and

erasure-decoding the combined, erasure-encoded fragments.

9. The computer-implemented method of claim 1 wherein retrieving a number of encrypted, erasure-encoded fragments adequate to reconstruct the data file comprises:

retrieving the retrieved, encrypted, erasure-encoded fragments which were produced using the first encryption technique from a first storage device; and

retrieving the retrieved, encrypted, erasure-encoded fragments which were produced using the second encryption technique from a second, independent storage device.

10. A computer-implemented method for a computer system for storing and recovering a data file, the method comprising:

receiving a data file for storage;

producing encrypted, erasure-encoded fragments from the received data file using a first exclusive-OR (XOR) encryption technique and an XOR-based erasure-encoding technique, the second XOR encryption technique being different than the first XOR encryption technique;

storing at least one of the encrypted, erasure-encoded fragments in at least one storage device;

either (1) sending the data file to a regional storage system for XOR encryption using a second XOR encryption technique and the XOR-based erasure-encoding technique, and for storage of at least one encrypted, erasure-encoded fragments produced thereby, or (2) generating fragments from the data file using the XOR-based erasure-encoding technique, and sending the fragments to a regional storage system for XOR encryption using a second XOR encryption technique, and for storage of at least one of the encrypted, erasure-encoded fragments produced thereby;

receiving a request to reconstruct the data file;

retrieving a number of encrypted, erasure-encoded fragments adequate to reconstruct the data file; and

reconstructing the data file from the retrieved, encrypted, erasure-encoded fragments.

11. The computer-implemented method of claim 10 wherein the first and second XOR encryption techniques use different encryption algorithms, different encryption keys, or both.

12. The computer-implemented method of claim 10 wherein storing at least one of the encrypted, erasure-encoded fragments in at least one storage device comprises storing the at least one of the encrypted, erasure-encoded fragments in a first storage device associated with the computer system;

and further comprising;

storing another of the encrypted, erasure-encoded fragments in a second storage device, the second storage device being independent of the first storage device.

13. The computer-implemented method of claim 10 wherein the regional storage system is independent of the computer system.

14. The computer-implemented method of claim 10 wherein producing encrypted, erasure-encoded fragments from the received data file comprises either:

encrypting the received data file using the first XOR encryption technique and erasure-encoding the encrypted data file using the XOR-based erasure-encoding technique to produce the encrypted, erasure-encoded fragments;

or

erasure-encoding the received data file using the XOR-based erasure-encoding technique, erasure-encoding an encryption vector from the first XOR encryption technique using the XOR-based erasure-encoding technique, and then XORing the erasure-encoded data file and the erasure-encoded encryption vector to produce the encrypted, erasure-encoded fragments.

15. The computer-implemented method of claim 10 wherein reconstructing the data file from the retrieved, encrypted, erasure-encoded fragments comprises:

(1) combining the retrieved, encrypted, erasure-encoded fragments, erasure-decoding the combined fragments to produce an encrypted data file, and decrypting the encrypted data file;

or

(2) individually decrypting the retrieved, encrypted, erasure-encoded fragments to provide decrypted, erasure-encoded fragments, combining the decrypted, erasure-encoded fragments, and erasure-decoding the decrypted, erasure-encoded fragments.

16. The computer-implemented method of claim 10 wherein retrieving a number of encrypted, erasure-encoded fragments adequate to reconstruct the data file comprises:

retrieving encrypted, erasure-encoded fragments from the at least one storage device;

decrypting the retrieved encrypted, erasure-encoded fragments to provide first decrypted, erasure-encoded fragments;

receiving second decrypted, erasure-encoded fragments from the regional storage system;

combining the first decrypted, erasure-encoded fragments and the second decrypted, erasure-encoded fragments; and

erasure-decoding the combined decrypted, erasure-encoded fragments.

17. A system for storing and recovering a data file, the system comprising a computer, the computer comprising:

a memory device containing operating instructions and files;

a network interface device for sending and receiving data over a network;

a processor, communicatively coupled to the memory device and to network interface device, the processor executing operating instructions to;

receive a data file for storage;

produce encrypted, erasure-encoded fragments from the received data file using a first exclusive-OR (XOR) encryption technique and an XOR-based erasure-encoding technique;

store at least one of the encrypted, erasure-encoded fragments in at least one storage device;

either (1) send the data file to a regional storage system for XOR encryption using a second XOR encryption technique and the XOR-based erasure-encoding technique, and for storage of at least one encrypted, erasure-encoded fragments produced thereby, or (2) generate fragments from the data file using the XOR-based erasure-encoding technique, and send the fragments to a regional storage system for XOR encryption using a second XOR encryption technique, and for storage of at least one of the encrypted, erasure-encoded fragments produced thereby;

the second XOR encryption technique being different than the first XOR encryption technique;

receive a request to reconstruct the data file;

retrieve a number of encrypted, erasure-encoded fragments adequate to reconstruct the data file; and

reconstruct the data file from the retrieved, encrypted, erasure-encoded fragments.

18. The system of claim 17 wherein the computer produces encrypted, erasure-encoded fragments from the received data file by executing operating instructions:

to encrypt the received data file using the first XOR encryption technique and to erasure-encode the encrypted data file using the XOR-based erasure-encoding technique to produce the encrypted, erasure-encoded fragments;

or

to erasure-encode the received data file using the XOR-based erasure-encoding technique, to erasure-encode an encryption vector from the first XOR encryption technique using the XOR-based erasure-encoding technique, and then to XOR the erasure-encoded data file and the erasure-encoded encryption vector to produce the encrypted, erasure-encoded fragments.

19. The system of claim 17 wherein the computer reconstructs the data file from the retrieved, encrypted, erasure-encoded fragments by executing operating instructions:

(1) to combine the retrieved, encrypted, erasure-encoded fragments, to erasure-decode the combined fragments to produce an encrypted data file, and to decrypt the encrypted data file;

or

(2) to individually decrypt the retrieved, encrypted, erasure-encoded fragments to provide decrypted, erasure-encoded fragments, to combine the decrypted, erasure-encoded fragments, and to erasure-decode the combined fragments.

20. The system of claim 17 wherein the computer:

retrieves a number of encrypted, erasure-encoded fragments adequate to reconstruct the data file by executing operating instructions to retrieve first encrypted, erasure-encoded fragments from the at least one storage device and to retrieve second decrypted, erasure-encoded fragments from the regional storage system;

reconstructs the data file from the first encrypted, erasure-encoded fragments and the second encrypted, erasure-encoded fragments by executing operating instructions to decrypt the retrieved encrypted, erasure-encoded fragments to provide first decrypted, erasure-encoded fragments, to combine the first decrypted, erasure-encoded fragments and the second decrypted, erasure-encoded fragments, and to erasure-decode the combined decrypted, erasure-encoded fragments.

21. A computer-readable storage medium having computer-executable instructions stored thereupon for storing and recovering a data file and the instructions, when executed by a computer, cause the computer to:

receive a data file for storage;

produce encrypted, erasure-encoded fragments from the received data file using a first exclusive-OR (XOR) encryption technique and an XOR-based erasure-encoding technique;

store at least one of the encrypted, erasure-encoded fragments in at least one storage device;

either (1) send the data file to a regional storage system for XOR encryption using a second XOR encryption technique and the XOR-based erasure-encoding technique, and for storage of at least one encrypted, erasure-encoded fragments produced thereby, or (2) generate fragments from the data file using the XOR-based erasure-encoding technique, and send the fragments to a regional storage system for XOR encryption using a second XOR encryption technique, and for storage of at least one of the encrypted, erasure-encoded fragments produced thereby;

the second XOR encryption technique being different than the first XOR encryption technique;

receive a request to reconstruct the data file;

retrieve a number of encrypted, erasure-encoded fragments adequate to reconstruct the data file; and

reconstruct the data file from the retrieved, encrypted, erasure-encoded fragments.

22. The computer-readable storage medium of claim 21, wherein the computer-readable storage medium has further computer-executable instructions stored thereupon to produce encrypted, erasure-encoded fragments from the received data file which, when executed by the computer, cause the computer:

to encrypt the received data file using the first XOR encryption technique and to erasure-encode the encrypted data file using the XOR-based erasure-encoding technique to produce the encrypted, erasure-encoded fragments;

or

to erasure-encode the received data file using the XOR-based erasure-encoding technique, to erasure-encode an encryption vector from the first XOR encryption technique using the XOR-based erasure-encoding technique, and then to XOR the erasure-encoded data file and the erasure-encoded encryption vector to produce the encrypted, erasure-encoded fragments.

23. The computer-readable storage medium of claim 21, wherein the computer-readable storage medium has further computer-executable instructions stored thereupon to reconstruct the data file from the retrieved, encrypted, erasure-encoded fragments which, when executed by the computer, cause the computer:

(1) to combine the retrieved, encrypted, erasure-encoded fragments, to erasure-decode the combined fragments to produce an encrypted data file, and to decrypt the encrypted data file;

or

(2) to individually decrypt the retrieved, encrypted, erasure-encoded fragments to provide decrypted, erasure-encoded fragments, to combine the decrypted, erasure-encoded fragments, and to erasure-decode the decrypted, erasure-encoded fragments.

24. The computer-readable storage medium of claim 21, wherein the computer-readable storage medium has further computer-executable instructions stored thereupon:

to retrieve a number of encrypted, erasure-encoded fragments adequate to reconstruct the data file which, when executed by the computer, cause the computer to retrieve first encrypted, erasure-encoded fragments from the at least one storage device and to receive second decrypted, erasure-encoded fragments from the regional storage system;

to reconstruct the data file from the first encrypted, erasure-encoded fragments and the second encrypted, erasure-encoded fragments which, when executed by the computer, cause the computer to decrypt the retrieved encrypted, erasure-encoded fragments to provide first decrypted, erasure-encoded fragments, to combine the first decrypted, erasure-encoded fragments and the second decrypted, erasure-encoded fragments, and to erasure-decode the combined decrypted, erasure-encoded fragments.