SECURING DATA IN A DISPERSED STORAGE NETWORK USING SHARED SECRET SLICES

• US 20100268877A1
• Filed: 04/18/2010
• Published: 10/21/2010
• Est. Priority Date: 04/20/2009
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: LEGGETTE, WESLEY, RESCH, JASON K.
• Granted Patent: US 8,504,847 B2
• Time in Patent Office: Days
• US Class Current: 711/114
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 16/1844 Management specifically adapted to replicated file systems
• CPC Class Codes: G06F 21/1083 Partial license transfers
• CPC Class Codes: G06F 2211/1059 Parity-single bit-RAID5, i.e. RAID 5 implementations
• CPC Class Codes: H04L 2209/34 Encoding or coding, e.g. Huffman coding or error correction
• 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 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/0894 Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions

Abstract

A data element can be encoded into multiple encoded data elements using an encoding algorithm that includes an encoding function and one or more encoder constant. The encoded data elements can be organized into multiple pillars, each having a respective pillar number. Each of the pillars is sent to a different storage unit of a distributed storage network. To recover the original data element, the encoded data elements are retrieved from storage, and the encoder constant is recovered using multiple encoded data elements. Recovering the encoder constant allows the encoding algorithm originally used to encode the data elements to be determined, and used to recover the original data element. The security of the stored data is enhanced, because an encoded data element from a single pillar is insufficient to identify the encoder constant.

Claims

1. A method comprising:

encoding a data element using an encoder algorithm having an encoding function and at least one encoder constant to generate a plurality of encoded data elements and to organize the encoded data elements into a plurality of pillars, each pillar encoded with a respective pillar number;

transmitting the plurality of pillars to a plurality of different storage units of a distributed storage network; and

wherein the encoded data element from a single pillar is insufficient to identify the at least one encoder constant, but the at least one encoder constant can be identified based on encoded data elements from a plurality of pillars.

2. The method of claim 1, the data element having a position within a sequence of data elements, the method further comprising:

encoding the data element using the constant determined, at least in part, by the position of the data element within the sequence of data elements.

3. The method of claim 2, further comprising:

encoding at least two data elements included in the sequence of data elements using different constants.

4. The method of claim 1, wherein the plurality of different storage units is associated with a vault of the distributed storage network, the method further comprising:

encoding the data element using an encoder algorithm selected based, at least in part, on the vault.

5. The method of claim 1, further comprising:

encoding the data element using an encoder algorithm having a number of encoder constants and an encoding function representing a geometric shape, the number of encoder constants based on the geometric shape.

6. The method of claim 1, further comprising:

encoding a first data element to generate a first plurality of data elements and to organize the first plurality of encoded data elements into at least a first-data-first-pillar and a second-data-second-pillar;

encoding a second data element to generate a second plurality of data elements and to organize the second plurality of encoded data elements into at least a second-data-first-pillar and a second-data-second-pillar;

including the first-data-first-pillar and the second data-first-pillar in a first data slice;

including the first-data-second-pillar and the second data-second-pillar in a second data slice; and

transmitting the first data slice and the second data slice to the plurality of different storage units of the distributed storage network.

7. An apparatus comprising:

an encoder to encode a data element using an encoder algorithm having an encoding function and at least one encoder constant to generate a plurality of encoded data elements and to organize the encoded data elements into a plurality of pillars, each pillar encoded with a respective pillar number;

an output to transmit the plurality of pillars to a plurality of different storage units of a distributed storage network; and

wherein the encoded data element from a single pillar is insufficient to identify the at least one encoder constant, but the at least one encoder constant can be identified based on encoded data elements from a plurality of pillars.

8. The apparatus of claim 7, the data element having a position within a sequence of data elements, the method further comprising:

the encoder to encode the data element using the constant determined, at least in part, by the position of the data element within the sequence of data elements.

9. The apparatus of claim 8, further comprising:

the encoder to encode at least two data elements included in the sequence of data elements using different constants.

10. The apparatus of claim 7, wherein the plurality of different storage units is associated with a vault of the distributed storage network, the method further comprising:

the encoder to encode the data element using an encoder algorithm selected based, at least in part, on the vault.

11. The apparatus of claim 7, further comprising:

the encoder to encode the data element using an encoder algorithm having a number of encoder constants and an encoding function representing a geometric shape, the number of encoder constants based on the geometric shape.

12. The apparatus of claim 7, further comprising:

the encoder to encode a first data element to generate a first plurality of data elements and to organize the first plurality of encoded data elements into at least a first-data-first-pillar and a second-data-second-pillar;

the encoder to encode a second data element to generate a second plurality of data elements and to organize the second plurality of encoded data elements into at least a second-data-first-pillar and a second-data-second-pillar;

the encoder to include the first-data-first-pillar and the second data-first-pillar in a first data slice;

the encoder to include the first-data-second-pillar and the second data-second-pillar in a second data slice; and

the output to transmit the first data slice and the second data slice to the plurality of different storage units of the distributed storage network.

13. An apparatus comprising:

an input to receive a plurality of encoded data elements from a plurality of different storage units included in a vault of a distributed storage network, each of the encoded data elements associated with a pillar having a respective pillar number, and encoded using an encoder algorithm including an encoding function and at least one encoder constant;

a decoder to recover the at least one encoder constant and determine the encoder algorithm using the plurality of encoded data elements, the respective pillar number, and the encoding function, wherein a single one of the plurality of encoded data elements is insufficient to recover the at least one encoder constant;

the decoder further to decode at least one of the plurality of encoded data elements to generate a decoded data element using the encoding algorithm.

14. The apparatus of claim 13, wherein the plurality of encoded data elements includes a greater number of encoded data elements than required to recover the encoder constant, the apparatus further comprising:

the decoder further to recover the at least one encoder constant and determine the encoder algorithm using fewer than all of the plurality of encoded data elements.

15. The apparatus of claim 14, further comprising:

the decoder to verify an integrity of the decoded data element by solving for the at least one encoder constant, wherein solving includes decoding more than one of the plurality of encoded data segments using the encoding algorithm.

16. The apparatus of claim 14, further comprising:

the decoder to verify an integrity of the plurality of encoded data elements by recovering the at least one encoder constant using at least one more encoded data element of the plurality of encoded data elements than minimally required.

17. A method comprising:

receiving a plurality of encoded data elements from a plurality of different storage units included in a vault of a distributed storage network, each of the encoded data elements associated with a pillar having a respective pillar number, and encoded using an encoder algorithm including an encoding function and at least one encoder constant;

recovering the at least one encoder constant and determining the encoder algorithm using the plurality of encoded data elements, the respective pillar number, and the encoding function, wherein a single one of the plurality of encoded data elements is insufficient to recover the at least one encoder constant;

decoding at least one of the plurality of encoded data elements to generate a decoded data element using the encoding algorithm.

18. The method of claim 17, wherein the plurality of encoded data elements includes a greater number of encoded data elements than required to recover the encoder constant, the method further comprising:

recovering the at least one encoder constant and determining the encoder algorithm using fewer than all of the plurality of encoded data elements.

19. The method of claim 17, further comprising:

verifying an integrity of the decoded data element by solving for the at least one encoder constant, the solving including decoding more than one of the plurality of encoded data segments using the encoding algorithm.

20. The method of claim 17, further comprising:

verifying an integrity of the plurality of encoded data elements by recovering the at least one encoder constant using at least one more encoded data element of the plurality of encoded data elements than minimally required.