Data storage system and method by shredding and deshredding

• US 10,083,083 B2
• Filed: 07/01/2014
• Issued: 09/25/2018
• Est. Priority Date: 08/31/2001
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: de la Torre, Douglas R., Young, David W.
• Primary Examiner(s): Phillips, III, Albert M
• Application Number:
  US14/321,629
• Publication Number:
  US 20140317421A1
• Time in Patent Office: 1,547 Days
• 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/1402 Saving, restoring, recovering or retrying
• CPC Class Codes: G06F 11/141 for bus or memory accesses
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: G06F 2201/80 Database-specific techniques
• CPC Class Codes: H03M 13/29 combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H04L 2209/30 Compression, e.g. Merkle-Damgard construction
• CPC Class Codes: H04L 9/3247 involving digital signatures
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A system and method for data storage by shredding and deshredding of the data allows for various combinations of processing of the data to provide various resultant storage of the data. Data storage and retrieval functions include various combinations of data redundancy generation, data compression and decompression, data encryption and decryption, and data integrity by signature generation and verification. Data shredding is performed by shredders and data deshredding is performed by deshredders that have some implementations that allocate processing internally in the shredder and deshredder either in parallel to multiple processors or sequentially to a single processor. Other implementations use multiple processing through multi-level shredders and deshredders. Redundancy generation includes implementations using non-systematic encoding, systematic encoding, or a hybrid combination. Shredder based tag generators and deshredder based tag readers are used in some implementations to allow the deshredders to adapt to various versions of the shredders.

Claims

1. A shredder having at least one processor and a memory that stores instructions that, when executed by the at least one processor, causes the at least one processor to perform a shredding process that comprises:

performing a plurality of data operations on input data to produce a plurality of shreds, the plurality of data operations including an encryption operation, a signature operation, and a redundancy operation, wherein, as a result of performing the redundancy operation, the input data is recoverable by a subset of at least two shreds of the plurality of shreds;

partitioning the plurality of shreds into a set of partitioned shreds for storage in a set of storage servers, wherein a first storage server of the set of storage servers is located at a different physical location than a second storage server of the set of storage servers; and

outputting the set of partitioned shreds to the set of storage servers for storage therein, wherein no one storage server of the set of storage servers stores enough shreds of the plurality of shreds to fully recover the input data, including outputting a first shred of the set of partitioned shreds to the first storage server and outputting a second shred of the set of partitioned shreds to the second storage server, wherein the plurality of data operations are separate and distinct from any forward error correction operation performed on the plurality of shreds in conjunction with outputting the set of partitioned shreds to the set of storage servers.

2. The shredder of claim 1 wherein the signature operation is performed after the encryption operation, and the redundancy operation is performed after the signature operation.

3. The shredder of claim 1 wherein the signature operation is performed after the redundancy operation on at least some of the plurality of shreds, wherein the signature operation is an integrity check operation.

4. The shredder of claim 1 further comprises:

encrypting the input data in accordance with the encryption operation to produce encrypted data;

performing a first portion of the signature operation on the encrypted data to produce a first signed encrypted data;

performing the redundancy operation on the first signed encrypted data to produce the plurality of shreds; and

performing a second portion of the signature operation on the plurality of shreds, wherein the plurality of shreds includes integrity check data.

5. The shredder of claim 1 wherein the encryption operation uses a random key.

6. The shredder of claim 1 wherein the encryption operation uses a key derived from the input data.

7. A shredder having at least one processor and a memory that stores instructions that, when executed by the at least one processor, causes the at least one processor to perform a shredding process that comprises:

performing an encryption operation and a signature operation on input data to produce second data;

performing a redundancy operation on the second data to produce a plurality of shreds; and

