Proof of retrievability for archived files

• US 8,984,363 B1
• Filed: 01/30/2013
• Issued: 03/17/2015
• Est. Priority Date: 05/03/2007
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Juels, Ari, Kaliski, Burton S. Jr., Bowers, Kevin D., Oprea, Alina M.
• Primary Examiner(s): Bonzo, Bryce
• Assistant Examiner(s): Mehrmanesh, Elmira
• Application Number:
  US13/753,839
• Time in Patent Office: 776 Days
• Field of Search: 714/752, 713/171, 726/26
• US Class Current: 714/752
• CPC Class Codes: G06F 11/10 Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: G06F 21/64 Protecting data integrity, e.g. using checksums, certificates or signatures
• CPC Class Codes: H04L 63/123 received data contents, e.g. message integrity
• CPC Class Codes: H04L 63/126 the source of the received data
• CPC Class Codes: H04L 9/3221 interactive zero-knowledge proofs

Abstract

A proof of retrievability (POR) mechanism is applicable to a data object for providing assurances of data object possession to a requesting client by transmitting only a portion of the entire data object. The client compares or examines validation values returned from predetermined validation segments of the data object with previously computed validation attributes for assessing the existence of the data object. Since the archive server does not have access to the validation function prior to the request, or challenge, from the client, the archive server cannot anticipate the validation values expected from the validation function. Further, since the validation segments from which the validation attributes, and hence the validation values were derived, are also unknown to the server, the server cannot anticipate which portions of the data object will be employed for validation.

Claims

1. A method comprising:

identifying a set of validation portions from a plurality of data portions comprising a data object, the set of validation portions including one or more subsets of validation portions for verifying recoverability of the data object;

determining, for each of the one or more subsets of the set of validation portions, recoverability attributes applicable to the subset of the set of validation portions;

defining a validation function, the validation function responsive to a challenge and for computing validation values, the validation values for comparison with corresponding recoverability attributes based on a particular subset of the set of validation portions from which the recoverability attributes were derived, the recoverability attributes for subsequent comparison with the corresponding validation values;

receiving a challenge indicative of a request to validate recoverability of the data object;

identifying the validation function responsive to the challenge for computing validation values;

determining, as a function of the received challenge, an indication of the subset of validation portions;

applying the validation function to each of the validation portions in the indicated subset to compute a validation value; and

comparing the validation value to a corresponding recoverability attribute to assess recoverability of the data object.

2. The method of claim 1 wherein defining the validation function comprises:

determining a validation key, the validation function responsive to the validation key for computing the recoverability attribute corresponding to a subset of the set of validation portions; and

generating the recoverability attributes for later comparison with the validation values.

3. The method of claim 2 wherein the validation key includes a message authentication code (MAC) key, further comprising:

selecting a MAC key known to a client and initially unknown to an archive server;

generating, using the validation function and the MAC key, the recoverability attribute of the subset of the set of validation portions;

associating the recoverability attribute of the subset of validation portions with the particular MAC key under which it was generated; and

subsequently, upon validation of the data object, sending to the archive sever information sufficient to compute the MAC key for computing validation values on the subset of portions using the validation function.

4. The method of claim 3 wherein the validation key is a symmetric key, the validation key providing a message authentication code (MAC), known to a client and requiring substantial computational resources to determine by the archive server without the validation key.

5. The method of claim 1 wherein the validation portions are sentinel values and the validation function returns the previously computed sentinel value wherein the sentinel values are stored as validation portions by at least one of insertion or overwriting in the data object.

6. The method of claim 1 wherein the validation function yields output that differs from an input subset of validation portions employed for computing the validation values.

7. The method of claim 1 wherein identifying the set of validation portions comprises:

determining a corruption threshold, the corruption threshold indicative of a minimum detectable corruption of the data object;

identifying, based on the corruption threshold, a size of the set of validation portions; and

computing the recoverability attributes by computing the validation portions according to the corruption threshold, the corruption threshold indicative of a number of data object validation portions for verifying existence of the data object on the archive server, the corruption threshold further comprising a ratio of coverage of the validation portions and a number of iterations.

8. The method of claim 7 further comprising establishing a recreation mechanism, the recreation mechanism operable to tolerate a corruption based on the corruption threshold.

9. The method of claim 1 wherein computing the validation portions of the data object comprises:

computing a run key corresponding to a particular subset of portions in the data object, the run key for computing an index to the validation portions of the data object;

providing, to an archive server, a portion function operable to identify, using the run key, the particular subset of validation portions;

sending the run key to an archive server as an indication of the subset of validation portions, the run key previously unknown to the server;

executing the portion function with the sent run key to identify the subset of the validation portions; and

computing the validation value for comparison with the corresponding recoverability attribute for validation indicated by the run key.

10. A method comprising:

identifying an error correction function operable to generate error correction values on portions of a data object, the error correction (ECC) values operable to recreate the data object;

