DISPERSED STORAGE NETWORK DATA SLICE INTEGRITY VERIFICATION

• US 20110126295A1
• Filed: 08/25/2010
• Published: 05/26/2011
• Est. Priority Date: 11/24/2009
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: RESCH, JASON K.
• Granted Patent: US 8,918,897 B2
• Time in Patent Office: Days
• 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 comprises:

issuing a retrieval request;

in response to the retrieval request, receiving secret shares of a set of secret shares to produce received secret shares;

when a threshold number of the secret shares is received, decoding the received secret shares in accordance with a secret share function to recapture a message authentication key;

in response to the retrieval request, receiving encoded data slices of a set of encoded data slices to produce received encoded data slices;

when a threshold number of the encoded data slices is received, identifying a received encoded data slice of the received encoded data slices having an authentication code associated therewith;

verifying the authentication code based on the message authentication key and the received encoded data slice; and

when the authentication code is verified, decoding the received 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:

assigning a threshold number of unique identifiers of the threshold number of received secret shares to a first variable of a polynomial to produce an assigned value set of the first variable;

assigning the threshold number of received secret shares to a second variable of the polynomial to produce an assigned value set of the second variable; and

solving for a constant of the polynomial to produce the message authentication key based on the assigned value set of the first variable and the assigned value set of the second variable.

3. The method of claim 2 further comprises:

assigning a threshold number of unique identifiers of a second threshold number of received secret shares to the first variable of the polynomial to produce a second assigned value set of the first variable;

assigning the second threshold number of received secret shares to the second variable of the polynomial to produce a second assigned value set of the second variable;

solving for the constant of the polynomial to produce a second message authentication key based on the second assigned value set of the first variable and the second assigned value set of the second variable;

comparing the second message authentication key with the message authentication key; and

when the comparing of the second message authentication key with the message authentication key is favorable, indicating verification of the message authentication key.

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

decoding the received 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 received 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. The method of claim 1 further comprises:

when the threshold number of the encoded data slices is received, identifying a second received encoded data slice of the received encoded data slices having a second authentication code associated therewith;

verifying the second authentication code based on the message authentication key and the second received encoded data slice; and

when the first and second authentication code are verified, decoding the received encoded data slices in accordance with an error coding dispersal storage function to recapture a data segment.

7. A method comprises:

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

generating an authentication code based on a message authentication key and an encoded data slice of the set of encoded data slices;

outputting the authentication code and the encoded data slice to a dispersed storage (DS) unit of a set of DS units;

encoding the message authentication key into a set of secret shares based on identity of at least some of the set of DS units; and

outputting a secret share of the set of secret shares to a corresponding one of the at least some of the set of DS units.

8. The method of claim 7 further comprises:

generating a second authentication code based on the message authentication key and a second encoded data slice of the set of encoded data slices; and

outputting the second authentication code and the second encoded data slice to a second DS unit of a set of DS units.

9. The method of claim 7, 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.

10. The method of claim 7, 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.

11. The method of claim 7, 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 at least some of the set of DS units 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 at least some of the set of DS units 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.

12. The method of claim 7, 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.

13. A computer comprises:

an interface; and

a processing module operable to;

issue, via the interface, a retrieval request;

receive, via the interface, secret shares of a set of secret shares to produce received secret shares in response to the retrieval request;

decode the received 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;

receive, via the interface, encoded data slices of a set of encoded data slices to produce received encoded data slices in response to the retrieval request;

identify 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;

verify the authentication code based on the message authentication key and the received encoded data slice; and

decode the received encoded data slices in accordance with an error coding dispersal storage function to recapture a data segment when the authentication code is verified.

14. The computer of claim 13, wherein the processing module further functions to decode the received secret shares in accordance with a secret share function by:

assigning a threshold number of unique identifiers of the threshold number of received secret shares to a first variable of a polynomial to produce an assigned value set of the first variable;

assigning the threshold number of received secret shares to a second variable of the polynomial to produce an assigned value set of the second variable; and

solving for a constant of the polynomial to produce the message authentication key based on the assigned value set of the first variable and the assigned value set of the second variable.

15. The computer of claim 14, wherein the processing module further functions to:

assign a threshold number of unique identifiers of a second threshold number of received secret shares to the first variable of the polynomial to produce a second assigned value set of the first variable;

assign the second threshold number of received secret shares to the second variable of the polynomial to produce a second assigned value set of the second variable;

solve for the constant of the polynomial to produce a second message authentication key based on the second assigned value set of the first variable and the second assigned value set of the second variable;

compare the second message authentication key with the message authentication key to produce a comparison; and

indicate verification of the message authentication key when the comparison is favorable.

16. The computer of claim 13, wherein the processing module further functions to decode the received secret shares in accordance with a secret share function by:

decoding the received secret shares in accordance with an error coding dispersal storage function to recapture the message authentication key.

17. The computer of claim 13, 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 received 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.

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

identify a second received encoded data slice of the received encoded data slices having a second authentication code associated therewith when the threshold number of the encoded data slices is received;

verify the second authentication code based on the message authentication key and the second received encoded data slice; and

decode the received encoded data slices in accordance with an error coding dispersal storage function to recapture a data segment when the first and second authentication code are verified.

19. 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 an authentication code based on a message authentication key and an encoded data slice of the set of encoded data slices;

output, via the interface, the authentication code and the encoded data slice to a dispersed storage (DS) unit of a set of DS units;

encode the message authentication key into a set of secret shares based on at least some of the set of DS units; and

output, via the interface, a secret share of the set of secret shares to a corresponding one of the at least some of the set of DS units.

20. The computer of claim 19, wherein the processing module further functions to:

generate a second authentication code based on the message authentication key and a second encoded data slice of the set of encoded data slices; and

output, via the interface, the second authentication code and the second encoded data slice to a second DS unit of a set of DS units.

21. The computer of claim 19, 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.

22. The computer of claim 19, 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.

23. The computer of claim 19, 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 at least some of the set of DS units 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 at least some of the set of DS units 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.

24. The computer of claim 19, 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.