outputting, via a communication network, the plurality of shreds to a set of storage servers for storage therein, wherein no one storage server of the set of storage servers stores enough shreds of the plurality of shreds to fully recover the input data, wherein a first storage server of the set of storage servers is located at a different physical location than a second storage server of the set of storage servers, including outputting a first shred of the plurality of shreds to the first storage server and outputting a second shred of the plurality of shreds to the second storage server, wherein the redundancy operation is separate and distinct from any forward error correction operation performed on the plurality of shreds in conjunction with outputting the plurality of shreds to the set of storage servers.

8. The shredder of claim 7 wherein the signature operation is performed after the encryption operation.

9. The shredder of claim 7 further comprises:

performing a second signature operation on the plurality of shreds such that the plurality of shreds includes integrity check data.

10. The shredder of claim 7 wherein the signature operation is performed after the encryption operation,

the encryption operation produces encrypted data, and

the signature operation comprises performing a HMAC function on the encrypted data.

11. The shredder of claim 7 wherein the encryption operation uses a random key.

12. The shredder of claim 7 wherein the encryption operation uses a key derived from the input data.

13. A computer-implemented method comprising:

performing, by at least one computing device, a plurality of data operations on input data to produce a plurality of shreds, the plurality of data operations including an encryption operation, a signature operation, and a redundancy operation wherein, as a result of performing the redundancy operation, the input data is recoverable by a subset of at least two shreds of the plurality of shreds;

partitioning, by the at least one computing device, the plurality of shreds into a set of partitioned shreds for storage in a set of storage servers; and

outputting, by the at least one computing device, the set of partitioned shreds to the set of storage servers for storage therein, wherein no one storage server of the set of storage servers stores enough shreds of the plurality of shreds to fully recover the input data, wherein a first storage server of the set of storage servers is located at a different physical location than a second storage server of the set of storage servers, including outputting a first shred of the set of partitioned shreds to the first storage server and outputting a second shred of the set of partitioned shreds to the second storage server, wherein the plurality of data operations are separate and distinct from any forward error correction operation performed on the plurality of shreds in conjunction with outputting the set of partitioned shreds to the set of storage servers.

14. The method of claim 13 wherein the signature operation is performed after the encryption operation, and the redundancy operation is performed after the signature operation.

15. The method of claim 13 wherein the signature operation is performed after the redundancy operation on at least some of the plurality of shreds, wherein the signature operation is an integrity check operation.

16. The method of claim 13 further comprises:

encrypting the input data in accordance with the encryption operation to produce encrypted data;

performing the signature operation on the encrypted data to produce a first signed encrypted data;

performing the redundancy operation on the first signed encrypted data to produce the plurality of shreds; and

performing a second signature operation on the plurality of shreds, wherein the plurality of shreds includes integrity check data.

17. The method of claim 13 wherein the encryption operation uses a random key.

18. The method of claim 13 wherein the encryption operation uses a key derived from the input data.

19. A computer-implemented method comprising:

performing, by at least one computing device, an encryption operation and a signature operation on input data to produce second data;

performing, by the at least one computing device, a redundancy operation on the second data to produce a plurality of shreds; and

outputting, by the at least one computing device, the plurality of shreds to a set of storage servers for storage therein, wherein no one storage server of the set of storage servers stores enough shreds of the plurality of shreds to fully recover the input data, wherein a first storage server of the set of storage servers is located at a different physical location than a second storage server of the set of storage servers, including outputting a first shred of the plurality of shreds to the first storage server and outputting a second shred of the plurality of shreds to the second storage server, wherein the redundancy operation is separate and distinct from any forward error correction operation performed on the plurality of shreds in conjunction with outputting the plurality of shreds to the set of storage servers.

20. The method of claim 19 wherein the signature operation is performed after the encryption operation.

21. The method of claim 19 further comprises:

performing a second signature operation on the plurality of shreds such that the plurality of shreds includes integrity check data.

22. The method of claim 19 wherein the signature operation is performed after the encryption operation,

the encryption operation produces encrypted data, and

the signature operation comprises performing a HMAC function on the encrypted data.

23. The method of claim 19 wherein the encryption operation uses a random key.

24. The method of claim 19 wherein the encryption operation uses a key derived from the input data.