Multi-level file digests

• US 8,301,896 B2
• Filed: 04/23/2010
• Issued: 10/30/2012
• Est. Priority Date: 07/19/2004
• Status: Active Grant

• Current Assignee: Intellectual Ventures I LLC (Intellectual Ventures LLC)
• Original Assignee: Guardian Data Storage LLC
• Inventors: Kenrich, Michael Frederick, Gutnik, Yevgeniy
• Primary Examiner(s): Perungavoor, Venkat
• Application Number:
  US12/766,536
• Publication Number:
  US 20100205446A1
• Time in Patent Office: 921 Days
• Field of Search: None
• US Class Current: 713/181
• CPC Class Codes: H04L 2209/60 Digital content management, e.g. content distribution
• CPC Class Codes: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 63/105 Multiple levels of security
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions

Abstract

Multi-level file digests for electronic files are disclosed. A top level digest represents a single digest for the associated electronic file. Lower level digests represent digests for portions of the associated electronic file. The top level digest is derived from the lower level digests. The top level digest is useful for facilitating rapid comparison to determine whether electronic files are the same. In one embodiment, electronic files are encrypted with a block encryption scheme, and digests are efficiently calculated and stored on a block-by-block basis. Advantageously, when modifications to an encrypted electronic file occurs, only those modified blocks need to be processed to undergo decryption and re-encryption to determine the appropriate digest.

Claims

1. A method comprising:

determining, by at least one processing device, block digests for blocks of data of an electronic file;

encrypting, by the at least one processing device, the blocks of data of the electronic file;

determining, by the at least one processing device, a super digest for the electronic file from the block digests;

storing, by the at least one processing device, the encrypted blocks of data of the electronic file in a body of an encrypted electronic file; and

storing, by the at least one processing device, the super digest in an encrypted portion of a header of the encrypted electronic file.

2. The method of claim 1, further comprising:

computing an additional super digest for a non-encrypted electronic file; and

comparing the super digest to the additional super digest in order to determine whether the encrypted electronic file and the non-encrypted electronic file comprise a same set of data.

3. The method of claim 1, further comprising:

determining an intermediate digest from a subset of the block digests.

4. The method of claim 3, wherein determining the super digest comprises determining the super digest from the intermediate digest and one or more additional intermediate digests.

5. The method of claim 3, further comprising:

storing the intermediate digest in the encrypted portion of the header of the encrypted electronic file.

6. The method of claim 3, further comprising:

computing an additional intermediate digest from an additional subset of block digests for a non-encrypted electronic file; and

comparing the intermediate digest to the additional intermediate digest in order to directly modify the subset of block digests of the encrypted electronic file.

7. The method of claim 1, further comprising:

storing the block digests in the encrypted portion of the header of the encrypted electronic file.

8. The method of claim 7, further comprising:

comparing a block digest of the encrypted electronic file to a block digest of a non-encrypted electronic file to identify a modified corresponding encrypted block of data;

decrypting the encrypted block of data to produce a decrypted block of data;

modifying the decrypted block of data; and

re-encrypting the modified decrypted block of data.

9. The method of claim 8, further comprising:

recomputing the block digest corresponding to the encrypted block of data; and

recomputing the super digest.

10. A computer-readable device having computer-executable instructions stored thereon, execution of which, by a computing device, causes the computing device to perform operations comprising:

determining block digests for blocks of data of an electronic file;

encrypting the blocks of data of the electronic file;

determining a super digest for the electronic file from the block digests;

storing the encrypted blocks of data of the electronic file in a body of an encrypted electronic file; and

storing the super digest in an encrypted portion of a header of the encrypted electronic file.

11. The computer-readable device of claim 10, the operations further comprising:

computing an additional super digest for a non-encrypted electronic file; and

comparing the super digest to the additional super digest in order to determine whether the encrypted electronic file and the non-encrypted electronic file comprise a same set of data.

12. The computer-readable device of claim 10, the operations further comprising:

determining an intermediate digest from a subset of the block digests.

13. The computer-readable device of claim 12, wherein determining the super digest comprises determining the super digest from the intermediate digest and one or more additional intermediate digests.

14. The computer-readable device of claim 12, the operations further comprising:

storing the intermediate digest in the encrypted portion of the header of the encrypted electronic file.