identifying a portioning function for portioning the data object, the portioning generating a set of more than one portion, the combined generated portions sufficient for recovery of the data object;

applying the error correcting function individually to said portions to generate a set of ECC values, and associating said generated ECC values with the data object to create an augmented data object;

receiving a challenge indicative of a request to validate recoverability of the data object;

identifying a validation function, the validation function responsive to the challenge and for computing validation values, the validation values for comparison with corresponding recoverability attributes based on a particular subset of a set of validation portions from which the recoverability attributes were derived, the set of validation portions including one or more subsets of validation portions for verifying recoverability of the data object, the recoverability attributes applicable to the subset of the set of validation portions and for subsequent comparison with the corresponding validation values;

determining, as a function of the received challenge, an indication of the subset of validation portions,

applying the validation function to each of the validation portions in the indicated subset to compute a validation value;

comparing the validation value to a corresponding recoverability attribute to assess recoverability of the data object;

determining that the data object is not recoverable according to the validation portions;

recreating the data object according to augmented data object comprising the data object associated with the ECC.

11. The method of claim 10 further comprising transforming, via a transformation function, the augmented data object under a key such that without knowledge of said key, an association of ECC values to corresponding portions in the generated set of portions requires substantial computational resources.

12. The method of claim 10 where transforming comprises defining a reordering of at least two data elements within the augmented data object under the key, reversal of said reordering without knowledge of the key requiring substantial computational resources.

13. The method of claim 10 wherein the transformation function is determined by at least one permutation function, the at least one of the permutation function specifying an ordering on ECC values within the transformed data object, the at least one permutation function being unknown to an archive.

14. The method of claim 13 wherein associating the ECC values comprises appending the ECC values to the data object, further including interleaving the ECC values such that the association is not readily identifiable without a first permutation function, wherein the portioning function employed to generate the ECC values is a second permutation function.

15. The method of claim 10 wherein transforming the data object includes transforming such that error correction values are indiscernible from non-error correction values in the data object.

16. A POR (proof of recoverability) processor, comprising:

a portioner configured to identify a set of validation portions from a plurality of data portions comprising a data object, the set of validation portions including one or more subsets of validation portions for verifying recoverability of the data object;

a retrievability processor configured to determine, for each of the one or more subsets of the set of validation portions, recoverability attributes applicable to the subset of the set of validation portions and configured to generate a challenge indicative of a request to validate recoverability of the data object from an archive server and invoking a validation generator for identifying, the validation function;

an authenticator configured to define a validation function, the validation function responsive to a challenge for computing validation values, the validation values for comparison with corresponding recoverability attributes based on a particular subset of the set of validation portions from which the recoverability attributes were derived, the recoverability attributes for subsequent comparison with the corresponding validation values; and

a validator configured to receive an indication of the subset of validation portions, the indication previously unknown to the archive server, apply the validation function to each of the validation portions in the indicated subset to compute a validation value, and compare the validation value to a corresponding recoverability attribute to assess recoverability of the data object.

17. The POR processor of claim 16 further comprising:

an ECC encoder configured to identify an error correction function operable to generate error correction values on portions of a data object, the error correction (ECC) values operable to recreate the data object;

a portioner configured to identify a portionation function for portioning the data object, the portioning generating a set of the portions responsive to the ECC values, the generated portions based on a maximum corruptible portion of the data object sufficient for recovery;

an augmenter configured to augment the data object such that an association of error correction values to corresponding portions in the generated set of portions responsive to the ECC values is not apparent from the location of the ECC values in the data object;

the ECC encoder further configured to apply the error correction function to the data object to generate the ECC values; and

the portioner further configured to arrange the ECC values such that the portions upon which the ECC values are based are not apparent from the location of the ECC values in the data object.

18. A computer program product having a non-transitory computer readable storage medium operable to store computer program logic embodied in computer program code encoded as a set of processor based instructions thereon for storing a data object for subsequent proof of recoverability comprising:

computer program code for identifying a set of validation portions from a plurality of data portions comprising a data object, the set of validation portions including one or more subsets of validation portions for verifying recoverability of the data object;

computer program code for determining, for each of the one or more subsets of the set of validation portions, recoverability attributes applicable to the subset of the set of validation portions;

computer program code for defining a validation function, the validation function responsive to a challenge for computing validation values, the validation values for comparison with corresponding recoverability attributes based on a particular subset of the set of validation portions from which the recoverability attributes were derived, the recoverability attributes for subsequent comparison with the corresponding validation values; and

computer program code for receiving a challenge indicative of a request to validate recoverability of the data object by identifying the validation function, determining, as a function of the received challenge, an indication of the subset of validation portions, applying the validation function to each of the validation portions in the indicated subset to compute a validation value, and comparing the validation value to a corresponding recoverability attribute to assess recoverability of the data object.