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

• US 6,959,384 B1
• Filed: 04/05/2000
• Issued: 10/25/2005
• Est. Priority Date: 12/14/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): Morse, Gregory
• Assistant Examiner(s): Brown, Christopher J.
• Application Number:
  US09/543,750
• Time in Patent Office: 2,029 Days
• Field of Search: 713/176
• US Class Current: 713/176
• 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 and authenticating a data block in a fault-tolerant fashion, the method including:

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

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

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

(a) receiving the encrypted second verification value;

(b) decrypting the encrypted second verification value;

(c) receiving the first hash value, a first portion of the encoded data stream, and the first verification value;

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

(e) 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

(f) 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.

2. A method for encoding and authenticating 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 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; and

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

(a) receiving the digital signature;

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

(c) receiving a first portion of the encoded data stream and the third verification value;

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

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

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

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

(h) receiving the second verification value;

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

(j) receiving a second portion of the encoded data stream and the first verification value;

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

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

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

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

3. A method as in claim 2, in which receiving and verifying the integrity of the encoded data stream further includes:

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

4. A method as in claim 2, 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.

5. A method as in claim 2, 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.

6. A method as in claim 2, in which the first cryptographic key is identical to the second cryptographic key.

7. A method as in claim 2, 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.

8. A method as in claim 2, in which the first verification value comprises a predefined data pattern.

9. A method as in claim 2, in which the encoded data stream further includes the second hash value, and in which receiving and verifying the integrity of the encoded data stream further includes:

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

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

10. A method as in claim 2, in which the encoded data stream further includes the second hash value, and in which receiving and verifying the integrity of the encoded data stream further includes:

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

