Dispersed storage network data slice integrity verification

• US 8,918,897 B2
• Filed: 08/25/2010
• Issued: 12/23/2014
• Est. Priority Date: 11/24/2009
• Status: Expired due to Fees

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Resch, Jason K.
• Primary Examiner(s): Zand, Kambiz
• Assistant Examiner(s): NGUYEN, TRONG H
• Application Number:
  US12/862,887
• Publication Number:
  US 20110126295A1
• Time in Patent Office: 1,581 Days
• Field of Search: None
• US Class Current: 726/27
• CPC Class Codes: G06F 11/1402 Saving, restoring, recovering or retrying
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
• CPC Class Codes: G06F 21/64 Protecting data integrity, e.g. using checksums, certificates or signatures
• CPC Class Codes: G06F 21/80 in storage media based on magnetic or optical technology, e.g. disks with sectors preventing unauthorised reproduction or copying of disc-type recordable media G11B20/00
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes

Abstract

A method begins with a processing module issuing a retrieval request, receiving secret shares of a set of secret shares to produce received secret shares, and receiving encoded data slices of a set of encoded data slices. The method continues with the processing module decoding the received secret shares to recapture a message authentication key when a threshold number of the secret shares is received. The method continues with the processing module identifying a received encoded data slice of the received encoded data slices having an authentication code associated therewith when a threshold number of the encoded data slices is received. The method continues with the processing module verifying the authentication code based on the message authentication key and the received encoded data slice. The method continues with the processing module decoding the received encoded data slices to recapture a data segment when the authentication code is verified.

Claims

1. A method for execution by one or more processing devices of a computing device, the method comprises:

issuing, by the one or more processing devices of the computing device, a retrieval request;

in response to the retrieval request, receiving at least a threshold number of double appended encoded data slices to storage units, wherein a double appended encoded data slice of the at least the threshold number of double appended encoded data slices includes an encoded data slice of a set of encoded data slices, a secret share of a set of secret shares, and an authentication code of a set of authentication codes;

separating the at least the threshold number of double appended encoded data slices into at least a threshold number of secret shares and at least a threshold number of appended encoded data slices;

decoding at least one of the at least the threshold number of secret shares in accordance with a secret share function to recapture a message authentication key;

for each of the threshold number of appended encoded data slices, verifying the authentication code based on the message authentication key and the encoded data slice; and

when the authentication codes are verified for the at least the threshold number of appended encoded data slices, decoding the encoded data slices of the at least the threshold number of appended encoded data slices in accordance with an error coding dispersal storage function to recapture a data segment.

2. The method of claim 1, wherein the secret share function comprises:

a polynomial that includes a first constant, a first variable, and one or more other constants, wherein the message authentication key is assigned to the first constant, an identifier of an encoded data slice of the set of set of encoded data slices is assigned to the first variable, and one or more other values are assigned to the one or more other constants.

3. The method of claim 2 further comprises:

the polynomial including the equation y=mx+b, wherein ‘

m’

corresponds to the first constant, ‘

x’

corresponds to the first variable, and ‘

b’

corresponds to the one or more other constants;

wherein the decoding the at least one of the at least the threshold number of secret shares includes;

setting ‘

y’

equal to the at least one of the at least the threshold number of secret shares;

obtaining the first variable from a corresponding encoded data slice of a set of encoded data slices;

obtaining a value for the constant ‘

b’

; and

solving for the first constant ‘

m’

.

4. The method of claim 1, wherein the secret share function comprises:

decoding the at least the threshold number of secret shares in accordance with an error coding dispersal storage function to recapture the message authentication key.

5. The method of claim 1, wherein the verifying the authentication code further comprises:

performing a keyed-hash message authentication code generation or a cryptographic hash function algorithm on the encoded data slice utilizing the message authentication key to produce a verification authentication code;

comparing the verification authentication code with the authentication code; and

when the comparing of the verification authentication code with the authentication code is favorable, indicating verification of the authentication code.

6. A method for execution by one or more processing devices of a computing device, the method comprises:

encoding, by the one or more processing devices, a data segment in accordance with an error coding dispersal storage function to produce a set of encoded data slices;

generating a set of authentication codes based on a message authentication key and the set of encoded data slices;

appending corresponding authentication codes of the set of authentication codes to corresponding encoded data slices of the set of encoded data slices to produce a set of appended encoded data slices, wherein a first authentication code is appended to a first encoded data slice;

encoding the message authentication key into a set of secret shares based on the set of encoded data slices;

appending corresponding secret shares of the set of secret shares to corresponding appended encoded data slices to produce a set of double appended encoded data slices, wherein a first secret share is appended to a first appended encoded data slice; and

outputting the double appended encoded data slices to storage units.

7. The method of claim 6, wherein the message authentication key comprises at least one of:

an output of a random number generator;

a result of a table lookup; and

a result of a retrieval.

8. The method of claim 6, wherein generating the authentication code further comprises at least one of:

performing a keyed-hash message authentication code generation function on the encoded data slice utilizing the message authentication key; and

performing a cryptographic hash function algorithm on the encoded data slice utilizing the message authentication key.

