Secure rebuilding of an encoded data slice in a dispersed storage network

• US 8,914,669 B2
• Filed: 11/07/2011
• Issued: 12/16/2014
• Est. Priority Date: 04/26/2010
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Dhuse, Greg, Leggette, Wesley, Baptist, Andrew, Resch, Jason K.
• Primary Examiner(s): LOHN, JOSHUA A
• Application Number:
  US13/291,009
• Publication Number:
  US 20120054500A1
• Time in Patent Office: 1,135 Days
• Field of Search: 714/6.2, 714/6.22, 714/6.24
• US Class Current: 714/6.24
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: G06F 2211/104 Metadata, i.e. metadata associated with RAID systems with parity
• CPC Class Codes: G06F 2221/2107 File encryption
• CPC Class Codes: H04L 2209/30 Compression, e.g. Merkle-Damgard construction
• CPC Class Codes: H04L 2209/34 Encoding or coding, e.g. Huffman coding or error correction
• CPC Class Codes: H04L 63/0478 applying multiple layers of encryption, e.g. nested tunnels or encrypting the content with a first key and then with at least a second key cryptographic mechanisms or cryptographic arrangements using a plurality of keys or algorithms H04L9/14
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• CPC Class Codes: H04L 69/40 for recovering from a failure of a protocol instance or entity, e.g. service redundancy protocols, protocol state redundancy or protocol service redirection management of faults, events, alarms or notifications in data switching networks H04L41/06
• CPC Class Codes: H04L 9/0822 using key encryption key
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/0897 involving additional devices, e.g. trusted platform module [TPM], smartcard or USB

Abstract

A method begins by a processing module identifying an encoded data slice to be rebuilt, selecting a decode threshold number of dispersed storage (DS) units of a storage set of DS units, generating a decode threshold number of key pairs, wherein a key pair of the decode threshold number of key pairs corresponds to a DS unit of the decode threshold number of DS units, and sending partial rebuilding requests to the decode threshold number of DS units, wherein a partial rebuilding request of the partial rebuilding requests includes the key pair. The method continues with the processing module receiving encrypted partial encoded data slices, wherein an encrypted partial encoded data slice received from the corresponding DS unit includes a multiple encryption, using the key pair, of a partial encoded data slice and decoding the encrypted partial encoded data slices to rebuild the encoded data slice.

Claims

1. A method comprises:

identifying an encoded data slice to be rebuilt;

selecting a decode threshold number of dispersed storage (DS) units of a storage set of DS units associated with the encoded data slice to be rebuilt;

generating a decode threshold number of key pairs, wherein a key pair of the decode threshold number of key pairs corresponds to a DS unit of the decode threshold number of DS units;

sending partial rebuilding requests to the decode threshold number of DS units, wherein a partial rebuilding request of the partial rebuilding requests includes the key pair and identity of the corresponding DS unit;

receiving encrypted partial encoded data slices in response to the partial rebuilding requests, wherein an encrypted partial encoded data slice received from the corresponding DS unit includes a multiple encryption, using the key pair, of a partial encoded data slice; and

decoding the encrypted partial encoded data slices to rebuild the encoded data slice.

2. The method of claim 1, wherein the generating the decode threshold number of key pairs comprises:

generating a decode threshold number of unique keys based on at least one of a random number generator, a random key generator, a predetermined key, a key seed, a key list, a private key, and public key, a received key, and a previous key; and

uniquely pairing keys of the decode threshold number of unique keys to produce the decode threshold number of key pairs.

3. The method of claim 1, wherein the decoding the encrypted partial encoded data slices comprises one of:

performing a logical exclusive OR function between each encrypted partial encoded data slice of the encrypted partial encoded data slices to rebuild the encoded data slice; and

performing the logical exclusive OR function between each encrypted partial encoded data slice and a corresponding key pair of the decode threshold number of key pairs to produce a decode threshold number of interim slices and performing the logical exclusive OR function between each interim slice of the decode threshold number of interim slices to reproduce the encoded data slice to be rebuilt.

4. The method of claim 1, wherein the partial encoded data slice comprises:

a result of a partial encoded data slice generation function including;

obtaining an encoding matrix utilized to generate the encoded data slice to be rebuilt;

reducing the encoding matrix to produce a square matrix that exclusively includes rows associated with the decode threshold number of DS units;

inverting the square matrix to produce an inverted matrix;

matrix multiplying the inverted matrix by an encoded data slice associated with the DS unit to produce a vector; and

matrix multiplying the vector by a row of the encoding matrix corresponding to the encoded data slice to be rebuilt to produce the partial encoded data slice.

5. A method comprises:

receiving a partial rebuilding request, wherein the request includes a key pair;

retrieving an encoded data slice associated with the partial encoded data slice request;

generating a partial encoded data slice based on the partial rebuilding request and the encoded data slice associated with the request;

multiple encrypting the partial encoded data slice using the key pair to produce an encrypted partial encoded data slice; and

outputting the encrypted partial encoded data slice.

6. The method of claim 5, wherein the generating the partial encoded data slice comprises one or more of:

obtaining an encoding matrix utilized to generate the encoded data slice;

reducing the encoding matrix to produce a square matrix that exclusively includes rows identified in the partial rebuilding request;

inverting the square matrix to produce an inverted matrix;

matrix multiplying the inverted matrix by the encoded data slice to produce a vector; and

