Systems and methods for protecting a multi-part broadcast control message

A method and/or apparatus are provided for protecting control information during broadcasts in a system where primary and second mobile broadcast control messages (PMBCM and SMBCM) are utilized. In order to protect the SMBCM, a first hash information instance is computed based on hashes for each a plurality of control data blocks for the SMBCM. The first hash information instance is appended to the PMBCM. Error-correcting code words are generated for the plurality of hashes for the plurality of control data blocks for the SMBCM. These error-correcting code words are appended to the control data blocks of the SMBCM. A receiver uses the first hash instance information in the PMBCM to determine if any control data blocks of the SMBCM are corrupt. If so, the error-correcting code words may be used to reconstruct the corrupted hash(es) for the control data block(s) in order to authenticate the remaining control data blocks.

BACKGROUND

Various features pertain to broadcast control channels. At least one aspect pertains to methods for protecting a multiple message broadcast control channel.

In a wireless multicast or broadcast delivery system, content and control information are transmitted from a single network server to several recipients over a lossy transmission environment, i.e., a wireless multicast channel. The control information typically includes two types of messages, a single primary message and one or more secondary messages. The primary message contains information that is processed by every recipient. It contains global information about the transmission network and includes identification information about the secondary messages, i.e. secondary messages identifiers. Therefore, the primary message is typically processed by the recipients before any of the secondary messages can be processed.

Secondary message includes data blocks, that is, a number M data blocks, which contain information that only a subset of the N recipients actually process. For example, the secondary messages may be addressed to a subset of all the recipients while the data blocks may be targeted for one or more recipients within the subset. The secondary messages may also be processed by every recipient or by only some of the recipients. The data blocks may also be processed by all or only some of the recipients.

It is possible for the recipients to receive erroneous information from these messages. Noise from the transmission media may alter the contents of the primary and/or secondary messages. Also, interference, such as intentional interference by malicious parties attempting to interfere with the communications may alter the primary and/or secondary messages. In most communication systems, the underlying communication infrastructure applies error-correcting codes to a whole message that can correct many, but not all, transmission errors. However, the error-correcting codes are able to detect the uncorrectable errors. In this case, the data blocks with uncorrectable errors are treated as erasures, and the corresponding data is ignored by the recipients.

While corrupted, erroneous or tampered data blocks (e.g., containing video, audio, etc.) may cause some information to be presented incorrectly or incomplete, its malicious effects are relatively limited. However, if blocks containing control messages are modified or tampered in transit (e.g., by a malicious entity), these control messages can potentially change or modify the operation of the receiver device (e.g., change codes, channels, security levels, etc.) thereby compromising its operation and/or security. In such scenarios, it is the goal of an attacker to cause the recipients to process these modified control messages, thereby changing the receiver's state of operation to a malicious state. Consequently, a method is needed to efficiently protect a multi-part broadcast control messages during transmission and/or be able to ascertain whether a control message has or has not been modified.

SUMMARY

A method and/or apparatus are provided for protecting control information during broadcasts in a system where primary and second mobile broadcast control messages (PMBCM and SMBCM) are utilized.

According to one feature, a method for generating a secondary broadcast control message is provided that may be implemented, for example, on a transmitter, encoder, processor, and/or may be stored in a computer-readable medium. A secondary broadcast control message is generated that includes a plurality of control data blocks and error correcting code words. Information for the secondary broadcast control message may be included in a primary broadcast control message. A first hash information instance may be computed for the secondary broadcast control message based on a plurality of hashes for the plurality of control data blocks of the secondary broadcast control message. The first hash information instance may be included in the primary broadcast control message. The primary broadcast control message and the secondary broadcast control message may then be transmitted or broadcasted.

In one example, computing the first hash information instance for the secondary broadcast control message based on a plurality of hashes for the plurality of control data blocks of the secondary broadcast control message may include (a) computing a first hash from a first control data block of the secondary broadcast control message, (b) computing a second hash from a second control data block of the secondary broadcast control message; and/or (c) computing the first hash information instance from the first hash and the second hash. A first error correcting code word may be computed based on the first hash and one or more additional hashes for the control data blocks of the secondary broadcast control message. A second error correcting code word may be computed based on the second hash and one or more additional hashes for the control data blocks of the secondary broadcast control message. The first error correcting code word and the second error correcting code word may be included in the secondary broadcast control message. The first error correcting code word may be included as part of the first control data block and the second error correcting code word may be included as pan of the second the control data block. In one example, the first error correcting code word may also be based at least partially on the second hash.

According to another feature, a method for processing a secondary broadcast control message is provided that may be implemented, for example, on a receiver, decoder, processor, and/or may be stored in a computer-readable medium. A primary broadcast control message may be obtained. A secondary broadcast control message associated with the primary broadcast control message may also be obtained. For instance, the primary broadcast control message and secondary broadcast control message may be wirelessly received as part of one or more broadcasts. A first hash information instance for the secondary broadcast control message in the primary broadcast control message may be identified. A second hash information instance may be computed based on a plurality of control data blocks of the secondary broadcast control message, where the secondary broadcast control message includes error correcting code words that facilitate computing a correct version of the second hash information even if one or more of the control data blocks have been compromised. In one example, each control data block may have an appended error correcting code word based on one or more computed hashes for the plurality of control data blocks. The first hash information instance may then be compared to the second hash information instance to determine whether the secondary broadcast control message has been compromised. A digital signature of the primary broadcast control message may also be verified, where the digital signature covers the primary broadcast control message and the first hash information instance.

A determination may then be made that a first control data block has been compromised. As a result, a first hash of the first control data block may be reconstructed from the error correcting code words. The second hash information may then be computed based on the first hash and one or more additional hashes for the plurality of control data blocks.

According to one aspect, a determination may be made that a first control data block of the secondary broadcast control message has been compromised based on an error correcting code calculation. As a result, a code word may be identified corresponding to a second control data block of the secondary broadcast control message. A first hash may then be computed for the first control data block of the secondary broadcast control message based at least in part on an error correcting code word corresponding to the second control data block of the secondary broadcast control message. A second hash may be computed from the second control data block of the secondary broadcast control message. The second hash information instance may then be computed from the first hash and the second hash. Computing the second hash information instance may include: (a) computing a first hash from a first control data block of the secondary broadcast control message; (b) computing a second hash from a second control data block of the secondary broadcast control message; and/or (c) computing the second hash information instance from the first hash and the second hash.

