Methods and systems for storage of large data objects

• US 8,782,441 B1
• Filed: 03/07/2013
• Issued: 07/15/2014
• Est. Priority Date: 03/16/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Osterwalder, Cyrill, DeCanniere, Christophe, Przydatek, Bartosz Jan, Shankar, Umesh
• Primary Examiner(s): Hailu, Teshome
• Application Number:
  US13/788,982
• Time in Patent Office: 495 Days
• Field of Search: 713/193
• US Class Current: 713/193
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 2221/2107 File encryption
• CPC Class Codes: H04L 9/0894 Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage
• CPC Class Codes: H04L 9/3242 involving keyed hash functions, e.g. message authentication codes [MACs], CBC-MAC or HMAC

Abstract

A storage service receives a binary large object (blob) for storage, and the service creates first and second sets of data chunks from the blob. The chunks in the first set together equal the blob, and the service uses one or more encryption keys to encrypt each of the data chunks in the first set. The chunks in the second set also together equal the blob. The service assigns a message authentication code (MAC) to each data chunk in the second set. The service stores the encrypted data chunks in one or more data stores, and it stores the encryption keys and the MACs as metadata in a metadata memory.

Claims

1. A method, comprising:

receiving, by a storage service, a binary large object;

by a processor of the storage service, creating a first set of data chunks, wherein each of the data chunks in the first set is a subset of the object, and together the data chunks in the first set equal the object;

by the processor, assigning an encryption key to each data chunk in the first set;

encrypting each of the data chunks in the first set to form a set of encrypted data chunks;

by the processor, creating a second set of ciphertext chunks, wherein the ciphertext chunks in the second set will, taken together and decrypted, form the binary large object;

by the processor, assigning a message authentication code (MAC) to each data chunk in the second set;

storing the encrypted data chunks in one or more data stores;

storing the encryption keys and the MACs as metadata in a metadata memory, wherein the metadata memory is separate from the one or more data stores, and wherein storing the encryption keys and the MACs as metadata comprises assigning a key, encrypting the metadata with the assigned key, and wrapping the assigned key;

receiving, by the storage service, an access request from a user, wherein the access request includes a user authentication credential;

verifying, by the storage service, the user authentication credential based on the access request;

accessing the metadata to retrieve the encryption keys and the MACs for the binary large object, wherein accessing the metadata comprises unwrapping the wrapped key to yield an unwrapped key, and

using the unwrapped key to decrypt the metadata;

retrieving the encrypted data chunks from the data store;

using the MACs to verify integrity of the encrypted data chunks;

using the encryption keys to decrypt the encrypted data chunks; and

returning the binary large object to the user.

2. The method of claim 1, wherein storing the metadata comprises assigning a metadata encryption key and using the metadata encryption key to encrypt the metadata.

3. The method of claim 1, wherein assigning the encryption key to at least one of the data chunks in the first set comprises determining a content-derived key for the at least one chunk.

4. The method of claim 1, wherein assigning the encryption key to at least one of the data chunks in the first set comprises generating a randomly-generated key for the at least one chunk.

5. The method of claim 1, further comprising storing, in the metadata, a data store location, wherein the data store location corresponds to a storage location of one or more of the data chunks in the first set or in the second set.

6. The method of claim 1, further comprising:

receiving, by the storage service, first user authentication information corresponding to a first authorized user of the binary large object; and

storing, in a memory that is separate from the data store, a first access control list, wherein the first access control list includes data relating to the first user authentication information.

7. The method of claim 6, wherein the memory in which the access control list is stored is also separate from the metadata memory.

8. The method of claim 6, further comprising:

receiving, by the storage service, a second instance of the binary large object;

receiving, by the storage service, second user authentication information corresponding to a second authorized user of the binary large object;

discarding the second instance of the binary large object without storing the second instance in the data store; and

storing, in a second access control list, data relating to the second user authentication information.

9. A method, comprising:

receiving, by a storage service, a binary large object;

by a processor of the storage service, creating a first set of data chunks, wherein each of the data chunks in the first set is a subset of the object, and together the data chunks in the first set equal the object;

by the processor, assigning an encryption key to each data chunk in the first set;