(9)(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.

11. A method as in claim 10, in which receiving and verifying the integrity of the encoded data stream further includes:

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

12. A method for encoding a block of content in a manner designed to facilitate authentication, the method including:

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

(b) hashing a combination of 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.

13. A method as in claim 12, in which the first verification value is derived, at least in part, from a third portion of the block of content.

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

(a) performing a first operation on a first portion of the block of content to obtain a first transformed value;

(b) performing a second operation on a first input and the first transformed value to obtain a first check value;

(c) performing the first operation on a second portion of the block of content to obtain a second transformed value; and

(d) performing the second operation on a second input and the second transformed value to obtain a second check value, wherein the second input is derived, at least in art, from the first check value;

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

(f) sending the digital signature, the second portion of the block of content, the second input, the first check value, the first portion of the block of content, and the first input to a computer readable storage device;

wherein the first input is derived, at least in part, from a third portion of the block of content.

15. A method for verifying the integrity of data contained in a data stream, the method including:

(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) receiving a first block of data and the second check value;

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

(e) comparing the first check value with the first calculated check valii~

(f) allowing at least one use of the first block of data if the first check value is equal to the first calculated check value;

(g) receiving the third check value, a second block of data, and the fourth check value;

(h) 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;

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

(j) allowing at least one use of the second block of data if the third check value is equal to the second calculated check value.

16. A method as in claim 15, in which the at least one use of the first block of data includes 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.

17. A method as in claim 15, in which the predefined operation comprises a hashing operation.

18. A method as in claim 17, 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.

19. A method as in claim 15, 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.

20. A system for performing fault-tolerant authentication of a stream of data, the system in including:

(a) a receiver for receiving sub-blocks of the stream of data, error-check values corresponding to the sub-blocks, and verification values in a chain of verification values associated with the stream of data, wherein each verification value in the chain is derived, at least in part, from (i) a sub-block of the stream of data, and(ii) at least one other verification value in the chain;

(b) error-detection logic operable to use a received error-check value to detect errors in a corresponding sub-block of the stream of data;

(c) error-handling logic operable to record the detection of errors by the error-detection logic, and to block the receipt of additional sub-blocks if a predefined error condition is satisfied; and

(d) authentication logic operable to use a first received verification value to verify the integrity of a second received verification value and one of (i) a received sub-block of the data stream, and (ii) a received error-check value;

wherein the predefined error condition is the detection of a predefined pattern of errors by the error-detection logic.

21. A system for performing fault-tolerant authentication of a stream of data, the system in including:

(a) a receiver for receiving sub-blocks of the stream of data error-check values corresponding to the sub-blocks, and verification values in a chain of verification values associated with the stream of data, wherein each verification value in the chain is derived, at least in part, from (i) sub-block of the stream of data, an (ii) at least one other verification value in the chain;

(b) error-detection logic operable to use a received error-check value to detect errors in a corresponding a sub-block of the stream of data;

(c) error-handling logic operable to record the detection of errors by the error-detection logic, and to block the receipt of additional sub-blocks if a predefined error condition is satisfied; and

(d) authentication logic operable to use a first received verification value to verify the integrity of a second received verification value and one of (i) a received sub-block of the data stream, and (ii) a received error-check value;

wherein a the error-detection logic includes;

hashing logic for computing hash of a sub-block of the stream of data;

comparison logic for comparing the hash of the sub-block with a received error-check value.

22. A method for encoding a block of data in a manner designed to facilitate fault-tolerant authentication, the method including:

generating 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, including;

inserting each check value of the progression into the block of data, each check value being inserted in proximity to a portion of the block of data to which it corresponds; and

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 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.

23. A method for securely accessing a data block, the method including:

selecting a portion of the data block;

loading a root verification value and one or more stored check values in a hierarchy of check values into a memory unit, wherein the hierarchy of check values is derived, at least in part, from an uncorrupted version of the data block;

verifying the integrity of the one or more stored check values using, at least in part, the root verification value;

generating a calculated check value by performing a transformation on a first sub-block of the data block, the first sub-block including at least part of the selected portion of the data block;

comparing the calculated check value with a first verified stored check value; and

releasing at least part of the selected portion of the data block for use if the calculated check value equals the first verified stored check value.

24. A method as in claim 23, in which the memory unit comprises a stack.

25. A method as in claim 23, in which the root verification value is obtained by decrypting a digital signature associated with the data block.

26. A method as in claim 23, in which the root verification value is derived, at least in part, from the check values in the hierarchy of check values.

27. A method as in claim 23, in which the memory unit is tamper-resistant.

28. A method as in claim 23, in which the hierarchy of check values comprises a tree data structure.

29. A method as in claim 28, in which the tree data structure is symmetric.

30. A method as in claim 29, in which the tree data structure has a branching factor of four.

31. A method as in claim 23, further including:

inhibiting at least one use of the selected portion of the data block if the calculated check value is not equal to the first verified stored check value.

32. A method as in claim 23, in which verifying the integrity of the one or more stored check values includes:

using the root verification value to verify the integrity of a second stored check value in the hierarchy of check values; and

using the second stored check value to verify the integrity of a first stored check value.

33. A method as in claim 32, in which using the second stored check value to verify the integrity of the first stored check value includes:

comparing the second store check value with a calculated group check value, wherein the calculated group check value is obtained by combining the first stored check value with at least one other check value at the same level in the hierarchy of check values as the first stored check value.

34. A method as in claim 23, in which the first verified stored check value comprises a first hash value, and in which the calculated check value comprises a second hash value obtained by hashing the first sub-block.

35. A method as in claim 23, whereby a user can select a first portion of the data block, and whereby the selected portion of the data block can be authenticated using the root verification value without authenticating the entire data block.

36. A method as in claim 35, whereby the user can select a second portion of the data block, and whereby the second portion of the data block can be authenticated using the root verification value without re-authenticating the first portion of the data block.

37. A method for encoding a digital file in a manner designed to facilitate secure, quasi-random access to said digital file, the method including:

generating a multi-level hierarchy of hash values from the digital file, wherein one or more hash values on a first level of the hierarchy are derived, at least in part, from a plurality of hash values on a second level of the hierarchy;

digitally signing a root hash value, the root hash value being derived, at least in part, from each of the hash values in the hierarchy; and

storing the signed root hash value and a predefined number of levels of the multi-level hierarchy of hash value on a computer readable medium.

38. A method as in claim 37, in which generating the multi-level hierarchy of hash values includes:

hashing a first portion of the digital file to obtain a first hash value;

hashing a second portion of the digital file to obtain a second hash value;

combining at least the first and second hash values to yield a third hash value;

wherein the first and second hash values comprise at least part of said second level of the multi-level hierarchy of hash values, and wherein the third hash value comprises at least part of said first level of the hierarchy of hash values.

39. A method as in claim 38, in which combining at least the first and second hash values includes concatenating at least the first and second hash values and hashing the result.

40. A method as claimed in claim 37, whereby at least a portion of the hierarchy of hash values can be retrieved and used to authenticate a arbitrary-selected portion of the digital file.