According to another aspect, if the comparison of the first hash information instance to the second hash information instance indicates that the secondary broadcast control message has been compromised additional steps may be performed. A third hash may be computed from a first code word corresponding to the first control data block. A fourth hash may be computed from a second code word corresponding to the second control data block. The second hash information instance may be recomputed from the third hash and the fourth hash. The first hash information instance may then be compared to the recomputed second hash information instance to determine whether the secondary broadcast control message has been compromised. The recomputed second hash information instance may then be compared to the first hash information instance to determine if they match. If a match is determined, (a) the one or more compromised control data blocks of the secondary broadcast control message may be identified and/or discarded, and/or (b) one or more of the remaining control data blocks may be utilized. If no match is determined, the secondary broadcast control message may be discarded.

According to yet another aspect, if the comparison of the first hash information instance to the second hash information instance indicates that the secondary broadcast control message has been compromised, additional steps may be performed. A first code word may be obtained corresponding to the first control data block and including information for a hash of the second control data block. A third hash may be computed for the second control data block based on information from the first code word. The second hash information may be recomputed instance from the first hash and the third hash. The recomputed second hash information instance may then be compared to the first hash information instance to determine if they match. If a match is determined, (a) the second control data block identified and/or discarded, and (b) one or more of the remaining control data blocks may be utilized. If no match is determined, (a) a second code word may be obtained that corresponds to the second control data block and includes information for a hash of the first control data block, (b) a fourth hash may be computed based on information from the second code word, and/or (c) the second hash information instance may be recomputed from the second hash and the fourth hash.

DETAILED DESCRIPTION

In the following description, specific details are given to provide a thorough understanding of the embodiments. However, it will be understood by one of ordinary skill in the art that the embodiments may be practiced without these specific detail. For example, circuits may be shown in block diagrams in order not to obscure the embodiments in unnecessary detail. In other instances, well-known circuits, structures and techniques may be shown in detail in order not to obscure the embodiments.

Overview

In multicast or broadcast distribution systems, control information, such as service guides, end-user license agreements, etc., need to be distributed to recipients correctly. An attacker can modify this control information, having an undesirable effect to the overall system. Usually, this risk can be addressed by computing a cryptographic authentication code over all of the control information. However, transmission errors caused by the noisy nature of the transmission medium may cause failed authentication verification. The amount of transmission errors can be reduced with the use of error correcting codes, such as Reed-Solomon codes, but not eliminated. While a message (including data and control information) may be protected by an error correcting code over the whole message, this does not distinguish between errors to data versus errors to control messages. Note that when errors to data (e.g., video, audio, etc.) occur, such data may often be ignored or reconstructed without significant deleterious effects. However, when errors are present to control information (e.g., control messages that can modify the operation or a receiver), these errors may be more difficult to reconstruct and can affect the performance of a system if retransmissions are needed.

A scheme is provided herein which combines erasure codes, digital signatures, and cryptographic hashes to enable control information to be verified in the presence of transmission errors. By using erasure codes, hash values of lost blocks of a control message can be regenerated. The regenerated hash values are then used to verify the remaining information in a strong cryptographic manner.

In one example, a private/public cryptographic key pair is generated by a security server. The private key is securely stored at the server, while the public key is distributed to all recipients that are to receive a multicast transmission (e.g., including a primary and second message). In addition to the private/public key pair, the server and the recipients may also generate an erasure code generator matrix, such as a Reed-Solomon Erasure Code Generator Matrix R. When the server is creating a primary message and a secondary message (comprising a plurality of data blocks) for transmission or broadcasting to the recipients, it generates a hash hx for each data block within the secondary message. These hash values hx may be combined to form a hash vector H, which the transposed vector is HT=[h1h2. . . hM] for x=1 . . . M. Using these hash values, a plurality of erasure codes C, which the transposed vector is CT=[c1c2. . . cM] for x=1 . . . M, can be generated such that C=RH. Then, a hash of the hash vector H is computed and stored as part of the primary message by the server. This is done for each of the secondary messages. Then, the server computes the digital signature of the primary message using the private key and sends it with the primary message. Finally, the erasure codes C are appended to the corresponding data block in every secondary message, which is sent to the recipients. An erasure code transforms a message of n blocks into a message with more than n blocks, such that the original message can be recovered from a subset of those blocks. The fraction of the blocks required to reconstruct is called the rate, denoted r. Erasure codes are used as part of forward error correction.

In the primary message, all of the information, including the hash information, is secured by the digital signature. Upon receiving the primary message, the recipients verify its digital signature. If the signature verification fails (e.g., either by modification by an attacker or noise on the transmission channel), the primary message is discarded. If the signature verification is successful, the recipients process the primary message; this includes identification and hash information for the secondary messages. Then, the recipients acquire the secondary messages using the information from the primary message. If the secondary message is received without any transmission errors, then the hash of each data block is computed and combined to form a hash vector. Then, the hash of the hash vector is locally computed and compared to the received hash from the primary message. If the hash from the primary message matches the computed hash, then the secondary message is received correctly and can be processed. If the hash from the primary message does not match the computed hash, then the secondary message is assumed to have been modified and is discarded. If the secondary message is received with transmission errors that corrupted K data blocks (where K<M/2), then the hash of each of the M-K error-free data blocks is computed. Then, K erasure code words are taken from any of the M-K data blocks. The K erasure code words are combined with the M-K computed hash values and input into an erasure code decoder, which regenerates the missing K hash values. The regenerated K hashes are combined with the computed M-K hashes to form a local version of the hash vector. Then, the hash of the locally-computed hash vector is computed and compared to the received hash from the primary message. If the received hash from the primary message matches the locally-computed hash, then the M-K data blocks from the secondary message are received correctly and can be processed. If the received hash from the primary message does not match the locally-computed hash, then the secondary message is assumed to have been modified and is discarded.

Example Network Environment

FIG. 1is a block diagram showing an example mobile broadcast system100in which a primary mobile broadcast control message (PMBCM) is protected by a digital signature. A secondary mobile broadcast control message (SMBCM) is also protected by the digital signature because hash information of the SMBCM is protected by the digital signature in the PMBCM.

