Method and apparatus for non-redundant encrypted storage

• US 8,572,409 B2
• Filed: 09/26/2008
• Issued: 10/29/2013
• 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.
• Primary Examiner(s): SHAW, BRIAN F
• Application Number:
  US12/239,518
• Publication Number:
  US 20100083003A1
• Time in Patent Office: 1,859 Days
• Field of Search: 713/193, 711/154, 711/135
• 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.

Claims

1. A method, comprising:

computing a first hash by applying a first hash function to a sub-block produced by a data de-duplication system, computing a second different hash by applying a second, different hash function to the first hash; and

upon determining that the second hash is not located in an index associated with the data de-duplication system, where the index stores second hash values computed by applying the second, different hash function to sub-blocks processed by the data de-duplication system;

producing an encrypted sub-block by applying an encryption function to the sub-block, where the encryption function uses the first hash as an encryption key;

storing the encrypted sub-block in a data store maintained by the data de-duplication system;

storing, in the index, the second hash value and a location in the data store where the encrypted sub-block is stored;

accessing a sub-block stored in the data store by;

computing a candidate hash value by applying the second hash function to a received hash value; and

upon determining that the candidate hash value appears in the index;

retrieving an encrypted sub-block associated with the candidate hash value; and

producing a decrypted sub-block by applying a decryption function to the encrypted sub-block, where the decryption function employs a value, other than the received hash value, as a decryption key.

2. The method of claim 1, where the data store is a hard disk drive or magnetic tape drive or solid state memory.

3. The method of claim 1, where the index is stored in random access memory.