Systems and methods for authenticating and protecting the integrity of data streams and other data
First Claim
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.
4 Assignments
0 Petitions
Accused Products
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.
-
Citations
40 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. - View Dependent Claims (3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
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. - View Dependent Claims (13)
-
-
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. - View Dependent Claims (16, 17, 18, 19)
-
-
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. - View Dependent Claims (24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36)
-
-
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. - View Dependent Claims (38, 39, 40)
-
Specification