In one example, broadcast message transmissions130may include content132(e.g., video, data, etc.), control information134), and a message error correcting code (ECC)136over the whole message130. The control information130may include a PMBCM138and one or more SMBCMs140and142associated with the PMBCM138.

A network operations center102collects broadcast signals and prepares them for broadcast over a mobile broadcast network. For example, the mobile broadcast network may be a Media Forward Link Only (MediaFLO) network, which is standardized by the FLO Forum. Other example broadcast networks are Digital Video Broadcasting-Handheld (DVB-H), published as European Telecommunications Standards Institute (ETSI) standard EN302304, Digital Multimedia Broadcasting (DMB) in Korea, and Integrated Services Digital Broadcasting (ISDB), by the Association of Radio Industries and Businesses in Japan. The systems and methods described herein are not limited to the above example mobile broadcast systems, but could be applied to other broadcast systems as well.

The network operations center102may receive content (e.g., video and/or data) and process it for distribution to a transmitter site104. Content may be received by satellite signal at an antenna106. Alternatively, content may be received from the internet or other network (not shown). A receiver/decoder108demodulates and decodes the received content. A transcoder110(e.g., transmission coder) codes the content for mobile broadcasting. A transmit multiplexer112may multiplex the content (e.g., video and/or data) with control information to generate a multiplexed stream of control information113for transmission. The network operations center102then transmits the multiplexed stream115to the transmitter site104.

The transmitter site104may include a receiver/decoder114which receives and decodes the multiplexed broadcast signals from the network operations center102. Signals may be transmitted to the transmitter site104by satellite, or by other high speed data transmission network, such as, for example, a fiber optic network (not shown). The transmitter/encoder116encodes and transmits mobile broadcast signals to one or more mobile wireless devices118,120and122. Prior to transmission, the transmitter/encoder116may generate an error correcting code for the whole transmission, which can be used by a recipient to determine if the transmission is corrupt and potentially regenerate the corrupted portions.

In one example, content and control information may be transmitted (e.g., as part of message130) from a network server, e.g., network operations center102to N recipients (shown as wireless devices118,120and122) over a lossy transmission environment, i.e., a wireless multicast channel. Control information134may include at least two types of messages: a PMBCM and one or more SMBCMs.

Note that, unless the multiplexed stream115(e.g., content and/or control information) is protected, there is a risk that an attacker A117may intercept the stream115and replace the control information therein with its own control information, and retransmit it to the transmitter site104(thereby attempting to modify the operation of recipient wireless devices). An attacker B119may also intercept messages broadcasted from the transmitter site104in order to replace control information therein.

The error correcting code136generated by the transmitter/encoder116may be used to detect transmission errors by the recipient devices118,120and122. However, an attacker110may intercept the transmission130, insert or replace control messages in the transmission, generate its own error correcting code, and retransmit the message such that no error is detected by the devices118,120and122. Consequently, this conventional use of error correcting codes over the whole transmission or message130is inadequate to protect against attackers that replace control information.

According to one feature, an additional level of error correcting codes are used to specifically protect control information against corruption or replacement during transmission.

Related Message Protection Approaches

Various approaches may be used to protect a primary message and/or secondary message from attackers.

A first approach provides a digital signature over the primary message and a separate digital signature over the secondary message, using a private key at the server. The recipients use a public key to verify the digital signatures. In this approach, an error in any of the M data blocks of the secondary message causes all of the M data blocks to be discarded, since there is no way to determine which of the M data blocks has the error or was attacked.

A second approach computes a keyed-hash over each secondary message using a shared secret key between the server and the network devices. In addition to the shortcomings of the first approach, this approach also has a problem with non-repudiation since there is no way to determine the actual sender of the secondary messages. Non-repudiation means being certain of who sent the message, so that a sender cannot claim not to be the sender of a message, or repudiate the message.

A third approach computes a digital signature over the primary message and a digital signature over each of the M data blocks in a secondary message. While this third approach addresses the issues associated with the first and second approaches, the size of the digital signature may be prohibitively large in relation to the size of the data block. Moreover, the processing requirement to verify the M digital signatures for each block is also burdensome on the recipients.

A fourth approach generates a hash tree over the second message and stores the root hash in the primary message. A digital signature is computed over the primary message. This approach addresses the processing issue with the third approach. However, each data block must contain enough hash information to guarantee that each data block can be verified independently of the others. For small numbers of data blocks M, the amount of additional hash information is manageable but can quickly grow as the data blocks M increases.

Example Method for Protecting Multi-Part Control Message

FIG. 2is a block diagram of a system for efficiently protecting a mobile broadcast control message (MBCM) that is divided between a PMBCM and a SMBCM. In one example, this process may be implemented at a transmitter of a MBCM. As used herein, an MBCM may be part of a larger broadcast or transmission (such as130inFIG. 1) that is protected by a high level ECC136(FIG. 1). A PMBCM202may include a primary message payload204, hash information206of at least a part of a SMBCM and a digital signature208. The primary message payload204may include global information about the transmission network, and identification information248about at least one SMBCM210, i.e. secondary messages identifiers. The PMBCM202is typically processed by the recipients before any of the secondary messages are processed. The SMBCM210may include one or more control data blocks.

It may be more important for the control data blocks to be protected than typical data carrying data blocks. Data carrying blocks may be video data which, if corrupted or received with errors, would only temporarily or minimally affect a user's experience (e.g., temporary degradation of a video display, or temporary loss of signal). However, the video signal typically returns to normal after a short time. However, control data blocks may affect the operation of the receiving device (e.g., which channels are viewed in a mobile video system, security codes, content restrictions or control. If the control data blocks are received in error, the functioning of the mobile video device may be impaired. For example, the wrong channels may be displayed, or no channels at all. Accordingly, it may be more important to protect the control data blocks.

One example of the SMBCM210is shown. Each SMBCM210includes M control data blocks212,214,216,218,220,222,224and226, which contain information that only a subset of the N recipients may actually process. For example, the SMBCMs may be addressed to a subset of all the recipients while the control data blocks may be targeted for one or more recipients within the subset. A secondary message identification248may include information identifying which SMBCMs are needed by or targeted to which receivers. For example, the secondary message identification248may include a mapping of a service or channel to an SMBCM ID. In that case, receivers would identify the service or channel selected and read the mapping from the selected service or channel to the mapped SMBCM ID. Accordingly, the receiver would know which SMBCMs to read.

