Systems and methods for authenticating and protecting the integrity of data streams and other data

• US 7,340,602 B2
• Filed: 04/22/2005
• Issued: 03/04/2008
• Est. Priority Date: 06/08/1999
• Status: Expired due to Term

• Current Assignee: PLS IV, LLC (Pretium Partners, LLC)
• Original Assignee: Intertrust Technologies Corporation (Fidelio Acquisition Co LLC)
• Inventors: Serret-Avila, Xavier
• Primary Examiner(s): Zand; Kambiz
• Assistant Examiner(s): Brown; Christopher J
• Application Number:
  US11/112,520
• Publication Number:
  US 20050235154A1
• Time in Patent Office: 1,047 Days
• Field of Search: 713/176, 713/161
• US Class Current: 713/161
• CPC Class Codes: G06F 21/53 by executing in a restricted environment, e.g. sandbox or secure virtual machine
• CPC Class Codes: G06F 21/64 Protecting data integrity, e.g. using checksums, certificates or signatures
• CPC Class Codes: G06F 2221/2149 Restricted operating environment
• CPC Class Codes: H04L 2209/30 Compression, e.g. Merkle-Damgard construction
• CPC Class Codes: H04L 2209/603 Digital right managament [DRM]
• CPC Class Codes: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions
• CPC Class Codes: H04L 9/50 using hash chains, e.g. blockchains or hash trees

Abstract

Systems and methods are disclosed for enabling a recipient of a cryptographically-signed electronic communication to verify the authenticity of the communication on-the-fly using a signed chain of check values, the chain being constructed from the original content of the communication, and each check value in the chain being at least partially dependent on the signed root of the chain and a portion of the communication. Fault tolerance can be provided by including error-check values in the communication that enable a decoding device to maintain the chain'"'"'s security in the face of communication errors. In one embodiment, systems and methods are provided for enabling secure quasi-random access to a content file by constructing a hierarchy of hash values from the file, the hierarchy deriving its security in a manner similar to that used by the above-described chain. The hierarchy culminates with a signed hash that can be used to verify the integrity of other hash values in the hierarchy, and these other hash values can, in turn, be used to efficiently verify the authenticity of arbitrary portions of the content file.

Claims

1. A method for encoding a data block, the method comprising:

(1) encoding the data block, the encoding including;

(a) hashing a first portion of the data block to obtain a first hash value;

(b) hashing a combination of the first hash value and a first verification value to obtain a second verification value, wherein the first verification value is derived, at least in part, from a hashed portion of the data block and a third verification value;

(c) encrypting the second verification value; and

(2) transmitting an encoded data stream to a receiver, wherein the encoded data stream comprises the encrypted second verification value, the first hash value, the first portion of the data block, and the first verification value.

2. The method of claim 1, the method further comprising authenticating the data block, the method comprising:

(3) receiving the encoded data stream and verifying its integrity, including;

(a) decrypting the encrypted second verification value;

(b) hashing the first portion of the encoded data stream to obtain a first re-computed hash;

(c) comparing the first re-computed hash with the first hash value, and, if the first re-computed hash is not equal to the first hash value, hashing a combination of the first hash value and the first verification value to obtain a first calculated hash value; and

(d) comparing the second verification value with the first calculated hash value, and, if the second verification value is equal to the first calculated hash value, releasing the first portion of the encoded data stream for use.

3. A method for encoding a data block, the method including:

(1) generating a chain of data verification values, including;

(a) hashing a first sub-block of the data block to obtain a first hash value;

(b) hashing a combination of the first hash value and a first verification value to obtain a second verification value;

(c) hashing a second sub-block of the data block to obtain a second hash value;

(d) hashing a combination of the second hash value and a third verification value to obtain a fourth verification value, wherein the third verification value is derived, at least in part, from the second verification value;

(e) generating a digital signature by signing the fourth verification value using a first cryptographic key;

(2) transmitting an encoded data stream to a receiver, the encoded data stream including the digital signature, the second sub-block, the third verification value, the second verification value, the first sub-block, and the first verification value.

4. The method of claim 3, further comprising:

(3) receiving and verifying the integrity of the encoded data stream, including;

(a) using a second cryptographic key to unsign the digital signature to obtain the fourth verification value;

(b) hashing the first portion of the encoded data stream to obtain a first received hash value;