encrypting each of the data chunks in the first set to form a set of encrypted data chunks;

by the processor, creating a second set of ciphertext chunks, wherein the ciphertext chunks in the second set will, taken together and decrypted, form the binary large object;

by the processor, assigning a message authentication code (MAC) to each ciphertext chunk in the second set;

storing the encrypted data chunks in one or more data stores;

determining a data store location, wherein the data store location corresponds to a storage location of one or more of the data chunks in the first set;

storing the encryption keys, the data store location and the MACs as metadata in a metadata memory, wherein the metadata memory is separate from the one or more data stores, and wherein storing the metadata comprises assigning a metadata encryption key and using the metadata encryption key to encrypt the metadata;

receiving, by the storage service, an access request from a user, wherein the access request includes a user authentication credential;

verifying, by the storage service, the user authentication credential based on the access request;

accessing the metadata to retrieve the encryption keys and the MACs for the binary large object, wherein accessing the metadata comprises unwrapping the wrapped key to yield an unwrapped key, and using the unwrapped key to decrypt the metadata;

retrieving the encrypted data chunks from the data store;

using the MACs to verify integrity of the encrypted data chunks;

using the encryption keys to decrypt the encrypted data chunks; and

returning the binary large object to the user.

10. The method of claim 9, wherein assigning the encryption key to at least one of the data chunks in the first set comprises determining a content-derived key for the at least one chunk.

11. The method of claim 9, wherein assigning the encryption key to at least one of the data chunks in the first set comprises generating a randomly-generated key for the at least one chunk.

12. The method of claim 9, further comprising:

receiving, by the storage service, a second instance of the binary large object;

receiving, by the storage service, user authentication information corresponding to an authorized user of the binary large object;

discarding the second instance of the binary large object without storing the second instance in the data store; and

storing, in an access control list, data relating to the second user authentication information.

13. A system, comprising:

a storage service comprising one or more processors, a non-transitory memory containing program instructions, one or more data stores, and a metadata memory that is separate from the one or more data stores,

wherein the program instructions, when executed, instruct one or more of the processors to;

receive a binary large object;

create a first set of data chunks, wherein each of the data, chunks in the first set is a subset of the object, and together the data chunks in the first set equal the object;

assign an encryption key to each data chunk in the first set;

encrypt each of the data chunks in the first set to form a set of encrypted data chunks;

create a second set of ciphertext chunks, wherein each of the ciphertext chunks in the second set is a subset of an encrypted form of the binary large object, and together the ciphertext chunks in the second set equal the binary large object;

assign a message authentication code (MAC) to each ciphertext chunk in the second set;

store the encrypted data chunks in one or more of the data stores;

store the encryption keys and the MACs as metadata in the metadata memory wherein storing the metadata comprises assigning a metadata encryption key and using the metadata encryption key to encrypt the metadata;

receive an access request from a user, wherein the access request includes a user authentication credential;

verify the user authentication credential based on the access request;

access the metadata to retrieve the encryption keys and the MACs for the binary large object, wherein accessing the metadata comprises unwrapping the wrapped key to yield an unwrapped key, and using the unwrapped key to decrypt the metadata

retrieve the encrypted data chunks from the data store;

use the MACs to verify integrity of the encrypted data chunks;

use the encryption keys to decrypt the encrypted data chunks; and

return the binary large object to the user.

14. The system of claim 13, wherein the program instructions, when executed, also instruct one or more of the processors to store, in the metadata, a data store location, wherein the data store location corresponds to a storage location of one or more of the data chunks in the first set or the second set.

15. The system of claim 13, wherein the program instructions, when executed, also instruct one or more of the processors to:

receive first user authentication information corresponding to a first authorized user of the binary large object; and

store, in a memory that is separate from the data store, a first access control list, wherein the first access control list includes data relating to the first user authentication information.

16. The system of claim 15, wherein the program instructions, when executed, also instruct one or more of the processors to:

receive a second instance of the binary large object;

receive second user authentication information corresponding to a second authorized user of the binary large object;

discard the second instance of the binary large object without storing the second instance in the data store; and

store, in a second access control list, data relating to the second user authentication information.