For example,FIG. 3is a block diagram illustrating certain control data blocks of a secondary message being dedicated for specific mobile wireless receivers. The SMBCM302may include a plurality of control data blocks, control data block1(DB1)304, control data block2(DB2)306to control data block M-1 (DB M-1)308and control data block M (DB M)310. In the example ofFIG. 3, there are N receivers (R). The control data block DB1304is intended for, and will be processed by, Receiver1(R1)312, Receiver4(R4)315, Receiver N-6 (R(N-6))314and Receiver R(N-5) (R(N-5))316, as indicated by solid line318. Similarly, control data block DB2306is intended for receivers R(2)320, R(3)322and R(5)324, as shown by large dashed line326. Similarly, control data block DB M-1308is intended for receivers R(6)328, R(N-3)330and R(N)332, as shown by small dashed line334. Finally, control data block DB M310is intended for receivers R(7)336, R(8)338, R(N-7)340, and R(N-4)342as shown by dot-dashed line344.

Referring again toFIG. 2, a private/public cryptographic key pair may be generated by the network (e.g., network operations center102). The private key is securely stored at the network, while the public key is distributed to all of the recipients (e.g., receivers) that will receive the multicast transmission. Additionally, the network and the recipients may also generate an erasure code generator matrix, such as, for example, a Reed-Solomon erasure code generator matrix R. The systems and methods herein are described with respect to private/public key cryptography and Reed-Solomon erasure codes, as examples. Other cryptography and erasure codes could be used.

The network102(e.g., network operations center) or transmitter site104may generate a hash (h(1)228, h(2)230, h(3)232, h(4)234, h(M-3)236, h(M-2)238, h(M-1)240and h(M)242) for each data block (212,214,216,218,220,222,224and226) within the SMBCM210. For instance, hash h1228is generated based on a data portion243of the control data block DB1212. These hash values, h1, h2. . . h(M) are combined to form a vector H (e.g., h1. . . h(M)), such that the transposed vector H is represented as:
HT=[h1h2. . . hM]
An erasure code generator246may generate erasure codes (e.g., vector C) from the hash values (e.g., vector H) and code generator matrix R by performing the following matrix computation:
C=R×H,
such that the transposed vector C is represented as:
CT=[c1c2. . . cM].
Therefore, each erasure code word produced by the generator246is a combination of hashes for a plurality of control data blocks. The erasure code words in the transposed vector C are appended to the corresponding control data block in every SMBCM. One example element of the transposed vector C is shown for control data block DB1212where erasure code word244is appended to the control data portion243of the control data block DB1212. In this example, the erasure code word244is based on a plurality of the hashes (h1. . . h(M)) associated with a plurality of control data blocks. Similarly, the other elements of the erasure code words in C corresponding to each control data block DB are appended to each control data block DB. Note that each erasure code associated with a particular control data block may be based on one or more hashes for other data blocks. Therefore, if one of those other control data blocks is corrupted (at a receiver), its hash can be reconstructed based on the erasure code associated with other control data blocks.

In addition to the hashes of each control data block, a hash information206is also computed of the hash vector (e.g., the combination of hashes for all blocks). In other words, hash information206is a hash of hashes. The hash206of the hash vector is computed and stored in the PMBCM by the server102or transmitter104. By computing a hash information206of hashes of the control data blocks, each of the control data blocks can be protected without including a separate hash for each control data block in the SMBCM. One hash206(which is a hash of hashes) can be used as a hash for all of the control data blocks. This is done for each of the SMBCMs. The server or transmitter computes the digital signature208of the PMBCM using the private key and sends it with the PMBCM.

In the PMBCM, all of the information, including the hash information206, is secured by the digital signature208. Upon receiving the PMBCM, the recipients verify its digital signature208. If the signature verification fails (either by modification by an attacker or noise on the transmission channel), the PMBCM is discarded.

FIG. 4is a block diagram illustrating reception of an efficiently protected broadcast control message. This diagram illustrates how a receiver may perform operations to verify the accuracy of information in a broadcast control message (e.g., primary and/or secondary messages). For instance, a digital signature405over the whole primary message402may be used to verify the message's accuracy. Note that the digital signature405may be a signature, at least in part, of hash information404, because hash information404may be included in the primary message402. Hash information404is a hash of hashes of SMBCM control data blocks, as described further below. If the signature verification succeeds, the recipients process the PMBCM402. The PMBCM402includes a secondary message identification403and hash information404for one ore more SMBCMs. The recipients acquire an SMBCM406using the information403from the PMBCM402. If the SMBCM is received without any transmission errors, then each hash (408,410,412,414,416,418,420and422) of each control data block is computed by hash engine426and combined to form a hash vector such that the transposed hash vector is HT=[h1h2. . . h(M)]. A hash engine426is shown as hash engines426aand426b. The hash engines426aand426bmay be the same hash engine, and are only shown separately to illustrate the different aspects of the hash engine426.

A hash instance424of the hash vector is computed by the hash engine426b. In other words, hash instance424is a hash of hashes of the received SMBCM control data blocks. Hash instance424is compared to the received hash404from the PMBCM402(e.g., another hash instance). If the hash instance404from the PMBCM402matches the computed hash instance424, then the SMBCM406is assumed to have been received correctly and can be processed. If the hash404from the PMBCM402does not match the computed hash424, then the SMBCM406is assumed to have been modified and may be discarded.

