Data de-duplication among untrusted entities

Patent metadata

Field	Value
Publication number	US-11218296-B2
Application number	US-201916505269-A
Country	US
Kind code	B2
Filing date	Jul 8, 2019
Priority date	Feb 9, 2019
Publication date	Jan 4, 2022
Grant date	Jan 4, 2022

Abstract

A data storage system allows data to be encrypted and de-duplicated at the same system. By way of example, a server of the data storage system may request a client device which intends to upload a data block to transmit a first fingerprint of the data block to the server. The first fingerprint may be derived from the plaintext of the data block. The server may apply a one-way function to the first fingerprint to generate an encryption key and transmit the encryption key to the client device. The client device uses the encryption key to encrypt the data block and generates a second fingerprint which is derived from the ciphertext of the data block. The server uses both the first fingerprint and the second fingerprint to verify the data block and the legitimacy of the client attempting to upload the data block.

First claim

What is claimed is:

1. A computer-implemented method, comprising:
receiving, by a server and from a client device, a first fingerprint derived from a plaintext of a data block to be uploaded to a data store;
applying, by the server, a one-way function to the first fingerprint to generate an encryption key;
transmitting, by the server, the encryption key generated by the server to the client device;
receiving, by the server, a second fingerprint from the client device, the second fingerprint derived from a ciphertext of the data block encrypted by the client device using the encryption key;
determining, by the server, whether the ciphertext of the data block is a duplicated copy that has already been saved in the data store by determining whether the second fingerprint is referenced in a data index for the data store; and
preforming a de-duplication of the data block upon determining that the ciphertext of the data block is duplicative.

2. The computer-implemented method of claim 1 , wherein the one-way function is a hash function that generates a hash of the first fingerprint as the encryption key.

3. The computer-implemented method of claim 1 , further comprising:
providing, in response to the second fingerprint not being referenced in the data index, an upload instruction to the client device for the client device to upload the data block to the data store;
adding the second fingerprint to the data index; and
associating, in the data index, a client identifier, which corresponds to a client of the client device, with the second fingerprint and the uploaded data block stored in the data store.

4. The computer-implemented method of claim 3 , wherein the upload instruction comprises an address of the data store for the data block to be uploaded to the data store.

5. The computer-implemented method of claim 1 , wherein the de-duplication of the data block comprises:
comparing, in response to the second fingerprint being referenced in the data index, a received first fingerprint to a stored first fingerprint, wherein the received first fingerprint is the first fingerprint transmitted from the client device and the stored first fingerprint is a value that is associated with the second fingerprint in the data index; and
determining whether the received first fingerprint matches the stored first fingerprint.

6. The computer-implemented method of claim 5 , wherein the value of the stored first fingerprint represents a digest of a data block stored in the data store, the data block is associated with the second fingerprint in the data index.

7. The computer-implemented method of claim 5 , further comprising:
associating, in response to the received first fingerprint matching the stored first fingerprint, a client identifier corresponding to a client of the client device with the second fingerprint in the data index.

8. The computer-implemented method of claim 5 , further comprising:
retrieving, in response to the received first fingerprint not matching the stored first fingerprint, a stored data block from the data store, wherein the stored data block is stored in the data store and is associated with the second fingerprint in the data index;
calculating a third fingerprint that is derived from a plaintext of the stored data block retrieved from the data store; and
comparing the third fingerprint to the received first fingerprint and to the stored first fingerprint.

9. The computer-implemented method of claim 8 , further comprising:
rejecting, in response to the third fingerprint matching the stored first fingerprint but not the received first fingerprint, a request from the client device to store the data block to the data store.

10. The computer-implemented method of claim 8 , further comprising:
providing, in response to the third fingerprint matching the received first fingerprint but not the stored first fingerprint, an upload instruction to the client device for the client device to upload the data block to the data store; and
dis-associating a client who previously uploaded the stored data block from the second fingerprint in the data index.

11. The computer-implemented method of claim 10 , further comprising:
flagging the client who previously uploaded the stored data block as a potentially malicious party.

12. The computer-implemented method of claim 1 , wherein the data store is an object data store, and the second fingerprint is used as an index entry of data block in the data index.

13. The computer-implemented method of claim 1 , wherein the data store is a de-duplicated data storage and the data index uses fingerprints of ciphertexts of encrypted data to check duplications.

14. A system comprising:
a server storing a data index, the data index using fingerprints of ciphertexts of encrypted data to reference the encrypted data stored in a data store, wherein the server comprising one or more processors and memory, the memory is configured to store instructions, the instructions, when executed by the one or more processors, cause the one or more processor to:
receive, by the server and from a client device, a first fingerprint derived from a plaintext of a data block to be uploaded to the data store;
apply, by the server, a one-way function to the first fingerprint to generate an encryption key;
transmit, by the server, the encryption key generated by the server to the client device;
receive, by the server, a second fingerprint from the client device, the second fingerprint derived from a ciphertext of the data block encrypted by the client device using the encryption key;
determine, by the server, whether the ciphertext of the data block is a duplicated copy that has already been saved in the data store by determining whether the second fingerprint is referenced in the data index; and
preforming a de-duplication of the data block based on whether the ciphertext of the data block is determined to be duplicative;

an interface communicated to the server and run at the client device, the interface configured to:
cause the client device to encrypt the data block using the encryption key when the encryption key is received at the client device.

15. The system of claim 14 , further comprising:
the data store storing data, at least some of the data being the encrypted data.

16. The system of claim 14 , wherein the data store is an object data store.

17. The system of claim 14 , wherein the server is further configured to:
compare, in response to the second fingerprint being referenced in the data index, a received first fingerprint to a stored first fingerprint, wherein the received first fingerprint is the first fingerprint transmitted from the client device and the stored first fingerprint is a value that is associated with the second fingerprint in the data index; and
determine whether the received first fingerprint matches the stored first fingerprint.

18. The system of claim 17 , wherein the server is further configured to:
retrieving, in response to the received first fingerprint not matching the stored first fingerprint, a stored data block from the data store, wherein the stored data block is stored in the data store and is associated with the second fingerprint in the data index;
calculating a third fingerprint that is derived from a plaintext of the stored data block retrieved from the data store; and
comparing the third fingerprint to the received first fingerprint and to the stored first fingerprint.

19. A non-transitory computer readable medium comprising stored instructions

Assignees

• Druva Inc

Inventors

• Gottipati Srikiran
• Borate Milind

Classifications

• H04L9/0861 Primary

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

• G06F3/067

  Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS] · CPC title

• G06F3/0623

  in relation to content · CPC title

• G06F3/0641

  De-duplication techniques · CPC title

• G06F3/0608

  Saving storage space on storage systems · CPC title