15. The computer-readable device of claim 12, the operations further comprising:

computing an additional intermediate digest from an additional subset of block digests for a non-encrypted electronic file; and

comparing the intermediate digest to the additional intermediate digest in order to directly modify the subset of block digests of the encrypted electronic file.

16. The computer-readable device of claim 10, the operations further comprising:

storing the block digests in the encrypted portion of the header of the encrypted electronic file.

17. The computer-readable device of claim 16, the operations further comprising:

comparing a block digest of the encrypted electronic file to a block digest of a non-encrypted electronic file to identify a modified corresponding encrypted block of data;

decrypting the encrypted block of data to produce a decrypted block of data;

modifying the decrypted block of data; and

re-encrypting the modified decrypted block of data.

18. The computer-readable device of claim 17, the operations further comprising:

recomputing the block digest corresponding to the encrypted block of data; and

recomputing the super digest.

19. A system comprising:

a computer-readable device configured to store;

a determining module configured to determine block digests for blocks of data of an electronic file,

an encrypting module configured to encrypt the blocks of data of the electronic file,

a determining module configured to determine a super digest for the electronic file from the block digests,

a storing module configured to store the encrypted blocks of data of the electronic file in a body of an encrypted electronic file, and

a storing module configured to store the super digest in an encrypted portion of a header of the encrypted electronic file; and

one or more processors configured to process the modules.

20. A method comprising:

receiving, by at least one processing device, a block-encrypted file having corresponding block digests and a super digest;

comparing, by the at least one processing device, the super digest to a known valid super digest value to determine whether any errors exist within the block-encrypted file;

comparing, by the at least one processing device, one or more of the block digests to known valid block digest values to determine whether any errors exist within corresponding blocks of the block-encrypted file, based on a determination that errors exist within the block encrypted file; and

identifying, by the at least one processing device, one or more of the corresponding blocks having errors.

21. The method of claim 20, further comprising:

comparing one or more intermediate digests determined from subsets of the block digests to known valid intermediate digests to determine whether any errors exist in corresponding subsets of the block digests of the block-encrypted file.

22. The method of claim 20, further comprising:

computing the known valid super digest value from a known valid electronic file; and

computing the known valid block digest values from the known valid electronic file.

23. The method of claim 22, wherein computing the known valid super digest value from the known valid electronic file comprises computing the known valid super digest value from a known valid encrypted electronic file.

24. The method of claim 22, wherein computing the known valid super digest value from the known valid electronic file comprises computing the known valid super digest value from a known valid unencrypted electronic file.

25. A computer-readable device having computer-executable instructions stored thereon, execution of which, by a computing device, causes the computing device to perform operations comprising:

receiving a block-encrypted file having corresponding block digests and a super digest;

comparing the super digest to a known valid super digest value to determine whether any errors exist within the block-encrypted file;

comparing one or more of the block digests to known valid block digest values to determine whether any errors exist within corresponding blocks of the block-encrypted file, based on a determination that errors exist within the block encrypted file; and

identifying one or more of the corresponding blocks having errors.

26. The computer-readable device of claim 25, the operations further comprising:

comparing one or more intermediate digests determined from subsets of the block digests to known valid intermediate digests to determine whether any errors exist in corresponding subsets of the block digests of the block-encrypted file.

27. The computer-readable device of claim 25, the operations further comprising:

computing the known valid super digest value from a known valid electronic file; and

computing the known valid block digest values from the known valid electronic file.

28. The computer-readable device of claim 27, wherein computing the known valid super digest value from the known valid electronic file comprises computing the known valid super digest value from a known valid encrypted electronic file.

29. The computer-readable device of claim 27, wherein computing the known valid super digest value from the known valid electronic file comprises computing the known valid super digest value from a known valid unencrypted electronic file.

30. A system comprising:

a computer-readable device configured to store;

a receiving module configured to receive a block-encrypted file having corresponding block digests and a super digest,

a comparing module configured to compare the super digest to a known valid super digest value to determine whether any errors exist within the block-encrypted file,

a comparing module configured to compare one or more of the block digests to known valid block digest values to determine whether any errors exist within corresponding blocks of the block-encrypted file, based on a determination that errors exist within the block encrypted file, and

an identifying module configured to identify one or more of the corresponding blocks having errors; and

one or more processors configured to process the modules.