FIG. 5is a block diagram illustrating reception of an efficiently protected broadcast control message in which at least one control data block was received incorrectly. A PMBCM501is received at a receiver. The PMBCM501may be processed as illustrated inFIG. 4. If the SMBCM502is received with errors, erasure code words from the control data blocks received correctly may be used to compute the correct hash for the data block received with error(s). If there are K corrupted control data blocks (i.e., blocks received with errors), then there are M-K error-free control data blocks. For example, control data block DB3504may be received corrupted, as shown inFIG. 5by the “X” on control data block DB3504. The K erasure code words may be taken from any of the M-K control data blocks correctly received. In the example ofFIG. 5, K=1. The K erasure code words are combined with the M-K computed hash values and input into the erasure code decoder506. In the example, one erasure code word CW1530serves as input to a forward error correction (FEC) decoder506because one control data block (i.e., DB3504) was received corrupted. Hash values510,512,514,516,518,520,522for the control data blocks are used together with the code word CW1530to generate the missing hash value for the corrupted control data block DB3504. The FEC506may utilized the code words (e.g., erasure code words) to regenerate the missing K hash values, for example, one hash value, Hash3508corresponding to the corrupted control data block DB3504. The regenerated K hashes508are combined with the computed M-K hashes510,512,514,516,518,520,522to form a hash vector524. The hash of the hash vector524is computed by a hash engine525as a hash instance526and compared to the received hash instance528from the PMBCM501. If the hash528from the PMBCM matches the computed hash526, then the M-K control data blocks from the SMBCM502are assumed to have been received correctly and can be processed. If the hash528from the PMBCM501does not match the computed hash526, then the SMBCM502is assumed to have been modified and is discarded. Consequently, any modification to a transmission that results in an invalid change to the control information (e.g., SMBC blocks) can be detected.

Note that alternative methodologies to those illustrated inFIGS. 4 and 5may be possible. For instance,FIGS. 14 and 16illustrate two alternative examples for protecting broadcast control messages.

Example Transmitter/Encoder Device and Operation thereof

FIG. 6is a block diagram illustrating an example of a broadcast transmitter600capable of efficiently protecting a multi-part broadcast control message. The broadcast transmitter600may be, for example, the transmitter site104shown with respect toFIG. 1. The transmitter600may include a receiver602for receiving signals prepared for wireless broadcasting to mobile receivers. The receiver602may be, for example, the receiver114shown with respect toFIG. 1. For example, the receiver602may receive signals (e.g., control messages) from the network operations center102shown with respect toFIG. 1. The receiver602may be connected to a processor604. The processor604may be included, at least in part, in the transmitter/encoder116shown with respect toFIG. 1. The processor604may include a primary broadcast control message generator609, a secondary broadcast control message generator611, cryptographic engine606and a FEC encoder608. The cryptographic engine606may include a hash engine612for hashing a control message, such as the control data blocks212-226of the SMBCM210shown with respect toFIGS. 2-5. A digital signer614may create a digital signature, such as the digital signature208shown with respect toFIG. 2. The FEC encoder608may be adapted to generate an erasure code (e.g., error correcting code words) for the control message, such as erasure code244for control data block212and the other erasure code words appended to each of the control data blocks shown with respect toFIG. 2. Alternatively, various features or functions of the processor604may be included in the transcoder110, multiplexer112or other module shown with respect toFIG. 1. In other words, various modules or functions of the processor604may be in the network operations center102or may be in the transmitter site104ofFIG. 1. For example, digital signer614may be at the network operations center102while the FEC encoder608may be in the transmitter/encoder116at the transmitter site104.

A modulator/RF front end618may be connected to the processor604. The modulator/transmitter618modulates and/or transmits the primary and secondary control messages, along with other signals, such as digital video data and transmits the signals on antenna620. A storage device616may also be connected to the processor604for storing the control messages and/or data.

One or more components of the broadcast transmitter600may be adapted to protect a multi-part broadcast control message. For instance, the primary broadcast control message generator609may be adapted to generate a primary broadcast control message while the second broadcast control message611may be adapted to generate a second broadcast control message. A hash may be computed over the secondary message SMBCM and appended to the primary message PMBCM. In one example, the hash over the SMBCM may be based on a plurality hashes for control data blocks of the SMBCM. Error correcting codes for the plurality of hashes may be generated and included as part of the SMBCM so that the control data blocks can be verified even if one or more of the control data blocks is corrupted during transmission. A digital signature may be computed over the PMBCM. This approach addresses the processing issue with the third approach noted above. However, each control data block of an SMBCM must contain enough hash information to guarantee that each control data block can be verified independently of the others. For small numbers of M control data blocks, the amount of additional hash information is manageable but can quickly grow as M increases.

FIG. 7is a flow diagram illustrating a method operational on a transmitter or encoder device for generating a secondary broadcast control message. The method may be performed by transmitter/encoder116or Tx Multiplexer112shown with respect toFIG. 1. Error correcting codes may be computed for a secondary broadcast control message702. For instance, an error correcting code for the secondary broadcast control message may be computed based on or more hashes for control data blocks of the secondary broadcast control message. The secondary broadcast control message may be generated that includes a plurality of control data blocks and error correcting code words704. The computed error correcting code words may be appended to the control data blocks of the secondary broadcast control message.FIG. 2illustrates one example of how a secondary broadcast control message210including control data blocks212-226having error correcting code words244.

Information for the secondary broadcast control message may be included in a primary broadcast control message706. For example, information identifying the secondary control message may be included in the primary broadcast control message. A first hash information instance for the secondary broadcast control message may be computed based on a plurality of hashes of control data blocks of the secondary broadcast control message708. The first hash information instance may be included in the primary broadcast control message710. Optionally, the primary broadcast control message may be encoded with a digital signature of the primary broadcast control message including the first hash information instance712. The primary and/or secondary broadcast control message(s) may then be transmitted714.

FIG. 8is a flow diagram illustrating a method operational on a transmitter or encoder device that may be performed in conjunction with the method illustrated inFIG. 7. The method ofFIG. 8provides an example of the step708(FIG. 7) of computing the first hash information instance for the secondary broadcast control message. A first hash is computed from a first control data block of the secondary broadcast control message802. A second hash may be computed from a second control data block of the secondary broadcast control message804. Similarly, additional hashes may be computed for each additional control data block of the secondary broadcast control message806. A hash information instance is computed from the first hash and the second hash (and possibly the additional hashes of the additional control data blocks)808. This hash information instance may be the first hash information instance of step708ofFIG. 7and/or the hash206ofFIG. 2. This process may be repeated for each secondary message such that a hash information instance for each secondary message is included in the primary message.

