METHOD AND APPARATUS FOR NON-REDUNDANT ENCRYPTED STORAGE

• US 20100083003A1
• Filed: 09/26/2008
• Published: 04/01/2010
• Est. Priority Date: 09/26/2008
• Status: Active Grant

• Current Assignee: Quantum Corporation (Chi Ko Investment Co., Ltd.)
• Original Assignee: Quantum Corporation (Chi Ko Investment Co., Ltd.)
• Inventors: SPACKMAN, Stephen P.
• Granted Patent: US 8,572,409 B2
• Time in Patent Office: Days
• US Class Current: 713/193
• CPC Class Codes: G06F 21/6209 to a single file or object, e.g. in a secure envelope, encrypted and accessed using a key, or with access control rules appended to the object itself
• CPC Class Codes: G06F 2221/2107 File encryption
• CPC Class Codes: H04L 9/0643 Hash functions, e.g. MD5, SHA, HMAC or f9 MAC

Abstract

For secure non-redundant storage of data, to store a data blocklet (sub-block), one takes a hash of each blocklet. The hash value is used as a key to encrypt the blocklet data. The key is then hashed to encrypt it and the hashed key used in the blocklet index to identify the blocklet. The blocklet index entry also conventionally includes the address of that encrypted blocklet. Unless one has a file representation which is a vector of the hash values, one cannot obtain direct information about the original blocklet from the blocklet index or the blocklet storage. To retrieve data, each original blocklet hash is hashed again to generate the index entry. Once the encrypted blocklet is located via the index, the same key (original hash) is used to decrypt the blocklet back to its original form and a file is assembled as a sequence of its blocklets.

Claims

1. A method of storing digital data, comprising:

partitioning the data into portions;

taking a first hash of a first portion;

taking a one-way function value of the first hash;

comparing the one-way function value to an index of previously stored data portions;

if the one-way function value is found in the index, updating the index;

if the one-way function value is not found, encrypting the first portion using the first hash as a key;

storing the encrypted first portion in storage;

updating the index with an entry including the one-way function value and a location of the encrypted first portion in the storage; and

repeating the method for a second portion of the data.

2. The method of claim 1, wherein the first hash or the one way function is keyed.

3. The method of claim 1, wherein the encrypting uses a symmetric cipher.

4. The method of claim 1, wherein the storage includes a hard disk drive or magnetic tape drive or solid state memory.

5. The method of claim 1, wherein the index is stored in random access memory.

6. The method of claim 1, wherein each portion is a sub-block.

7. The method of claim 1, wherein the partitioning partitions the data into portions of differing length.

8. The method of claim 1, wherein the first hash and the one-way function are different functions.

9. The method of claim 1, wherein the storage stores a de-duplicated block pool of portions of the data.

10. The method of claim 1, further comprising accessing a stored portion of the data by:

providing a first hash value;

taking a one-way function value of the first hash value;

comparing the one-way function value to the index;

if the one-way function value is found in the index, retrieving a portion of the data from the storage from the location indicated in the index; and

decrypting the retrieved portion using the first hash as a key.

11. A computer apparatus programmed to carry out the method of claim 1.

12. A computer readable medium carrying computer code to carry out the method of claim 1.

13. Apparatus for storing data, comprising:

a first storage for storing the data;

a partitioner coupled to the first storage to partition the data into portions;

a first hash module coupled to the partitioner to take a first hash of a portion;

a one-way function module coupled to the first hash module to take a one-way function value of the first hash;

a processor coupled to the one-way function module and to a second storage storing an index of previously stored data portions;

an encryptor coupled to the first hash module and to the first storage to encrypt the portion using the first hash as a key;

a third storage coupled to the encryptor to store the encrypted portion;

wherein the processor updates the index with an entry including the one-way function value and a location of the encrypted portion in the third storage.

14. The apparatus of claim 13, wherein the first hash or the one way function is keyed.

15. The apparatus of claim 13, wherein the encryptor uses a symmetric cipher.

16. The apparatus of claim 13, wherein the third storage includes a hard disk drive or magnetic tape drive or solid state memory.

17. The apparatus of claim 13, wherein the second storage for the index is random access memory.

18. The apparatus of claim 13, wherein each portion of the data is a sub-block.

19. The apparatus of claim 13, wherein the partitioner partitions the data into portions of differing length.

20. The apparatus of claim 13, wherein the first hash and the one-way function are different functions.

21. The apparatus of claim 13, wherein the third storage stores a de-duplicated block pool of portions of the data.

22. A data storage system comprising:

a workstation coupled to a network;

a reduced redundancy data storage apparatus coupled to the network and including;

a first storage for storing the data from the workstation;

a partitioner coupled to the first storage to partition the data into portions;

a first hash module coupled to the partitioner to take a first hash of a portion;

a one-way function module coupled to the first hash module to take a one-way function value of the first hash;

a processor coupled to the one-way function module and to a second storage storing an index of previously stored data portions;

an encryptor coupled to the first hash module and to the first storage to encrypt the portion using the first hash as a key; and

a third storage coupled to the encryptor to store the encrypted portion;

wherein the processor updates the index with an entry including the one-way function value and a location of the encrypted portion in the third storage.