Efficient storage of encrypted data in a dispersed storage network

• US 8,819,452 B2
• Filed: 09/17/2010
• Issued: 08/26/2014
• Est. Priority Date: 11/25/2009
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Gladwin, S. Christopher, Abhijeet, Kumar, Dhuse, Greg, Resch, Jason K., Grube, Gary W., Markison, Timothy W.
• Primary Examiner(s): Eskandarnia, Arvin
• Application Number:
  US12/885,124
• Publication Number:
  US 20110126026A1
• Time in Patent Office: 1,439 Days
• Field of Search: 713/193
• US Class Current: 713/193
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: G06F 16/1752 based on file chunks
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: G06F 16/1827 Management specifically adapted to NAS management of storage area networks [SAN] G06F3/067
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: G06F 21/6272 by registering files or documents with a third party
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: G06F 2221/2107 File encryption
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• 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 69/04 Protocols for data compression, e.g. ROHC
• CPC Class Codes: H04L 9/0861 Generation of secret information including derivation or calculation of cryptographic keys or passwords

Abstract

A method begins with a processing module obtaining data to store and determining whether substantially similar data to the data is stored. When the substantially similar data is not stored, the method continues with the processing module generating a first encryption key based on the data, encoding the first encryption key into encoded data slices in accordance with an error coding dispersal storage function, and storing the encoded data slices in a dispersed storage network (DSN) memory. The method continues with the processing module encrypting the data using an encryption key of the substantially similar data in accordance with an encryption function to produce encrypted data, compressing the encrypted data in accordance with a compression function to produce compressed data, storing the compressed data when the substantially similar data is stored.

Claims

1. A method comprises:

obtaining data to store;

determining whether similar data to the data is stored; and

when the similar data is stored;

encrypting the data using an encryption key of the similar data in accordance with an encryption function to produce encrypted data;

compressing the encrypted data in accordance with a compression function to produce compressed data; and

storing the compressed data; and

when the similar data is not stored;

generating a first encryption key based on the data;

encrypting the data using the first encryption key in accordance with the encryption function to produce first encrypted data;

compressing the first encrypted data in accordance with the compression function to produce first compressed data; and

storing the first compressed data.

2. The method of claim 1, wherein the generating the first encryption key comprises at least one of:

setting the first encryption key to be equal to the data; and

performing a function on the data to produce a representation of the data and setting the first encryption key to be equal to the representation of the data.

3. The method of claim 1 further comprises:

encoding the first encryption key into a plurality of encoded data slices in accordance with an error coding dispersal storage function; and

storing the plurality of encoded data slices in a dispersed storage network (DSN) memory.

4. The method of claim 1 further comprises:

generating a key reference based on the first encryption key, wherein the key reference contains storage location information of the first encryption key.

5. The method of claim 1, wherein the determining whether similar data to the data is stored comprises:

generating a first encryption key based on the data;

comparing a representation of the first encryption key with a representation of the encryption key of the similar data; and

when the representation of first encryption key compares favorably with the representation of the encryption key of the similar data, indicating that the similar data is stored.

6. The method of claim 1, wherein the compressing the encrypted data comprises one or more of:

compressing the encrypted data using one or more of a run-length encoding function, a Lempel-Ziv-Welch compression algorithm, a Huffman compression algorithm, a Golomb compression algorithm, a fractal compression algorithm, a wavelet compression algorithm; and

encrypting the encrypted data utilizing a second encryption algorithm to produce further encrypted data.

7. A method comprises:

obtaining data to store;

determining whether similar data to the data is stored; and

when the similar data is not stored;

generating an encryption key to be similar to the data;

generating a key reference regarding the encryption key;

performing a mathematical function on the data based on the encryption key to produce a data result having a near constant bit pattern;

compressing the data result in accordance with a compression function to produce compressed data;

storing the compressed data and the key reference in a first storage manner; and

storing the encryption key in a second storage manner.

8. The method of claim 7 further comprises:

storing the compressed data and the key reference in local secure memory; and

storing the encryption key as a plurality of encoded data slices in dispersed storage network memory.

9. The method of claim 7, wherein the determining whether similar data to the data is not stored comprises:

comparing a representation of the encryption key with a representation of the encryption key of the similar data; and

when the representation of encryption key compares unfavorably with the representation of the encryption key of the similar data, indicating that the similar data is not stored.

10. A computer comprises:

an interface; and

a processing module operable to;

obtain data to store;

determine whether similar data to the data is stored; and

when the similar data is stored;

encrypt the data using an encryption key of the similar data in accordance with an encryption function to produce encrypted data;

compress the encrypted data in accordance with a compression function to produce compressed data; and

store, via the interface, the compressed data; and

when the substantially similar data is not stored;

generate a first encryption key based on the data;

encrypt the data using the first encryption key in accordance with the encryption function to produce first encrypted data;

compress the first encrypted data in accordance with the compression function to produce first compressed data; and

store, via the interface, the first compressed data.

11. The computer of claim 10, wherein the processing module further functions to generate the first encryption key by at least one of:

setting the first encryption key to be equal to the data; and

performing a function on the data to produce a representation of the data and setting the first encryption key to be equal to the representation of the data.

12. The computer of claim 10, wherein the processing module further functions to:

encode the first encryption key into a plurality of encoded data slices in accordance with an error coding dispersal storage function; and

control storing of the plurality of encoded data slices in a dispersed storage network (DSN) memory.

13. The computer of claim 10, wherein the processing module further functions to:

generate a key reference based on the first encryption key, wherein the key reference contains storage location information of the first encryption key.

14. The computer of claim 10, wherein the processing module further functions to determine whether similar data to the data is stored by:

generating a first encryption key based on the data;

comparing a representation of the first encryption key with a representation of the encryption key of the similar data; and

when the representation of first encryption key compares favorably with the representation of the encryption key of the similar data, indicating that the similar data is stored.

15. The computer of claim 10, wherein the processing module further functions to compress the encrypted data by one or more of:

compressing the encrypted data using one or more of a run-length encoding function, a Lempel-Ziv-Welch compression algorithm, a Huffman compression algorithm, a Golomb compression algorithm, a fractal compression algorithm, a wavelet compression algorithm; and

encrypting the encrypted data utilizing a second encryption algorithm to produce further encrypted data.

16. A computer comprises:

an interface; and

a processing module operable to;

obtain data to store;

determine whether similar data to the data is stored; and

when the similar data is not stored;

generate an encryption key to be similar to the data;

generate a key reference regarding the encryption key;

perform a mathematical function on the data based on the encryption key to produce a data result having a near constant bit pattern;

compress the data result in accordance with a compression function to produce compressed data;

store, via the interface, the compressed data and the key reference in a first storage manner; and

store, via the interface, the encryption key in a second storage manner.

17. The computer of claim 16, wherein the processing module further functions to:

control storing of the compressed data and the key reference in local secure memory; and

control storing of the encryption key as a plurality of encoded data slices in dispersed storage network memory.

18. The computer of claim 16, wherein the processing module further functions to determine whether similar data to the data is not stored by:

comparing a representation of the encryption key with a representation of the encryption key of the similar data; and

when the representation of encryption key compares unfavorably with the representation of the encryption key of the similar data, indicating that the similar data is not stored.