Cheap signatures for synchronous broadcast communication

• US 7,464,266 B2
• Filed: 02/13/2004
• Issued: 12/09/2008
• Est. Priority Date: 02/13/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wheeler, Graham A.
• Primary Examiner(s): SMITHERS, MATTHEW
• Application Number:
  US10/779,382
• Publication Number:
  US 20050182932A1
• Time in Patent Office: 1,761 Days
• Field of Search: 713/177, 713/160, 713/400, 713/401, 713/180, 713/176
• US Class Current: 713/168
• CPC Class Codes: H04L 2209/80 Wireless network architectures or network communication protocols for wireless network security H04W12/00
• CPC Class Codes: H04L 9/12 Transmitting and receiving encryption devices synchronised or initially set up in a particular manner
• CPC Class Codes: H04L 9/3242 involving keyed hash functions, e.g. message authentication codes [MACs], CBC-MAC or HMAC
• CPC Class Codes: H04L 9/3249 using RSA or related signature schemes, e.g. Rabin scheme
• CPC Class Codes: H04L 9/50 using hash chains, e.g. blockchains or hash trees

Abstract

A method and system are configured for synchronous broadcast communications by applying signature keys using hashing functions. Each subsequent transmission in a sequence includes a signature key that can be verified by hashing to a preceding signature key from a previous portion of the sequence. The first transmission in the sequence is signed using a signature key that is known by the client device, typically verified using some other mechanism such as asymmetric key signatures. Each client device can utilize an internal counter for the current time or the block number in the transmission sequence to maintain synchronized transmissions in the even that a particular portion of the sequence is missed, and to validate signature keys. Since the signature keys can be validated when they are received but not predicted before they are received, the transmission is difficult to attack while synchronization is maintained.

Claims

1. A method for signing frame transmissions from a broadcast server to a client device, comprising:

obtaining a data block that is scheduled for transmission in a next frame;

wherein the next frame includes segment groups;

wherein each segment group includes a number (n) of data blocks;

wherein each data block includes a plurality of packets;

selecting a secret key (S_n) that is associated with the client device for a predetermined number of the data blocks in the frame;

generating a count that is associated with a time;

computing a set of hash keys using the secret key (S_n) and the count;

selecting a hash key (S_i) that is associated with the data block, wherein the selected hash key corresponds to one of the set of hash keys;

computing a keyed-hash message authentication code (HMAC) value for the next frame using the hash key (S₁);

periodically signing and transmitting a datum containing the hash key of an earlier or initial frame with a digital signature key (K_S); and

assembling the next frame such that the data block and the HMAC value appear before the hash key in the frame transmission.

2. The method of claim 1 wherein the datum corresponds to at least one of {n, S₀)}K_s and (n, b, S_b) where b corresponds to a preceding frame number from a previous frame transmission.

3. The method of claim 1, further comprising:

selecting the count such that the count is associated with an index of the data block.

4. The method of claim 1, further comprising:

selecting the count such that the count corresponds to a time stamp associated with an internal clock in the broadcast server.

5. The method of claim 1, wherein computing the set of hash keys corresponds to applying a one-way hashing function to the secret key (S_n) for n iterations such that S_i=HASH(S_i+1).

6. The method of claim 1, wherein computing the HMAC value corresponds to a hashed message authentication code, wherein a value (H_i) associated with the hashed message authentication code is given as H_i=HMAC(F_i, S_i), where F_i corresponds to the data being signed, S_i the key for signing, and i the sequence number associated with the data and key.

7. The method of claim 1, further comprising:

selecting a new secret key as the secret key (S_n) when the previous secret key has been applied to n data blocks in the next frame.

8. The method of claim 1, wherein periodically signing the datum comprises signing the datum for every frame.

9. The method of claim 1, further comprising:

incrementing the count before retrieving a data block that is scheduled for transmission in the next frame.

10. The method of claim 9, wherein incrementing the count corresponds to at least one of:

incrementing a time step in the broadcast server, incrementing the frame number associated with the next frame that is scheduled for transmission, and incrementing the block number associated with the next data block in the next frame that is scheduled for transmission.

11. A method for authenticating frame transmissions from a server to a client device, comprising:

retrieving an Rivest Shamir Adleman (RSA) signed datum from a frame;

wherein the frame includes segment groups;