FIG. 9is a flow diagram illustrating a method that may be used in conjunction with the method described with respect toFIGS. 7 and 8. For instance, the steps ofFIG. 9may be performed as part of steps702and/or704ofFIG. 7. A first error correcting code word is computed based on a first hash and (possibly) one or more additional hashes902. Such first hash may be a hash of a first control data block of the secondary broadcast control message while the one or more additional hashes may be hashes for other control data blocks of the secondary broadcast control message. Similarly, a second error correcting code word may be computed based on a second hash and (possibly) one or more additional hashes904. Such second hash may be a hash of a second control data block of the secondary broadcast control message while the one or more additional hashes may be hashes for other control data blocks of the secondary broadcast control message. The first error correcting code word and the second error correcting code word may be included in the secondary broadcast control message906. For example, the first error correcting code word may be appended to the first control data block and the second error correcting code word may be appended to the second control data block.

As illustrated inFIGS. 2,7,8, and9, the integrity of a secondary broadcast control message may be secured by generating a hash from the hashes of control data blocks of the secondary broadcast control message. This hash is appended to an associated primary broadcast control message. Additionally, error correcting code words may be generated for each of the hashes of the control data blocks, thereby facilitating reconstruction of hashes for a potentially compromised control data block.

According to one feature for securing the integrity of a secondary message (or control data block therein), the digital signature is not distributed across each SMBCM but is localized to the PMBCM. For instance, the digital signature208inFIG. 2is only for the PMBCM202and is not appended with the SMBCM210. This saves significant processing time and power, and also consumes less communication bandwidth.

According to another feature for securing the integrity of a secondary message (or control data block therein), a single-level erasure code is generated where only the error correcting code words of the hash array are appended to the SMBCMs. For instance, as illustrated inFIG. 2, an erasure code244is generated based on the hash array (hashes228-242) and is appended to the control data portion243of the first control data block DB1212. This approach avoids the use of a second level of erasure codes (e.g., based on the digital signature208and/or hashes228-242) thereby reducing processing power and time in addition to avoiding usage of more bandwidth consumption.

Example Receiver/Decoder Device and Operation thereof

FIG. 10is a block diagram of a receiver or decoder device capable of receiving and processing an efficiently protected multi-part broadcast control message. The receiver1000may receive a primary message (PMBCM) and a secondary message (SMBCM) at antenna1002. A demodulator/RF Front End Receiver1004receives and/or demodulates the received signals, including the PMBCM and SMBCMs. The demodulated messages are received by processor1006. A processor1006may include a primary broadcast control message verifier1009, a secondary broadcast control message verifier1011, a cryptographic engine1008and a FEC decoder1010. The cryptographic engine1008may be adapted to perform hashing of control data blocks at a hash engine1012and digital signature verification at a digital signature verifier1014as described above with respect toFIGS. 1-5. The hash engine1012may be separate from the cryptographic engine1008. Also, if convenient, the cryptographic engine1008and FEC decoder1010may be on separate processors, instead of on a single processor1006.

As described above with respect toFIGS. 4 and 5, a PMBCM may be decoded and the digital signature is verified. If the digital signature is incorrect, the PMBCM is discarded. If the digital signature is correct, the PMBCM is interpreted. The SMBCM ID is identified, and the SMBCM is acquired and decoded. The SMBCM hashes are computed by the hash engine1012, as described with respect toFIGS. 4,5,14and15. If a control data block is received corrupted, then the processor1006passes K code words and M-K hashes to FEC decoder1010. The FEC decoder1010may generate the missing hashes K, such as, for example, the hash h3508shown with respect toFIG. 5. A hash instance526of the hashes for control data blocks of a SMBCM is computed by the hash engine1012. The processor1006compares hash instance526to a received hash instance528. Processor1006is connected to storage1016for storing messages and data for use with receiver1000.

The receiver1000may be capable of displaying mobile video signals. For example, the receiver1000may be a MediaFLO-compatible device or other mobile video device. Accordingly, the receiver1000may include a user interface1018. The user interface1018may include a visual display1020and speaker (not shown) for playing video/audio received. The user interface1018may also include a keypad1022for receiving user input such as video channel selection, entering security information, such as a personal identification number (PIN), or other input information. The receiver1000may also include various other devices and modules not shown. For example, receiver1000may include a wireless wide area network transceiver for communicating on a wireless network, such as, for example, a CDMA cellular network or a GSM network.

FIG. 11is a flow diagram illustrating a method operational at a receiver or decoder device for receiving a secondary broadcast control message. For example, the method may be performed by the receiver1000ofFIG. 10. A primary broadcast control message is obtained1102. That is, the primary broadcast control message may be received (e.g., by listening on a particular channel) or may be read from a memory or buffer at the receiver. A digital signature of the primary broadcast control message may be verified. For example, the digital signature may be verified by a digital signature verifier1014(FIG. 10). A secondary broadcast control message may be obtained using the secondary broadcast control message information from the primary broadcast control message1104. In some instances, secondary broadcast control message information for the secondary broadcast control message may be identified in, or obtained from, the primary broadcast control message. A first hash information instance for the secondary broadcast control message is identified in the primary broadcast control message1106. The secondary broadcast control message may then be decoded. A second hash information instance (for the secondary broadcast control message) may be computed based on a plurality of control data blocks of the secondary broadcast control message, where the secondary broadcast control message includes error correcting code words that facilitate computing a correct version of the second hash information even if one or more of the control data blocks have been compromised1108. The first hash information instance is compared to the second hash information instance to determine whether the secondary broadcast control message has been compromised1110.

FIG. 12is a flow diagram illustrating a method that can be carried out in conjunction with the method illustrated with respect toFIG. 11. The method ofFIG. 12may illustrate one example of the step1108(FIG. 11) for computing the second hash information instance for the secondary broadcast control message. A first hash from a first control data block of a received secondary broadcast control message is computed1202. A second hash from a second control data block of the received secondary broadcast control message is also computed1204. Finally, a hash information instance is computed from the first hash and the second hash1206.