matrix multiplying the vector by a row of the encoding matrix corresponding to an encoded data slice to be rebuilt to produce the partial encoded data slice.

7. The method of claim 5, wherein the multiple encrypting the partial encoded data slice comprises:

encrypting the partial encoded data slice utilizing a first key of the key pair to produce an interim slice; and

encrypting the interim slice utilizing a second key of the key pair to produce the encrypted partial encoded data slice.

8. The method of claim 7, wherein the encrypting the partial encoded data slice utilizing the first key comprises at least one of:

performing a logical exclusive OR function between the partial encoded data slice and the first key to produce the interim slice; and

encrypting the partial encoded data slice utilizing the first key to produce the interim slice.

9. The method of claim 7, wherein the encrypting the interim slice utilizing the second key comprises at least one of:

performing a logical exclusive OR function between the interim slice and the second key to produce the encrypted partial encoded data slice; and

encrypting the interim slice utilizing the second key to produce the encrypted partial encoded data slice.

10. A rebuilding module comprises:

a first module for identifying an encoded data slice to be rebuilt;

a second module for selecting a decode threshold number of dispersed storage (DS) units of a storage set of DS units associated with the encoded data slice to be rebuilt;

a third module for generating a decode threshold number of key pairs, wherein a key pair of the decode threshold number of key pairs corresponds to a DS unit of the decode threshold number of DS units;

a fourth module for sending partial rebuilding requests to the decode threshold number of DS units, wherein a partial rebuilding request of the partial rebuilding requests includes the key pair and identity of the corresponding DS unit;

a fifth module for receiving encrypted partial encoded data slices in response to the partial rebuilding requests, wherein an encrypted partial encoded data slice received from the corresponding DS unit includes a multiple encryption, using the key pair, of a partial encoded data slice; and

a sixth module for decoding the encrypted partial encoded data slices to rebuild the encoded data slice.

11. The rebuilding module of claim 10, wherein the third module is further operable to generate the decode threshold number of key pairs by:

generating a decode threshold number of unique keys based on at least one of a random number generator, a random key generator, a predetermined key, a key seed, a key list, a private key, and public key, a received key, and a previous key; and

uniquely pairing keys of the decode threshold number of unique keys to produce the decode threshold number of key pairs.

12. The rebuilding module of claim 10, wherein the sixth module is further operable to decode the encrypted partial encoded data slices by one of:

performing a logical exclusive OR function between each encrypted partial encoded data slice of the encrypted partial encoded data slices to rebuild the encoded data slice; and

performing the logical exclusive OR function between each encrypted partial encoded data slice and a corresponding key pair of the decode threshold number of key pairs to produce a decode threshold number of interim slices and performing the logical exclusive OR function between each interim slice of the decode threshold number of interim slices to reproduce the encoded data slice to be rebuilt.

13. The rebuilding module of claim 10, wherein the partial encoded data slice comprises:

a result of a partial encoded data slice generation function including;

obtaining an encoding matrix utilized to generate the encoded data slice to be rebuilt;

reducing the encoding matrix to produce a square matrix that exclusively includes rows associated with the decode threshold number of DS units;

inverting the square matrix to produce an inverted matrix;

matrix multiplying the inverted matrix by an encoded data slice associated with the DS unit to produce a vector; and

matrix multiplying the vector by a row of the encoding matrix corresponding to the encoded data slice to be rebuilt to produce the partial encoded data slice.

14. A rebuilding module comprises:

a first module for receiving a partial rebuilding request, wherein the request includes a key pair;

a second module for retrieving an encoded data slice associated with the partial encoded data slice request;

a third module for generating a partial encoded data slice based on the partial rebuilding request and the encoded data slice associated with the request;

a fourth module for multiple encrypting the partial encoded data slice using the key pair to produce an encrypted partial encoded data slice; and

a fifth module for outputting the encrypted partial encoded data slice.

15. The rebuilding module of claim 14, wherein the third module is further operable to generate the partial encoded data slice by one or more of:

obtaining an encoding matrix utilized to generate the encoded data slice;

reducing the encoding matrix to produce a square matrix that exclusively includes rows identified in the partial rebuilding request;

inverting the square matrix to produce an inverted matrix;

matrix multiplying the inverted matrix by the encoded data slice to produce a vector; and

matrix multiplying the vector by a row of the encoding matrix corresponding to an encoded data slice to be rebuilt to produce the partial encoded data slice.

16. The rebuilding module of claim 14, wherein the fourth module is further operable to multiple encrypt the partial encoded data slice by:

encrypting the partial encoded data slice utilizing a first key of the key pair to produce an interim slice; and

encrypting the interim slice utilizing a second key of the key pair to produce the encrypted partial encoded data slice.

17. The rebuilding module of claim 16, wherein the fourth module is further operable to encrypt the partial encoded data slice utilizing the first key by at least one of:

performing a logical exclusive OR function between the partial encoded data slice and the first key to produce the interim slice; and

encrypting the partial encoded data slice utilizing the first key to produce the interim slice.

18. The rebuilding module of claim 16, wherein the fourth module is further operable to encrypt the interim slice utilizing the second key by at least one of:

performing a logical exclusive OR function between the interim slice and the second key to produce the encrypted partial encoded data slice; and

encrypting the interim slice utilizing the second key to produce the encrypted partial encoded data slice.