(c) hashing a combination of the first received hash value and the third verification value to obtain a first calculated hash;

(d) comparing the fourth verification value with the first calculated hash;

(e) releasing the first portion of the encoded data stream for use if the fourth verification value is equal to the first calculated hash;

(f) verifying that the second verification value is securely derived from the third verification value;

(g) hashing the second portion of the encoded data stream to obtain a second received hash value;

(h) hashing a combination of the second received hash value and the first verification value to obtain a second calculated hash;

(i) comparing the second verification value with the second calculated hash; and

(j) releasing the second portion of the encoded data stream for use if the second verification value is equal to the second calculated hash.

5. The method as in claim 4, in which (c) receiving and verifying the integrity of the encoded data stream further comprises:

(k) preventing further processing of the encoded data stream if the second verification value is not equal to the second calculated hash.

6. The method as in claim 3, in which the combination of the first hash value and the first verification value comprises a concatenation of the first hash value and the first verification value.

7. The method as in claim 3, in which:

the digital signature, the second sub-block, and the third verification value are transmitted consecutively in the encoded data stream; and

the second verification value, the first sub-block, and the first verification value are transmitted consecutively in the encoded data stream.

8. The method as in claim 4, in which the first cryptographic key is identical to the second cryptographic key.

9. The method as in claim 4, in which the first cryptographic key comprises a sender'"'"'s private key, and in which the second cryptographic key comprises the sender'"'"'s public key.

10. The method as in claim 3, in which the first verification value comprises a predefined data pattern.

11. The method as in claim 4, in which the encoded data stream further comprises the second hash value, and in which receiving and verifying the integrity of the encoded data stream further comprises:

(3)(c)(1) receiving the second hash value; and

(d)(1) replacing the first received hash value with the second hash value if the first received hash value is not equal to the second hash value.

12. The method as in claim 4, in which the encoded data stream further comprises the second hash value, and in which receiving and verifying the integrity of the encoded data stream further comprises:

(3)(c)(1) receiving the second hash value;

(g)(1) if the fourth verification value is not equal to the first calculated hash, generating a first recovered hash value by hashing a combination of the second hash value and the third verification value;

(g)(2) comparing the fourth verification value with the first recovered hash value;

(g)(3) releasing the first portion of the encoded data stream for use if the fourth verification value is equal to the first recovered hash value.

13. The method as in claim 12, in which receiving and verifying the integrity of the encoded data stream further comprises:

(g)(4) preventing further processing of the encoded data stream if the fourth verification value is not equal to the first recovered hash value.

14. A method for encoding a block of content in a manner designed to facilitate authentication comprising:

(a) hashing a first portion of the block of content to obtain a first hash value;

(b) combining the first hash value and a first data verification value to obtain a second verification value;

(c) hashing a second portion of the block of content to obtain a second hash value;

(d) hashing a combination of the second hash value and a third verification value to obtain a fourth verification value, wherein the third verification value is derived, at least in part, from the second verification value;

(e) generating a digital signature by signing the fourth verification value using a cryptographic key; and

(f) sending the digital signature, the second portion of the block of content, the third verification value, the second verification value, the first portion of the block of content, and the first verification value to a computer readable storage device.

15. The method as in claim 14, in which the first verification value is derived, at least in part, from a third portion of the block of content.

16. The method as in claim 14, wherein combining the first hash value and a first data verification value comprises hashing the first hash value and a first data verification value.

17. The method as in claim 14, wherein combining the second hash value and a third verification value comprises hashing the second hash value and a third verification value.

18. A method for verifying the integrity of data contained in a data stream comprising:

(a) receiving an encrypted first check value, the encrypted first check value being derived, at least in part, from a second check value, a third check value, a fourth check value, and the data;

(b) decrypting the encrypted first check value;

(c) obtaining a first calculated check value by performing a predefined operation on a combination of (i) a value derived from a first block of data, and (ii) the second check value;

(d) comparing the first check value with the first calculated check value;

(e) enabling use of the first block of data if the first check value is equal to the first calculated check value;

(f) receiving a second block of data;

(g) obtaining a second calculated check value by performing the predefined operation on a combination of (i) a value derived from the second block of data, and (ii) the fourth check value;

(h) comparing the third check value with the second calculated check value; and

(i) enabling use of the second block of data if the third check value is equal to the second calculated check value.

