Redundancy controls in convergent encryption using dynamic salt values

Patent metadata

Field	Value
Publication number	US-11329803-B2
Application number	US-202017037427-A
Country	US
Kind code	B2
Filing date	Sep 29, 2020
Priority date	Sep 29, 2020
Publication date	May 10, 2022
Grant date	May 10, 2022

Abstract

Systems and methods are described for providing storage of encrypted data sets, deduplication of such data sets, and control of the redundancy of those data sets. A form of modified convergent encryption can be employed, whereby an encryption key for a data set is selected based on a combination of the plaintext of the data set and a salt value, with the salt value being selected from a number of permutations corresponding to a desired redundancy of the data set in a storage system. Accordingly, a given data set can result in a number of ciphertexts equal to the desired redundancy, and deduplication can occur by removing duplicative instances of individual ciphertexts. Salt values can be selected according to a variety of criteria, including user-based, time-based, and location-based criteria.

First claim

What is claimed is:

1. A data storage system that conducts modified convergent encryption, in which a given plaintext is encrypted into one of a number of possible ciphertexts constrained by a desired redundancy of the plaintext on the data storage system, the data storage system comprising:
a distributed data store configured to store ciphertext; and
one or more processors of the data storage system configured to:
obtain from a client computing device an instruction to store a data set;
in response to the instruction to store the data set:
select a salt value from a constrained number of salt permutations corresponding to a target redundancy of the data set in the data storage system, wherein the salt value is selected according to at least one of a user requesting to store the data set, a time of the instruction to store the data set, a location on the distributed data store on which the data set is requested to be stored, or a state of present storage of the data set in the distributed data store;
add to plaintext of the data set the selected salt value;
hash the plaintext of the data set with the added salt value according to a cryptographic hashing algorithm to result in a hash value;
encrypt the plaintext of the data set using the hash value as an encryption key to result in ciphertext of the data set;
determine whether the ciphertext of the data set is currently stored within the distributed data store; and
when it is determined that the ciphertext of the data set is not currently stored within the distributed data store, store the ciphertext of the data set in the distributed data store.

2. The system of claim 1 , wherein the cryptographic hashing algorithm is one of a Secure Hash Algorithm (SHA) family algorithm or a BLAKE family algorithm.

3. The system of claim 1 , wherein to encrypt the plaintext of the data set, the one or more processors are configured to use at least one of a block cipher or a stream cipher.

4. The system of claim 1 , wherein the salt value is selected according to the user requesting to store the data set, and wherein the salt value is unique to the user.

5. The system of claim 1 , wherein the salt value is selected according to the user requesting to store the data set, and wherein the salt value is shared among a proportion of users of the system that is inversely proportional to the number of salt permutations.

6. A computer-implemented method implemented at a data storage system, the computer-implemented method comprising:
obtaining instructions to store a data set on the storage system;
selecting a salt value from a constrained number of salt permutations corresponding to a target redundancy of the data set in the storage system;
adding to plaintext of the data set the selected salt value;
hashing the plaintext of the data set with the added salt value according to a cryptographic hashing algorithm to result in a hash value;
encrypting the plaintext of the data set using the hash value as an encryption key to result in ciphertext of the data set; and
in response to determining that the ciphertext of the data set is not currently stored within the storage system, storing the ciphertext of the data set in the storage system.

7. The method of claim 6 , wherein the salt value is selected according to at least one of a user requesting to store the data set, a time of a request to store the data set, a location on the storage system on which the data set is requested to be stored, or a state of present storage of the data set in the storage system.

8. The method of claim 6 , wherein the salt value is selected according to a time of a request to store the data set, and wherein all requests to store data sets that are obtained over a time window share the salt value.

9. The method of claim 6 , wherein the salt value is selected according to a time of the instruction to store the data set, and wherein the salt value is probabilistically selected between two potential salt values, including a first potential salt value corresponding to a first period of time and a second potential salt value corresponding to a second period of time.

10. The method of claim 6 , wherein the salt value is selected according to a location on the storage system on which the data set is requested to be stored, and wherein different locations on the storage system are associated with different salt values.

11. The method of claim 10 , wherein different locations on the storage system are associated with isolated computing systems.

12. The method of claim 6 , wherein the salt value is selected according to a time of the instruction to store the data set.

13. The method of claim 6 , wherein the data set is a fixed-length block of a larger data set, and wherein the method further comprises storing, in a manifest corresponding to the larger data set, an identifier of the ciphertext of the data set and the encryption key with which the ciphertext of the data set is encrypted.

14. The method of claim 6 , wherein the salt value is selected according to a state of present storage of the data set in the storage system, and wherein the state of present storage indicates a number of redundant instances of the data set stored on the storage system.

15. One or more non-transitory computer-readable media comprising computer-executable instructions that, when executed by a computing system associated with a data storage system, cause the computing system to:
obtain instructions to store a data set on the data storage system;
select a salt value from a constrained number of salt permutations corresponding to a target redundancy of the data set in the storage system;
add to plaintext of the data set the selected salt value;
hash the plaintext of the data set with the added salt value according to a cryptographic hashing algorithm to result in a hash value;
encrypt the plaintext of the data set using the hash value as an encryption key to result in ciphertext of the data set; and
in response to a determination that the ciphertext of the data set is not currently stored within the storage system, store the ciphertext of the data set in the storage system.

16. The one or more non-transitory computer-readable media of claim 15 , wherein to add the salt value to the plaintext of the data set, the instruction cause the computing system to at least one of prepend or append the salt value to the plaintext of the data set.

17. The one or more non-transitory computer-readable media of claim 15 , wherein the instructions further cause the computing system to:
generate a message authentication code (MAC) for the ciphertext of the data set; and
determine whether the ciphertext of the data set is currently stored within the storage system by querying whether the MAC for the ciphertext of the data set matches a MAC of any ciphertext stored on the storage system.

18. The one or more non-transitory computer-readable media of claim 17 , wherein the MAC is at least one of a hash-based MAC (HMAC), a Galois/Counter Mode MAC (GMAC), or a Poly1305 MAC.

19. The one or more non-transitory computer-readable media of claim 17 , wherein the MAC is generated using a combination of the ciphertext of the data set and the encryption key with which the ciphertext of the data set is encrypted.

20. The one or more non-transitory computer-readable media of claim 17 , wherein to encrypt plaintext of the data set, the instructions cause the computing system to implement at least one of Advanced Encryption Standard (AES) encryption or ChaCha e

Assignees

• Amazon Tech Inc

Inventors

• Brooker Marc
• Surkatty Osman
• Manwaring Derek
• Danilov Mikhail
• Mcdonnell Peter Martin
• Schneider Stefan

Classifications

• H04L9/0643 Primary

  Hash functions, e.g. MD5, SHA, HMAC or f9 MAC · CPC title

• H04L9/0894

  Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage · CPC title

• H04L9/0637 Primary

  Modes of operation, e.g. cipher block chaining [CBC], electronic codebook [ECB] or Galois/counter mode [GCM] · CPC title

• H04L9/3242

  involving keyed hash functions, e.g. message authentication codes [MACs], CBC-MAC or HMAC · CPC title

• H04L9/0861

  Generation of secret information including derivation or calculation of cryptographic keys or passwords · CPC title