MULTI-LEVEL FILE DIGESTS

• US 20100205446A1
• Filed: 04/23/2010
• Published: 08/12/2010
• 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: Gutnik, Yevgeniy, KENRICH, Michael Frederick
• Granted Patent: US 8,301,896 B2
• Time in Patent Office: Days
• 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-20. -20. (canceled)

21. A method 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.

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

23. The method of claim 21, further comprising:

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

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

25. The method of claim 23, further comprising:

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

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

27. The method of claim 21, further comprising:

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

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

29. The method of claim 28, further comprising:

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

recomputing the super digest.

30. A tangible computer-readable medium having computer-executable instructions stored thereon, execution of which, by a computing device, causes the computing device to perform a method 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.

31. The computer-readable medium of claim 30, the method 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.

32. The computer-readable medium of claim 30, the method further comprising:

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

33. The computer-readable medium of claim 32, wherein determining the super digest comprises determining the super digest from the intermediate digest and one or more additional intermediate digests.

34. The computer-readable medium of claim 32, the method further comprising:

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

35. The computer-readable medium of claim 32, the method 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.

36. The computer-readable medium of claim 30, the method further comprising:

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

37. The computer-readable medium of claim 36, the method 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.

38. The computer-readable medium of claim 37, the method further comprising:

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

recomputing the super digest.

39. A system comprising:

a tangible computer-readable medium 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.

40. A method 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.

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

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

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

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

45. A tangible computer-readable medium having computer-executable instructions stored thereon, execution of which, by a computing device, causes the computing device to perform a method 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.

46. The computer-readable medium of claim 45, the method 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.

47. The computer-readable medium of claim 45, the method 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.

48. The computer-readable medium of claim 47, 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.

49. The computer-readable medium of claim 47, 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.

50. A system comprising:

a tangible computer-readable medium 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.