19. The method as in claim 18, in which enabling use of the first block of data comprises one of:

sending the first block of data to a speaker system;

displaying the first block of data on a viewing device;

printing the first block of data; and

storing the first block of data on a computer readable medium.

20. The method as in claim 18, in which the predefined operation comprises a hashing operation.

21. The method as in claim 20, in which the combination of (i) the value derived from the first block of data and, (ii) the second check value comprises a concatenation of the second check value with a hash of the first block of data.

22. The method as in claim 18, in which the second check value is derived, at least in part, from the third check value, and in which the third check value is derived, at least in part, from the fourth check value.

23. A system for encoding a stream of data, the system comprising:

(1) means for encoding the data block, the encoding including;

(a) means for hashing a first portion of the data block to obtain a first hash value;

(b) means for hashing a combination of the first hash value and a first verification value to obtain a second verification value, wherein the first verification value is derived, at least in part, from a hashed portion of the data block and a third verification value;

(c) means for encrypting the second verification value; and

(2) means for transmitting an encoded data stream to a receiver, wherein the encoded data stream comprises the encrypted second verification value, the first hash value, the first portion of the data block, and the first verification value.

24. The system of claim 23, the system further comprising means for authenticating the data block comprising:

(3) means for receiving the encoded data stream and verifying its integrity, including;

(a) means for decrypting the encrypted second verification value;

(b) means for hashing the first portion of the encoded data stream to obtain a first re-computed hash;

(c) means for comparing the first re-computed hash with the first hash value, and, if the first re-computed hash is not equal to the first hash value, hashing a combination of the first hash value and the first verification value to obtain a first calculated hash value; and

(d) means for comparing the second verification value with the first calculated hash value, and, if the second verification value is equal to the first calculated hash value, releasing the first portion of the encoded data stream for use.

25. A method for encoding a block of data in a manner designed to facilitate fault-tolerant authentication comprising:

generating a progression of check values, each check value in the progression being derived from a portion of the block of data and from at least one other check value in the progression;

generating an encoded block of data, comprising;

inserting error-check values into the block of data, each error-check value being inserted in proximity to a portion of the block of data to which it corresponds, and each error-check value being operable to facilitate authentication of a portion of the block of data and of a check value in the progression of check values;

transmitting the encoded block of data and the check values to a user'"'"'s system, whereby the user'"'"'s system is able to receive and authenticate portions of the encoded block of data before the entire encoded block of data is received,

wherein each error-check value comprises a hash of the portion of the block of data to which it corresponds.

26. The method as in claim 25, in which each check value in the progression comprises the hash of a combination of at least (i) a hash of the portion of the block of data to which it corresponds, and (ii) another check value in the progression.

27. A system for encoding a data block comprising:

(1) means for generating a chain of data verification values, including;

(a) means for hashing a first sub-block of the data block to obtain a first hash value;

(b) means for hashing a combination of the first hash value and a first verification value to obtain a second verification value;

(c) means for hashing a second sub-block of the data block to obtain a second hash value;

(d) means for hashing a combination of the second hash value and a third verification value to obtain a fourth verification value, wherein the third verification value is derived, at least in part, from the second verification value;

(e) means for generating a digital signature by signing the fourth verification value using a first cryptographic key;

(2) means for transmitting an encoded data stream to a receiver, the encoded data stream including the digital signature, the second sub-block, the third verification value, the second verification value, the first sub-block, and the first verification value.

28. The system of claim 27, further comprising:

(3) means for receiving and verifying the integrity of the encoded data stream, including;

(a) means for using a second cryptographic key to unsign the digital signature to obtain the fourth verification value;

(b) means for hashing the first portion of the encoded data stream to obtain a first received hash value;

(c) means for hashing a combination of the first received hash value and the third verification value to obtain a first calculated hash;

(d) means for comparing the fourth verification value with the first calculated hash;

(e) means for releasing the first portion of the encoded data stream for use if the fourth verification value is equal to the first calculated hash;

(f) means for verifying that the second verification value is securely derived from the third verification value;

(g) means for hashing the second portion of the encoded data stream to obtain a second received hash value;

(h) means for hashing a combination of the second received hash value and the first verification value to obtain a second calculated hash;

(i) means for comparing the second verification value with the second calculated hash; and