FIG. 13is a flow diagram illustrating a method that may be carried out in conjunction with the method illustrated with respect toFIG. 11. For instance, the method ofFIG. 13may be performed if a corrupted secondary message (or control data block therein) is detected by higher level error correction coding (e.g. using message error correcting code136ofFIG. 1). Based on error correction coding it may be determined that a first control data block of the secondary broadcast control message was compromised1302. The determination may be made, for example, by FEC decoder1010, shown with respect toFIG. 10. The compromised control data block may be, for example, DB(3)504, shown with respect toFIG. 5. The receiver may then reconstruct a first hash of the first control data block from the error correcting code words. For instance, an error correcting code word corresponding to a second control data block of the secondary broadcast control message is identified1304. The code word may be CW1530, shown with respect toFIG. 5. As described above with respect toFIG. 5, code word CW1530may be erasure code244. Specifically, the identified error correcting code word corresponds to a control data block that was received uncompromised. A first hash for the first control data block of the secondary broadcast control message is computed based at least in part on the code word corresponding to the second block of the secondary broadcast control message1306. A second hash is computed from the second control data block of the secondary broadcast control message1308. The hashes may be computed by the hash engine1012shown with respect toFIG. 10. The second hash information instance is computed1310from the first hash and the second hash. The hash information instance may be computed by the hash engine1012shown with respect toFIG. 10).

First Alternative Example of Protecting Broadcast Control Message

FIG. 14is a block diagram illustrating a receiver capable of verifying a received secondary broadcast control message by using error correcting code words. This may be an alternative way of protecting and decoding a broadcast control message, and may be a variation of the methodology illustrated inFIGS. 4 and 5. In this example, a secondary broadcast control message1400may include a plurality of control data blocks1440,1442,1444,1446,1448,1450,1452and1454. The plurality of control data blocks1440,1442,1444,1446,1448,1450,1452and1454may have a corresponding set of code words CW1to M1402. Using the fact that C=RH, the equation H=R−1C can be formed.

At the transmitter/encoder, a hash instance is generated from hashes for each control data block of the SMBCM1400. That hash instance may be appended to the associated PMBCM. Additionally, for each hash of a control data block, an error correcting code word may be generated and appended or associated with its corresponding control data block. These error correcting code words are shown as CW1to M1402corresponding to the control data blocks for the SMBCM1400. The error correcting code words may be transmitted as part of the SMBCM1400.

At the receiver/decoder, the integrity of the received SMBCM may be verified using the hash instance from the PMBCM. In one example, the receiver/decoder may compute hashes for the received control data blocks of the SMBCM1400via a first hash engine1425and/or a second hash engine1427. The first hash engine1425may compute the hashes408-422for each control data block1440-1454while the second hash engine1427may compute a Hash Instance A from the computed hashes408-422. In some implementations, the Hash Instance A may be compared1431to a received first hash information from the PMBCM (not shown) associated with the SMBCM1400. If that comparison1431fails, then a subsequent operation may be performed by using error-correcting code words CW1to M1402to attempt to obtain the correct hashes.

Using the error-correcting code words CW1to M1402corresponding to the control data blocks1440-1454for the SMBCM1400, a forward error correction (FEC) decoder1406can compute the hash array H1408,1410,1412,1414,1416,1418,1420and1422. That is, the FEC decoder1406can recompute the hashes1408-1422for the SMBCM1400using the error correcting code words1402. A third hash engine1429then computes a Hash Instance B based on the hashes of the hash array1408-1422. The hash information instance1426can be computed from the hash array H1408-1422.

In one instance, the Hash Instance B may be used as hash information instance1426which is compared1431to a received first hash information from the PMBCM (not shown) associated with the SMBCM1400. This verifies that the error-correcting code words were received correctly. To verify the authenticity of each control data block1440-1454in the SMBCM1400, each received hashes408-422may be compared to its corresponding recomputed hash1408-1422. If a hash408-422does not match its corresponding recomputed hash1408-1422, then the corresponding control data block1440-1454is ignored or rejected. On the other hand, if a hash408-422matches its corresponding recomputed hash1408-1422, then the corresponding control data block1440-1454is accepted or utilized.

In yet other implementations, the Hash Instance A may be compared1460with the Hash Instance B to determine if the control data blocks have been compromised or corrupted. This comparison1460may take place either before or after comparing1431the hash instance1426with the received first hash instance from the PMBCM.

FIG. 15is a flow diagram illustrating a method that may be carried out in conjunction with the method illustrated with respect toFIG. 12and by the system illustrated with respect toFIG. 14. In some examples, this method may be optionally implemented after it has been determined that a received first hash information instance does not match a calculated second hash information instance (Hash Instance A inFIG. 14) for a secondary broadcast control message1502. In other examples, this method may be implemented before and/or concurrent with any determination as to the accuracy of the received control data blocks or their hashes. A third hash, for example, H(1)1408, H(2)1410, H(3)1412or H(4)1414, is computed from a first code word for example, code word CW(M-3), corresponding to the first control data block, for example, DB(M-3), of the secondary broadcast control message1504. A fourth hash is computed from a second code word, for example, CW(M-2), corresponding to the second control data block, for example, DB(M-2), of the secondary broadcast control message1506. The second hash information instance may then be recomputed from the third hash and the fourth hash1508. A comparison is then made to determine whether the first hash information instance and recomputed second hash information instance match1510. If there is no match, it can be concluded that the secondary broadcast message has been compromised1512and the secondary broadcast control message may be discarded1514. Otherwise, if there is a match, the compromised control data block(s) may be identified and/or discarded. This identification of compromised control data blocks may be performed by comparing hashes computed from one or more error correcting code words for each control data block to hashes computed for said control data block. One or more of the remaining control data block(s), those data blocks that are not compromised, can be utilized1518.

Second Alternative Example of Protecting Broadcast Control Message

FIG. 16is a block diagram illustrating a receiver capable of verifying a received secondary broadcast control message by using error correcting code words. This block diagram may illustrate another alternative way of protecting and decoding a secondary broadcast control message. This example is a variation of the methodology illustrated inFIGS. 4 and 5. In the example illustrated inFIG. 16, a first hash engine1623uses the received control data blocks DB(M-3)1602, DB(M-2)1604, DB(M-1)1606and DB(M)1608to compute corresponding hash values H(M-3)1616, H(M-2)1618, H(M-1)1620and H(M)1622. If one or more other control data blocks1601,1603,1605, and/or1607are received with errors, error-correcting code words (e.g., code word1624) for the control data blocks1602,1604,1606, and/or1608can be used by FEC decoder1627to compute the one or more hash values1608,1610,1612, and/or1614for the other control data blocks1601,1603,16(05, and/or1607. That is, in this example, the error-correcting code words (e.g., code word1624) for the control data blocks1602,1604,1606, and/or1608may include information to reconstruct the hashes for one or more other control data blocks1601,1603,1605, and/or1607that may have been received with errors. InFIG. 16, only the error-correcting code word CW(M-3)1624for control data block1602is shown for illustration purposes. However, other code words CW(M-2), CW(M-1) and CW(M) are contemplated and may also be used by FEC decoder1627to compute the hash values1608,1610,1612, and/or1614for the other control data blocks16011,1603,1605, and/or1607.

A second hash engine1625may then compute a hash information instance1626based on the hash values1608,1610,1612,1614,1616,1618,1620and1622. A comparator1629may then compare hash information instance1626to the first hash information528from the PMBCM to authenticate the control data blocks of the SMBCM160).