wherein each segment group includes data block;

wherein each of the data blocks include packets;

verifying an RSA signature associated with the RSA signed datum from the frame;

storing a hash key (S₀) that is associated with the frame when the RSA signature is verified;

retrieving another hash key (S_i) and an keyed-hash message authenticationcode (HMAC) value from the frame;

verifying the other hash key (S_i) that is obtained from a previous frame;

verifying the HMAC value with the other hash key (S_i);

computing a hash key using a count and a secert key (S_i) that is known by both the server and client device, wherein the count corresponds to a time stamp;

discarding the frame when at least one of the other hash key (S_i) and the HMAC value fail verification; and

accepting the frame when the other hash key (S_i) and the HMAC value are successfully verified.

12. The method of claim 11, identifies the frame number associated with the frame, and identifies the block number that is associated with the frame.

13. The method of claim 11, wherein verifying the other hash key (S_i) comprises:

retrieving a previously stored hash key, retrieving a count in the client device, computing an expected hash key from the previously stored hash key and the count, and comparing the expected hash key to the other hash key (S_i).

14. The method of claim 13, wherein the count corresponds to at least one of:

a time stamp in the client device, identifying the frame number associated with the frame, and identifying the block number that is associated with the frame.

15. The method of claim 11, wherein verifying the HMAC value with the other hash key (S_i) comprises:

computing a value (H_i) that is associated with a hashed message authentication code as given by H_i=HMAC(F_i, S_i), where F_i corresponds to the data being signed, S_i the key for signing, and i the sequence number associated with the data and key, and comparing the computed value with the retrieved HMAC value from the frame.

16. The method of claim 11, further comprising:

storing a verified hash key (S_i) for verification of further transmission frames after the hash key is accepted.

17. A broadcast communication system for communicating frame transmissions from a server to a client device, comprising:

a scheduler that is arranged to provide data blocks to the server for transmission in a next frame;

wherein each of the data block includes a plurality of packets;

a counter that is arranged to provide a count in the server;

a hashing function in the server that is arranged to compute hash keys for the next frame using the count and a secret key;

an HMAC function in the server that is arranged to provide an HMAC value in response to hash keys associated with the next frame;

a broadcast processor in the server that is arranged to receive the hash keys, HMAC values, and the data blocks, and organize the next frame for transmission

such that the data block and the HMAC value appear before the hash key in the frame transmission.

18. The broadcast communication system of claim 17, further comprising:

a broadcast receiver in the client device that is arranged to receive a transmitted frame, wherein the transmitted frame starts with another HMAC value, continues with another signed datum{n, S₀)}K_s followed by another data block, and ends with another hash key S_i;

a counter in the client device that is arranged to provide another count;

a hashing function in the client device that is arranged to compute additional hash keys for the frame transmission using the other count, the secret key, and previously stored hash keys;

a verification function block in the client device that is arranged to verify the other hash key (S_i) with the additional hash keys and verify the HMAC value with the other hash key (S_i) and previous hash keys;

a means for discarding the frame in the client device when at least one of the other hash key (S_i) and the HMAC value fail verification; and

a means for accepting the frame in the client device when the other hash key (S_i) and the HMAC value are successfully verified.

19. The broadcast communication system of claim 18, further comprising:

a means for recording the other hash key (S_i) when the frame is accepted, wherein the other hash key (S_i) is utilized for verification of subsequently received transmission frames.

20. A system for authenticating frame transmissions in a client device, comprising:

a broadcast receiver that is arranged to receive a transmitted frame, wherein the transmitted frame includes segment groups;

wherein each segment group includes data blocks;

wherein each of the data blocks include packets;

wherein the transmitted frame include an HMAC value and a data block, and ends with a hash key S_i;

a counter that is arranged to provide a count that has a time dependence;

a hashing function that is arranged to compute hash keys for the transmitted frame using the count and a secret key;

a verification function block that is arranged to verify the hash key (S_i) with the computed hash keys, and also arranged to verify the HMAC value with the hash key (S_i) and the previously stored hash keys;

a means for discarding the frame when at least one of the hash key (S_i) and the HMAC value fail verification;

a means for accepting the frame when the hash key (S_i) and the HMAC value are successfully verified; and

a means for storing the hash key as a previously stored hash key when the frame is accepted such that subsequent frames utilize the stored hash key for verification.