(j) means for releasing the second portion of the encoded data stream for use if the second verification value is equal to the second calculated hash.

29. The system as in claim 28, in which (c) means for receiving and verifying the integrity of the encoded data stream further comprises:

(k) means for preventing further processing of the encoded data stream if the second verification value is not equal to the second calculated hash.

30. The system as in claim 27, in which the combination of the first hash value and the first verification value comprises a concatenation of the first hash value and the first verification value.

31. The system as in claim 27, in which:

the digital signature, the second sub-block, and the third verification value are transmitted consecutively in the encoded data stream; and

the second verification value, the first sub-block, and the first verification value are transmitted consecutively in the encoded data stream.

32. The system as in claim 28, in which the first cryptographic key is identical to the second cryptographic key.

33. The system as in claim 28, in which the first cryptographic key comprises a sender'"'"'s private key, and in which the second cryptographic key comprises the sender'"'"'s public key.

34. The system as in claim 27, in which the first verification value comprises a predefined data pattern.

35. The system as in claim 28, in which the encoded data stream further comprises the second hash value, and in which means for receiving and verifying the integrity of the encoded data stream further comprises:

(3)(c)(1) means for receiving the second hash value; and

(d)(1) means for replacing the first received hash value with the second hash value if the first received hash value is not equal to the second hash value.

36. The system as in claim 28, in which the encoded data stream further comprises the second hash value, and in which means for receiving and verifying the integrity of the encoded data stream further comprises:

(3)(c)(1) means for receiving the second hash value;

(g)(1) means for, if the fourth verification value is not equal to the first calculated hash, generating a first recovered hash value by hashing a combination of the second hash value and the third verification value;

(g)(2) means for comparing the fourth verification value with the first recovered hash value; and

(g)(3) means for releasing the first portion of the encoded data stream for use if the fourth verification value is equal to the first recovered hash value.

37. The system as in claim 36, in which means for receiving and verifying the integrity of the encoded data stream further comprises:

(g)(4) means for preventing further processing of the encoded data stream if the fourth verification value is not equal to the first recovered hash value.

38. A system for encoding a block of content in a manner designed to facilitate authentication comprising:

(a) means for hashing a first portion of the block of content to obtain a first hash value;

(b) means for combining the first hash value and a first data verification value to obtain a second verification value;

(c) means for hashing a second portion of the block of content to obtain a second hash value;

(d) means for hashing a combination of the second hash value and a third verification value to obtain a fourth verification value, wherein the third verification value is derived, at least in part, from the second verification value;

(e) means for generating a digital signature by signing the fourth verification value using a cryptographic key; and

(f) means for sending the digital signature, the second portion of the block of content, the third verification value, the second verification value, the first portion of the block of content, and the first verification value to a computer readable storage device.

39. A system for verifying the integrity of data contained in a data stream comprising:

(a) means for receiving an encrypted first check value, the encrypted first check value being derived, at least in part, from a second check value, a third check value, a fourth check value, and the data;

(b) means for decrypting the encrypted first check value;

(c) means for obtaining a first calculated check value by performing a predefined operation on a combination of (i) a value derived from a first block of data, and (ii) the second check value;

(d) means for comparing the first check value with the first calculated check value;

(e) means for enabling use of the first block of data if the first check value is equal to the first calculated check value;

(f) means for receiving a second block of data;

(g) means for obtaining a second calculated check value by performing the predefined operation on a combination of (i) a value derived from the second block of data, and (ii) the fourth check value;

(h) means for comparing the third check value with the second calculated check value; and

(i) means for enabling use of the second block of data if the third check value is equal to the second calculated check value.

40. A system for encoding a block of data in a manner designed to facilitate fault-tolerant authentication comprising:

means for generating a progression of check values, each check value in the progression being derived from a portion of the block of data and from at least one other check value in the progression;

means for generating an encoded block of data, comprising;

means for inserting error-check values into the block of data, each error-check value being inserted in proximity to a portion of the block of data to which it corresponds, and each error-check value being operable to facilitate authentication of a portion of the block of data and of a check value in the progression of check values;

means for transmitting the encoded block of data and the check values to a user'"'"'s system, whereby the user'"'"'s system is able to receive and authenticate portions of the encoded block of data before the entire encoded block of data is received,

wherein each error-check value comprises a hash of the portion of the block of data to which it corresponds.