9. The method of claim 6, wherein the encoding the message authentication key into the set of secret shares further comprises:

assigning the message authentication key to a constant of a polynomial;

assigning a unique identifier of the corresponding one of the set of encoded data slices to a variable of the polynomial to produce a first assigned variable;

solving the polynomial to produce the secret share based on the constant and the first assigned variable;

assigning a second unique identifier of a second one of the set of encoded data slices to the variable of the polynomial to produce a second assigned variable; and

solving the polynomial to produce a second secret share of the set of secret shares based on the constant and the second assigned variable.

10. The method of claim 6, wherein the encoding the message authentication key into the set of secret shares further comprises:

encoding the message authentication key in accordance with an error coding dispersal storage function to produce the set of secret shares.

11. A computer comprises:

an interface; and

a processing module operable to;

issue, via the interface, a retrieval request;

in response to the retrieval request, receive, via the interface, at least a threshold number of double appended encoded data slices to storage units, wherein a double appended encoded data slice of the at least the threshold number of double appended encoded data slices includes an encoded data slice of a set of encoded data slices, a secret share of a set of secret shares, and an authentication code of a set of authentication codes;

separate the at least the threshold number of double appended encoded data slices into at least a threshold number of secret shares and at least a threshold number of appended encoded data slices;

decode at least one of the at least the threshold number of secret shares in accordance with a secret share function to recapture a message authentication key when a threshold number of the secret shares is received;

for each of the threshold number of appended encoded data slices, verify the authentication code based on the message authentication key and the encoded data slice; and

when the authentication codes are verified for the at least the threshold number of appended encoded data slices, decode the encoded data slices of the at least the threshold number of appended encoded data slices in accordance with an error coding dispersal storage function to recapture a data segment when the authentication code is verified.

12. The computer of claim 11, wherein the secret share function comprises:

a polynomial that includes a first constant, a first variable, and one or more other constants, wherein the message authentication key is assigned to the first constant, an identifier of an encoded data slice of the set of set of encoded data slices is assigned to the first variable, and one or more other values are assigned to the one or more other constants.

13. The computer of claim 12, wherein the processing module further functions to:

the polynomial including the equation y=mx+b, wherein ‘

m’

corresponds to the first constant, ‘

x’

corresponds to the first variable, and ‘

b’

corresponds to the one or more other constants;

wherein the processing module decodes the at least one of the at least the threshold number of secret shares by;

setting ‘

y’

equal to the at least one of the at least the threshold number of secret shares;

obtaining the first variable from a corresponding encoded data slice of a set of encoded data slices;

obtaining a value for the constant ‘

b’

; and

solving for the first constant ‘

m’

.

14. The computer of claim 11, wherein the processing module further functions to decode the at least the threshold number of secret shares in accordance with a secret share function by:

decoding the at least the threshold number of secret shares in accordance with an error coding dispersal storage function to recapture the message authentication key.

15. The computer of claim 11, wherein the processing module further functions to verify the authentication code by:

performing a keyed-hash message authentication code generation or a cryptographic hash function algorithm on the encoded data slice utilizing the message authentication key to produce a verification authentication code;

comparing the verification authentication code with the authentication code; and

when the comparing of the verification authentication code with the authentication code is favorable, indicating verification of the authentication code.

16. A computer comprises:

an interface; and

a processing module operable to;

encode a data segment in accordance with an error coding dispersal storage function to produce a set of encoded data slices;

generate a set of authentication codes based on a message authentication key and the set of encoded data slices;

append corresponding the authentication codes of the set of authentication codes to corresponding encoded data slices of the set of encoded data slices to produce a set of appended encoded data slices, wherein a first authentication code is appended to a first encoded data slice;

encode the message authentication key into a set of secret shares based on the set of encoded data slices;

append corresponding secret shares of the set of secret shares to corresponding appended encoded data slices to produce a set of double appended encoded data slices, wherein a first secret share is appended to a first appended encoded data slice; and

output, via the interface, the double appended encoded data slices to storage units.

17. The computer of claim 16, wherein the message authentication key comprises at least one of:

an output of a random number generator;

a result of a table lookup; and

a result of a retrieval.

18. The computer of claim 16, wherein the processing module further functions to generate the authentication code by at least one of:

performing a keyed-hash message authentication code generation function on the encoded data slice utilizing the message authentication key; and

performing a cryptographic hash function algorithm on the encoded data slice utilizing the message authentication key.

19. The computer of claim 16, wherein the processing module further functions to encode the message authentication key into the set of secret shares by:

assigning the message authentication key to a constant of a polynomial;

assigning a unique identifier of the corresponding one of the set of encoded data slices to a variable of the polynomial to produce a first assigned variable;

solving the polynomial to produce the secret share based on the constant and the first assigned variable;

assigning a second unique identifier of a second one of the set of encoded data slices to the variable of the polynomial to produce a second assigned variable; and

solving the polynomial to produce a second secret share of the set of secret shares based on the constant and the second assigned variable.

20. The computer of claim 16, wherein the processing module further functions to encode the message authentication key into the set of secret shares by:

encoding the message authentication key in accordance with an error coding dispersal storage function to produce the set of secret shares.