If the comparison1629fails, a process of elimination can be used to determine which control data block has been modified or has errors. Specifically, if the comparison fails, it can be assumed that at least one of the control data blocks DB(M-3)1602, DB(M-2)1604, DB(M-1)1606and DB(M)1608was received with one or more errors. One of these control data blocks may be selected randomly, or sequentially, or by any other method, and excluded from the calculation of the hash values1608,1610,1612and1614. Thus, for example, the control data block DB(M-3)1602could be selected to not be used by FEC decoder506to compute hash values1608,1610,1612and1614. The hash information instance1626is computed from the hash values computed without using DB(M-3) and just relying on DB(M-2), DB(M-1) and DB(M) as input to FEC decoder1627. If a match is successful then it is determined that DB(M-3)1602was the control data block received in error. Control data block DB(M-3)1602can be discarded and the other control data blocks can be used. Note that, if discarded, the hash1616for DB(M-3)1602may be recomputed based on other error-correcting code words from other control data blocks. Alternatively, if the comparison is not successful, then another control data block DB(M-2)1604can be selected for exclusion in reconstructing hashes. Similar calculations to those above can be performed using only DB(M-3)1602, DB(M-1)1606and DB(M)1608. If a match is successful, then it is determined that DB(M-2)1604was received in error and the other control data blocks can be used. In this way, all data blocks can be checked and any one control data block received in error can be identified, so that it can be discarded while the other control data blocks can be used.

Similarly, if two control data blocks are received in error, two control data blocks would be selected and excluded from the computation of hashes1608,1610,1612and1614. There are more combinations of two control data blocks than combinations of just one control data block, assuming there are more than three control data blocks. Accordingly, as long as there are more than three control data blocks, more computations would be needed to identify two control data blocks received in error than for just one received in error, but it is still possible. Even higher numbers of control data blocks than two can be identified by similar processes of elimination of all the combination until the control data blocks received in error are identified.

FIG. 17(comprisingFIGS. 17A and 17B) is a flow diagram illustrating a method that may be carried out in conjunction with the method illustrated with respect toFIG. 12. This method may be based on the alternative methodology illustrated inFIG. 16. In some examples, this method may be optionally implemented after it has been determined that a received first hash information instance does not match a calculated second hash information instance for a secondary broadcast control message1702. In other examples, this method may be implemented before and/or concurrent with any determination as to the accuracy of the received control data blocks or their hashes.

A first (error-correcting) code word is obtained corresponding to the first control data block and including information for a hash of the second control data block1704. A third hash is computed for the second control data block based on information from the first code word1706. Note that the first code word includes information for one or more hashes of other control data blocks of the secondary broadcast control message. The second hash information instance may be computed or recomputed from the first hash and the third hash1708.

A comparison may then be made to determine whether the first hash information instance and second hash information instance match1710. If there is a match, the compromised control data block may be identified and/or discarded1712. In this example, it may be assumed that the second control data block has been corrupted and may be discarded. This identification of compromised control data blocks may be performed by comparing hashes computed from one or more error correcting code words for each control data block to hashes computed for said control data block. One or more of the remaining control data block(s), those data blocks that are not compromised, can be utilized1714.

If there is no match, the process is repeated with a different error-correcting code word. For example, a second code word may be obtained corresponding to the second control data block and including information for a hash of the first control data block1716. A fourth hash may be computed based on information from the second code word1718. The second hash information instance may be recomputed from the second hash and the fourth hash1720.

A comparison may then be made to determine whether the first hash information instance and second hash information instance match1722. If there is a match, the compromised control data block may be identified and/or discarded1724. In this example, it may be assumed that the first control data block has been corrupted and may be discarded. This identification of compromised control data blocks may be performed by comparing hashes computed from one or more error correcting code words for each control data block to hashes computed for said control data block. One or more of the remaining control data block(s), those data blocks that are not compromised, can be utilized1726. Otherwise, if there is no match, different code words are tried to compute new hashes1728and the second hash information instance is recomputed using the new hashes1730. This process may be repeated multiple times to identify the compromised control data blocks and verify or authenticate the remaining control data blocks.

It should be recognized that, generally, most of the processing described in this disclosure may be implemented in a similar fashion. Any of the circuit(s) or circuit sections may be implemented alone or in combination as part of an integrated circuit with one or more processors. The one or more of the circuits may be implemented on an integrated circuit, an Advanced RISC Machine (ARM) processor, a digital signal processor (DSP), a general purpose processor, etc.

Moreover, a storage medium may represent one or more devices for storing data, including read-only memory (ROM), random access memory (RAM), magnetic disk storage mediums, optical storage mediums, flash memory devices and/or other machine readable mediums for storing information. The term “machine readable medium” includes, but is not limited to portable or fixed storage devices, optical storage devices, wireless channels and various other mediums capable of storing, containing or carrying instruction(s) and/or data.

One or more of the components, steps, and/or functions illustrated in the FIGs. may be rearranged and/or combined into a single component, step, or function or embodied in several components, steps, or functions without affecting the operation of the pseudo-random number generation. Additional elements, components, steps, and/or functions may also be added without departing from the invention. The apparatus, devices, and/or components illustrated in the FIGs may be configured to perform one or more of the methods, features, or steps described in the FIGs. The novel algorithms described herein may be efficiently implemented in software and/or embedded hardware.

The various features of the invention described herein can be implemented in different systems without departing from the invention. For example, some implementations of the invention may be performed with a moving or static communication device (e.g., access terminal) and a plurality of mobile or static base stations (e.g., access points).