CN1163018C - Method and device for generating message authentication code - Google Patents

Abstract

A method for generating a message authentication code (MAC) includes the steps of allocating bits of a message into a larger message according to a pseudo-random number allocation format. The cyclic redundancy check (CRC) bits of the larger message are calculated and used as the MAC of that message. The larger message does not need to be generated. The CRC polynomial of the remainder modulo polynomial xi is calculated, where i is the expected bit position in the "larger message". A bit-by-bit "exclusive OR" operation is performed on the CRC and the calculated remainder to derive a new CRC.

Description

Method and device for generating message authentication code

Background of the Invention

I. Field of Invention

The present invention relates generally to the field of communications, and more particularly to the generation of message authentication codes.

II. Background

A Message Authentication Code (MAC) is a cryptographic derivative that can be appended to a message to verify that the message originated from a party and has not been altered by any other party. This represents the reason why MACs are used in many areas of telecommunications. One example field is wireless communications.

The field of wireless communications has many applications including, for example, cordless telephony, paging, wireless local loop, wireless data applications such as personal digital assistants (PDAs), wireless telephony such as cellular and PCS telephone systems, mobile Internet Protocol (IP) Telephone and satellite communication systems. A particularly important application is wireless telephony for mobile users.

A variety of air interfaces have been developed for wireless communication systems including, for example, Frequency Division Multiple Access (FDMA), Time Division Multiple Access (TDMA), and Code Division Multiple Access (CDMA). In connection with this, various national and international standards have been established including, for example, Advanced Mobile Phone Service (AMPS), Global System for Mobile Communications (GSM) and Interim Standard 95 (IS-95).

An example wireless telephone communication system is a Code Division Multiple Access (CDMA) system. IS-95 standard and its variants IS-95A, ANSI J-STD-008, IS-95B, proposed third generation standard IS-95C and IS-200, proposed high data rate CDMA standard dedicated to data, etc. ( Collectively referred to herein as IS-95) are promulgated by the Telecommunications Industry Association (TIA) and other well-known standards organizations to specify the use of the CDMA air interface in cellular or PCS telephony communication systems. Exemplary wireless communication systems configured substantially in accordance with the use of the IS-95 standard are described in US Patent Nos. 5,103,459 and 4,901,307, assigned to the assignee of the present invention and incorporated herein by reference in their entirety.

In a typical communication, MAC m is the output of a function computed using as input a message M (of length L _M ) and a shared secret key K known only to the originator and receiver of the message. If the chosen function is secure, an active attacker who is able to intercept and potentially modify the sent message can neither discover the key K nor generate a message that has a reasonable probability of being accepted as a valid message by the recipient. If the MAC is long L _m (bits), the attacker will always simply guess a value of m for the desired message with probability 1/2 ^{L m} . Therefore, any guarantee of MAC security is probabilistic in nature. Whether introduced intentionally or randomly, MAC generally does not provide better guarantees against detection errors than this probability. In particular, a single bit error in a message generally has the same chance of matching the MAC attached to the message as any other replacement. Although this probability is small, it is still significant.

A cyclic redundancy check (CRC) is an example of a well-known error detection and correction code (ECC). ECC is used in many applications where data transmissions may be corrupted and when it is desired that the receiver be able to detect the most common corruptions and correct them. CRCs are computationally efficient and have useful error detection properties. If the received message M has errors in any small number of bits, the CRC will ensure detection that errors have occurred and actually indicate (assuming the errors are as small as possible) which bits are erroneous. This enables error correction. The CRC is calculated by considering the bits of the message as coefficients of a polynomial and calculating the remainder when this polynomial is divided by a polynomial P of degree L. Careful selection of the polynomial P gives the desired error detection and correction properties. Although CRCs are good for detecting types of random errors caused during transmission, they are not useful in preventing active attacks of any kind, since an attacker can easily calculate the effect of any modification of the CRC on the message. An attacker can also modify the CRC accordingly. This is true even if secret information is incorporated in the calculation of the CRC but not sent with the message.

There is a need to provide a combined MAC/CRC, ie a code that includes a guarantee that a mismatch between a message and its MAC will detect small random errors that have been detected by the CRC. This code would also be beneficial, while guaranteeing that an active attacker who does not know the secret message K will not be able to discover K or "forge" the message with a probability better than 1/( ^2k -1). (It should be noted that, as is known to those skilled in the art, the extra "-1" in the probability value stems from the fact that the attacker knows that in this case the original MAC will not be used with the message the attacker is modifying mostly the same message, so the attacker will instead randomly choose one of the other possible MACs). Therefore, there is a need for a method of generating a MAC with guaranteed corruption detection properties.

Summary of Invention

The present invention is directed to a method of generating a MAC with guaranteed corruption detection properties. Accordingly, in one aspect of the invention, a method of advantageously generating a message authentication code includes the steps of pseudo-randomly assigning a first plurality of message bits to a second plurality of bits in a key-dependent manner. generating a third plurality of bits of a cyclic redundancy check comprising a second plurality of bits; and sending a first plurality of message bits and a message authentication code comprising a third plurality of bits.

In another aspect of the present invention, a generator configured to advantageously generate a message authentication code includes means for pseudo-randomly assigning the first plurality of message bits to the first plurality of message bits in a key-dependent manner. means for generating a third plurality of bits comprising a cyclic redundancy code check code of the second plurality of bits; and means for transmitting the first plurality of message bits and comprising the first plurality of bits Means for three batches of multi-bit message authentication codes.

In another aspect of the invention, a generator configured to beneficially generate a message authentication code includes configured to pseudo-randomly distribute the first plurality of message bits to the second plurality of message bits in a key-dependent manner. A processor in bits, coupled to the distributor and configured to generate a generator of a third plurality of bits comprising a cyclic redundancy check of the second plurality of bits, and a generator coupled to the generator and configured to A transmitter that sends a first plurality of message bits and a message authentication code comprising a third plurality of bits.

In one embodiment of the invention, a method of advantageously pseudo-randomly allocating bits of a message comprises the steps of computing the residual modulus P of a polynomial ^xi , where i is a predetermined message bit position and P is a cyclic redundancy code checking polynomial; and for each message bit equal to 1 of the message, perform an "exclusive OR" operation of the CRC bit and the calculated remainder bit by bit.

Brief description of attached drawings

Figure 1 is a block diagram of a cellular telephone system.

Figure 2 is a block diagram of a processor and associated storage elements for generating messages and associated message authentication codes (MACs).

Figure 3 is a block diagram of a generator used to generate messages and associated MACs.

4 is a schematic diagram of registers that may be used in the generator of FIG. 3 to use a keyed pseudorandom number (PRN) message bit allocation technique.

FIG. 5 is a schematic diagram of a cyclic redundancy check (CRC) generator that may be used in the generator of FIG. 3 .

FIG. 6 is a flowchart illustrating method steps performed by a generator, such as the generator of FIG. 3, to generate a MAC of a message.

FIG. 7 is a flowchart illustrating method steps performed by a generator, such as that of FIG. 3, to generate a MAC of a message.

Detailed Description of Preferred Embodiments

The example implementations described herein below reside in a wireless telephony communication system configured to use a CDMA air interface. However, those skilled in the art appreciate that the MAC generation method and apparatus embodying features of the invention may be present in any of a variety of communication systems using a wide range of techniques known to those skilled in the art.

As shown in FIG. 1, a CDMA radiotelephone system typically includes a collection of mobile subscriber units 10. As shown in FIG. A number of base stations 12 , a base station controller (BSC) 14 and a mobile switching center (MSC) 16 . The MSC 16 is arranged to be connected to the ordinary public switched telephone network (PSTN) 18. MSC 16 is also configured to interface with BSC 14 . BSC 14 is coupled to base station 12 through a backhaul line. The backhaul line can be configured to support any of several well-known interfaces including, for example, E1/T1, ATM, IP, PPP Frame Relay, HDSL, ADSL or XDSL. It will be appreciated that there may be more than two BSCs 14 in the system. Each base station 12 advantageously includes at least one sector (not shown), each sector containing an omnidirectional antenna or an antenna pointing in a direction away from the base station 12 . Alternatively, each sector may contain two antennas for diversity reception. Each base station 12 may advantageously be designed to support a pool of frequency assignments. The intersection of a sector and a frequency assignment may be referred to as a CDMA channel. The base station 12 may also be referred to as a base transceiver subsystem (BTS) 12 . Alternatively, the industry may collectively refer to the BSC 14 and one or more BTS 12 as "base stations". BTS 12 may also generally refer to "cell site" 12. Or a single sector of a given BTS 12 is also called a cell site. Mobile subscriber unit 10 is typically a cellular or PCS telephone 10 . The system is advantageously configured for use with the IS-95 standard.

During typical operation of the cellular telephone system, base station 12 receives groups of reverse-link signals from groups of mobile units 10 . Mobile unit 10 is conducting a telephone call or other communication. Each reverse link signal received by a given base station 12 is processed within that base station 12 . The resulting data were submitted to BSC14. BSC 14 provides a combination of call resource allocation and mobility management functions, including coordination of soft handoffs between base stations 12 . BSC14 also sends received data to MSC16, and MAC16 provides other routing services and connects with PSTN18. Similarly, PSTN 18 interfaces with MAC 16, which interfaces with BSC 14, which in turn control base station 12 to transmit groups of forward link signals to groups of mobile units 10.

According to an embodiment, as shown in FIG. 2 , the mechanism 100 for generating a message including MAC includes a processor 102 , a software module 104 and a storage medium 106 . Processor 102 is advantageously a microprocessor or a special purpose processor such as digital signal processing (DSP), but may alternatively be any common form of processor, controller, microcontroller or state machine. Processor 102 is coupled to software module 104 , which is advantageously implemented as a RAM memory containing software instructions directing the execution of processor 102 . Software instructions may comprise a software program or a set of microcode. RAM memory 104 may be on-board RAM, or processor 102 and RAM memory 104 may reside in an ASIC. In an alternative embodiment, firmware instructions replace software module 104 . Storage medium 106 is coupled to processor 102 and is advantageously implemented as a combination of RAM memory and any form of ordinary non-volatile memory, such as ROM memory. As described below, storage medium 106 is used to implement a linear feedback shift register (LFSR) to generate the MAC, and to store precomputed tables and instructions. For example, instructions and tables are stored in a ROM memory component and registers are stored in a RAM memory component. Optionally. Storage medium 106 may be implemented as a disk storage or a flash memory accessible by processor 102 . Alternatively, storage medium 106 may be implemented as a register. Organization 100 may reside in any conventional communication device such as mobile subscriber unit 10 or base station 12 in the CDMA wireless telephone system of FIG.

As shown in FIG. 3, in one embodiment, a generator 200 for generating messages and related MACs includes a keyed pseudo-random number (PRN) distributor 202, a cyclic redundancy check code (CRC) generator 204, modulator 206 and transmitter 208 . The message bits of the message M are provided to the keyed PRM distributor 202 . As detailed below, keyed PRN allocator 202 pseudo-randomly distributes the message bits into bit sequences in a key-dependent manner. The bit sequence comprising the assigned message bits is provided to CRC generator 204 . The CRC generator 204 calculates the CRC of the bit sequence including the assigned bits according to any common CRC calculation method known to those skilled in the art.

CRC generator 204 generates CRC bits which will be used as a MAC for these message bits. The MAC bits and message bits are provided to modulator 206 . Modulator 206 modulates the received bits for transmission on a communication channel. Modulation schemes vary with the communication system and the type of communication channel being used. In one embodiment, the modulation scheme is a CDMA scheme and the communication system is the wireless telephone system of FIG. 1 . Modulator 206 provides the modulated message and MAC signal to transmitter 208 . A transmitter sends the modulated message and MAC signal over a communication channel.

According to the embodiment described with reference to FIG. 3, the CRC of a larger "message" (sequence of bits) is calculated and sent as a MAC, where the individual bits of the original message, M, have been encoded in a cryptographically dependent manner not predicted by the attacker. keys are assigned. Thus, small random errors can be detected and corrected by usual CRC mechanisms, while active attacks (ie, intentional modification of an otherwise legitimate message) have only a limited probability of success.

Beneficially, the method by which the bits of the original message M are allocated by the larger message varies from message to message. Mutations in the distribution method prevent the attacker from collecting messages and gradually increase the probability of a successful attack. Since a MAC must guarantee detection of small errors, if two similar messages (with different MACs by definition) are sent, the MAC of another message that is similar but different to the two similar messages must also be different. so that the attacker can only randomly choose from 2 ^L -2 possible MACs etc. Advantageously, information denoted as a "salt" S is used to link information related to a particular message, such as the moment the message was sent, or a sequence number, to the manner in which the bits of the message are allocated. This is analogous to the fact that a stream cipher should never produce the same stream of output for two different messages or two different segments of a single message.

Accordingly, the bits from the original message M must be distributed into the larger "message" in a way that is unpredictable to the attacker and does not help the attacker discover information about the shared key K. Thus, according to the embodiment described with reference to FIG. 3, evenly distributed PRNs are generated to control the distribution of message bits within a larger message. The evenly distributed PRN is advantageously derived from the common key K and salt S in a manner that is unpredictable to the attacker.

In an exemplary embodiment, the output of a stream cipher known as SDBER, the SOBER stream cipher filed on February 8, 1999 under application number 09/246366 titled Use to Generate Encrypted Stream Ciphers, is used as the source of the PRN. Methods and apparatus are described in the US application. This application is assigned to the assignee of the present invention. A stream cipher is a pseudo-randomly generated bit stream, which is subjected to an "exclusive OR" operation (XDR) with each bit of the message to be sent bit by bit to generate an encrypted message. When receiving the encrypted message, use the same First-class ciphers "exclusive-or" it to produce the original message. In alternative embodiments, other forms of PRN generators may replace the stream cipher. In particular, a PRN generator that provides less security than a stream cipher can be used in place of the stream cipher.

In one embodiment, as shown in Figure 4, the bits of message M 300 are allocated under the control of a keyed PRN generator (not shown) by: Bits are placed initially and sequentially, skipping an unpredictable number of positions in the larger message 302 between two bits. When, or if, the end of the larger message 302 is encountered, the allocation position restarts at the beginning of the larger message 302 . The maximum number of positions skipped between bits of the larger message 302 is advantageously determined such that the allocated positions do not completely wrap around, ie so that the starting position in the larger message 302 is not reached or passed. This ensures that no two bits in the message M 300 are assigned to the same position in the larger message 302, and if two bits are assigned to the same position in the larger message 302, simultaneous changes in the two bits will cancel each other out and will not be detected, thereby failing to achieve the goal. Considering the worst case where each gap between allocated bits is a maximum length, the maximum gap length must be limited. However, the average gap length is only half of the maximum gap length. Therefore, on average, message bits are only allocated within half of the larger message. This allocation technique advantageously provides ample security and relative ease of implementation.

In another embodiment, the message bits 300 are allocated by dividing the larger message 302 into approximately equal sized blocks, starting with a random offset and wrapping around, placing a bit in each block at a random position Inside. A desirable property of this distribution technique is that the bits are well distributed throughout the larger message.

The bits of the larger message 302 are provided to a CRC generator 304 which calculates a CRC of the received bits. The CRC bits 306 are used as the MAC 306 of the message M 300. It should be noted that, as shown in conjunction with other embodiments described below with reference to FIG. 6, it is not necessary to actually generate a larger message 302 to achieve the desired effect.

In an example embodiment, the length L _m of the CRC/MAC is 16 bits. The largest message to which the error detection guarantee applies is ²¹⁶ bits including the CRC itself. (If (1-x) times the original polynomial is used as the CRC generator, the maximum message length will be 2 ¹⁵ -1 bits). The length L _m of the input message M 300 is advantageously kept much smaller than 2 ¹⁵ -16 bits. According to the second embodiment described above, the length _Lm of the input message M 300 is advantageously limited to less than half of ^215-16 bits if the larger message 302 is divided into roughly equal sized chunks. According to the first embodiment described above, if bit positions are skipped within the larger message 302, the length _Lm of the incoming message M 300 is advantageously limited to be smaller than a quarter of ^215-16 bits.

After placing the first bit of message M 300, the remaining L _m -1 bits are placed in the remaining 2 ¹⁵ -17 positions, if the length L _m of the input message M is 1520 bits, the maximum allocation interval or block The size of will be the largest integer less than 32751/1519 or 21 bits. However, a PRN generator can be viewed as generating a stream of bits. Accordingly, using a number that is a power of 2 rather than using 21 bits may advantageously be more efficient. If a power of 2 is used as the maximum allocation interval or block size. A random number in the range of 0 to 15 can be generated by taking the output 4 bits from the PRN generator. These random numbers are then advantageously adjusted to be in the range of 5-20. Those skilled in the art will understand that the average spacing between bits or the block size must be at least 2. Therefore, the optimal value for the interval or block size is a power of 2 between 2 ² and 2 ⁴ . The placement of each bit of message M 300 thus requires two to four bits of the PRN output.

As described below, it may be beneficial to spread the bits further apart, even if the uncertainty in the position of the bits is limited to accepting fewer PRN generator outputs. Whether fixed or variable, a minimum extension size or a minimum block size can be used.

In another embodiment, message bits are assigned by using a keyed permutation function, such as a block cipher, to derive new bit positions from original bit positions. In one embodiment, a block cipher with a block size of 14 bits is used in conjunction with random offset positions within the larger message 302 . It should be noted that the need to use a different permutation for each message requires that the block cipher use a different key for each message 300 . Although this is theoretically possible, in practice it is inefficient.

In one embodiment, as shown in FIG. 5, the CRC generator 400 is implemented as a register, which includes 16 one-bit storage elements 402a-g (for simplicity, only the storage element 402 is shown in the figure), three modulus - 2 adders 404, 406, 408 and three switches 410, 412, 414. In an alternative embodiment, as described above with reference to FIG. 2, the CRC generator is implemented with a microprocessor that executes a set of software instructions, advantageously contained in RAM memory, and accesses a look-up table (LUT). The look-up table is advantageously contained in ROM memory or flash memory.

In CRC generator 400, the input message bits are provided to switch 410, which is set to receive either these input message bits or a digital value of one. Switch 412 is set to receive either a digital value of 0 or a value from modulo-2 adder 408 . Switch 414 is set to receive either a value from switch 410 or a value from switch 412 and modulo-2 adder 408, from which the output CRC is taken. The modulo-2 adder 404 is located between the fifth one bit storage element 402c and the sixth one bit storage element 402d. The modulus-2 adder 406 is located between the twelfth one-bit storage element 402e and the thirteenth one-bit storage element 402f. Modulo-2 adder 408 is located after the sixteenth bit storage element 402h and is configured to receive a value from switch 410 . The generator polynomial g(x) of the CRC is equal to x ¹⁶ +x ¹² +x ⁵ +1, defined by the layout of the modulo-2 adders 404 , 406 , 408 .

In operation, the switches 410, 412, 414 are initially set in the "up" position (as shown in the figures). The register is timed k times, where k is defined as the length of the input message plus 8 bits. The register is a shift register such that with each clock cycle the bits are each shifted to the right by one storage element (as shown in the figure). The switches 410, 412, 414 are then set to the "down" position (as shown in the figures). The register is then timed to append sixteen times. Sixteen additional output bits contain the CRC field of the message, and the bits are sent in the order in which they appear on the output of the CRC generator 400 .

The input message bits constitute a "larger message" whose CRC field is used as the MAC of message M. The MAC then advantageously includes the inherent security benefits of the CRC. Since the computed MAC is actually a CRC, the guarantees about error detection and correction that apply to the CRC also apply to the MAC, except for the guarantees that apply to "burst errors". The burst error guarantee is violated because consecutive bits are separated during computation and no longer form a "burst".

There are basically two types of attacks against MACs. The first kind of attack against MAC is to steal business. An attacker tries to generate a message with a valid MAC after observing other valid messages. Alternatively, the attacker attempts to derive the key K, allowing the attacker to generate forged messages at will. The second type of attack against MAC selects messages. An attacker tries to craft a special message and somehow design the system to compute an effective MAC, hoping to recover the key K.

An attacker wishing to make a change of only one bit to a message with a valid MAC would then need to be able to compute the corresponding change to the CRC; this in turn requires being able to predict the position of that bit in the extended message. Since there are only 2L ^-1 possible positions for this bit, the attacker can do only slightly better than guessing the MAC.

One possible attack against any kind of MAC is the so-called chosen-plaintext attack. In this type of attack, the attacker can somehow arrange for the message sent to be accompanied by a valid MAC so that the message has some content chosen by the attacker. For example, an attacker could send an e-mail to a recipient, and the e-mail is eventually sent over the sending channel with a valid MAC computed and attached, the attacker could craft a message consisting of a single "1" bit followed by all "0" bits. By observing the calculated CRC, the attacker can deduce the starting position and some output to the PRN generator. This is disadvantageous because it leads to a method of predicting future outputs. Accordingly, in one embodiment, the other one bit of the larger message is set to one. The other one bit is chosen at a random position.

The attacker optionally sends a message containing all zeros. The observed CRC gives _Lm bits of the output of the attacker's PRN generator, which must be secure enough to prevent recovery of the key information K, given this revelation.

If an attacker attempts to change bits of the message in addition to predicting where these bits start, the attacker must also determine the dispersion of these bits. This makes the probability of success less than changing only one bit.

There is also a modification attack available. If an attacker can make a change that will spread into a pattern that is a multiple of the CRC polynomial, there will be no effect on the computed MAC. This effectively counteracts the unpredictability of where these bits start. If it is advantageous to use a small number of stream cipher bits, it is beneficial to choose to expand these bits polynomially taking into account that particular CRC, so that this type of attack is impossible for small multiples of the polynomial and statistically significant for large multiples of the polynomial It is difficult.

In one embodiment, a CRC calculation is performed on the "larger message", generating a MAC of the incoming message M, without actually generating a larger message. For each bit of the input message M to be allocated in this imaginary "larger message", the modulo P of the remainder of the polynomial ^Xi , i being the predetermined position of the message bit in the larger message, must be calculated. Because CRCs are linear, if that particular bit of the message is a 1, the remainder can be calculated using polynomial addition, ie, an "exclusive OR" (XOR) operation, to the existing CRC. The CRC of an all-zero message is zero, so by legally applying the XOR polynomial addition technique to each bit in the input message M, and also by performing only the L _m calculation, the CRC can be calculated without generating a larger message. Similarly, an initial seed of the input message with a non-zero bit is equivalent to choosing a random start CRC for the computation.

^Xi mod P, where i is in the range 0 to 32767 (assuming Lm is 16), can be calculated in a number of ways. In one embodiment, a pair of look-up tables (LUTs) are used. It should be noted that one LUT giving a CRC for each possible value of i in the above equation would suffice, but requires ²¹⁶ 16-bit entries. Instead, i is beneficially expressed in the form 256hi+lo, where hi and lo are the high-order 8 bits and low-order 8 bits of i, respectively. Precomputing the two LUTs seems to give the results of the CRC calculations X ^256hi mod P and X ^lo mod P respectively, such that each term in the first LUT is XORed with the corresponding term in the second LUT The operation is equivalent to calculating CRC. Accordingly, two LUTs are required, each with 256 16-bit entries, and two table lookups are performed for every non-zero bit of the input message M to calculate the CRC.

It is also beneficial in software implementations to note that when these bits are allocated by larger messages, hi does not vary rapidly so that repeated references to the same value cancel each other out. Whether each value of hi has been used an odd number of times is the most practical effect.

In one embodiment, the PRN generates the MAC of the incoming message M as the CRC of an imaginary "larger message" without generating the larger message, following the steps of the algorithm shown in the flowchart of FIG. 6 . In this embodiment, Lm is 16 bits and Lm is 1520 bits. The CRC polynomial P is a 16-bit CRC-CCITT polynomial P(X)=X ¹⁶ +X ¹² +X ⁵ +1. Those skilled in the art will appreciate that the specific LUT used to look up the CRC value can be easily calculated. The notation R _n , where n is an integer, is used hereinafter to indicate that the next n bits of the output of the PRN generator (not shown) should be taken. In this embodiment, a fixed minimum interval of 5 bits is used, using 3 bits of the PRN output, resulting in an evenly distributed bit interval of 5 to 12 bits. The variable C represents the accumulator of the final output MAC. The variable K indicates the position of the next bit to be placed in the "larger message". The variable i represents the bit position in the input message M.

In step 500, the generator sets C equal to _R16 , which is equivalent to selecting a random bit position that will be set to 1. The next 16 bits of the generator output will form the CRC. The generator then proceeds to step 502. In step 502 the generator sets K equal to R ₁₅ modulo 32751, which is actually the position of the first bit of the incoming message M to be assigned. The generator then proceeds to step 504 . In step 504 the generator sets i equal to zero. Generation then proceeds to step 506 .

In step 506, the generator determines whether bit M[i] (currently assigned input message bit) is set to one. If bit M[i] is not set to 1, the generator proceeds to step 508 . On the other hand, if bit M[i] is set to 1, the generator proceeds to step 510 . In step 510, the generator computes ^XK modulo P and performs a bitwise XOR operation on C and ^XK modulo P according to the polynomial addition technique described above. The new value of C is set equal to the bits resulting from the XOR calculation. The generator then proceeds to step 508 .

In step 508, the generator calculates the sum of K, 5, _R3 (the next three bits of the generator output), modulo 32751. The result is set equal to K, such that K is updated to be the position to which the next bit of the input message will be assigned. This calculation is performed in step 510 after the current bit M[i] is allocated. The generator then proceeds to step 512 . In step 512 the generator increments i. The generator then proceeds to step 514 . In step 514 the generator determines if i is greater than 1519. If i is not greater than 1519, the generator returns to step 506 to process the next input message bit M[i]. On the other hand, if i is greater than 1519, the generator proceeds to step 516. In step 516 the generator returns C's MAC for the incoming message.

In an alternative embodiment, the calculation performed in step 508 is the sum of K, 10, _R4 (the next 4 bits of the generator output), x65521. The result is again set equal to K. According to this embodiment, the generator sets K equal to _R16 modulo 65521 in step 502 . An original polynomial that can be used according to this embodiment is x ¹⁶ +x ¹⁴ +x ¹² +x ⁷ +x ⁶ +x ⁵ +x ² +x+1.

In another embodiment, the PRN generator follows the steps of the algorithm shown in the flowchart of FIG. 7 to generate the MAC of the incoming message M as the CRC of an imaginary "larger message" without generating the larger message. In this embodiment, L _m is 16 bits and L _M is 1520 bits. The CRC polynomial P is a 16-bit CRC-CCITT polynomial P(x)=x ¹⁶ +x ¹² +x ⁵ +1. Those skilled in the art will appreciate that the specific LUT used to look up the CRC value can be easily calculated. The notation R _n , n being an integer, is used hereinafter to indicate that the next n bits of the output of the PRN generator (not shown) should be taken. In this embodiment, a fixed minimum interval of 5 bits is used, using 3 bits of the PRN output, resulting in an evenly distributed bit interval of 5 to 12 bits. The variable C represents the accumulator of the final output MAC. The variable K indicates the position of the next bit to be placed in the "larger message". The variable i represents the bit position in the input message M.

In step 600, the generator sets C equal to _R16 , which is equivalent to selecting a random bit position that will be set to 1. The next 16 bits of the generator output will form the CRC. The generator then proceeds to step 602. In step 602 the generator sets K equal to R ₁₅ modulo 32751, which is actually the position of the first bit of the incoming message M to be assigned. The generator then proceeds to step 604. In step 504 the generator sets i equal to zero. Generate then proceeds to step 606.

In step 606, the generator determines whether bit M[i] (currently assigned input message bit) is set to one. If bit M[i] is not set to 1, the generator proceeds to step 608 . On the other hand, if the bit M[i] is set to 1, the generator proceeds to step 610 . In step 610, the generator computes X ^K modulo P and performs a bitwise XOR operation on C and x ^K modulo P according to the polynomial addition technique described above. The new value of C is set equal to the resulting bits of the XOR calculation. The generator then proceeds to step 608.

In step 608 the generator increments i by 1. The generator then proceeds to step 612 . In step 612 the generator determines if i is greater than 1519. If i is not greater than 1519, the generator proceeds to step 614. On the other hand, if i is greater than 1519, the generator proceeds to step 616. In step 616 the generator returns the value of C as the MAC of the incoming message. In step 614 the generator calculates the sum of K, 5, R ₃ (the next three bits of the generator output), modulo 32751. The result is set equal to K. K is thus updated to be the assigned position of the next bit of the input message. This calculation of the new bit position is performed when a new bit is to be allocated. After performing the computation of step 614, the generator returns to step 606 to process the next input message bit M[i].

In an alternative embodiment, the calculation performed in step 608 is the sum of K, 10, R ₄ (the next 4 bits of the generator output), and 65521. The result is again set equal to K. According to this embodiment, the generator sets K equal to _R16 modulo 65521 in step 602 . An original polynomial that can be used according to this embodiment is x ¹⁶ +x ¹⁴ +x ¹² +x ⁷ +x ⁶ +x ⁵ +x ² +x+1.

Thus, a novel method and apparatus for generating a MAC has been described. Those skilled in the art will appreciate that the various illustrative logic blocks and algorithm steps disclosed herein and described in connection with the embodiments may be implemented with digital signal processors (DSPs), application specific integrated circuits (ASICs) discrete gate or transistor logic, such as registers and A FIFO is implemented or executed by a discrete hardware component, a processor executing a set of firmware instructions, or any generic programmable software module and a processor. The processor may advantageously be a microprocessor, but alternatively, the processor may be any conventional processor, controller, microcontroller or state machine. A software module may reside in RAM memory, flash memory, registers, or any other form of writable storage medium indicated in the industry. Those skilled in the art will also recognize that throughout the above description referenced data, instructions, commands, information, signals, bits, symbols and terminals are advantageously referred to in terms of voltage, current, electromagnetic waves, magnetic fields or particles, optical fields or particles or any combination of them.

The preferred embodiment of the invention has thus been shown and described. However, it will be apparent to those of ordinary skill in the art that many changes can be made in the embodiments disclosed herein without departing from the spirit or scope of the invention. Accordingly, the invention is not to be restricted except in light of the following claims.

Claims (29)

1. A method for generating a message authentication code, characterized in that it comprises the following steps: pseudo-randomly assigning the first plurality of message bits to the second plurality of bits in a key-dependent manner; generating a third plurality of bits comprising a cyclic redundancy check of said second plurality of bits; and Sending said first set of message bits and a message authentication code comprising said third set of bits. 2. The method of claim 1, wherein said generating step is performed using a microprocessor, a look-up table accessible by the microprocessor, and a set of software instructions executable by the microprocessor. 3. The method of claim 1, wherein said generating step is performed using a shift register. 4. The method of claim 1, wherein said pseudo-randomly assigning step comprises the steps of: placing a first position of the first plurality of bits in an offset bit position of the second plurality of bits; and An unpredictable number of bit positions in the second plurality of bits are skipped from the offset bit position. 5. The method of claim 4, further comprising the step of placing a next bit of said first plurality of bits into a starting bit position of said second plurality of bits. 6. The method of claim 4, further comprising the step of determining a maximum number of bit positions skipped in the step of skipping such that a starting bit position of the second plurality of bits is not reached or passed. 7. A method as claimed in claim 4, characterized in that the number of bit positions skipped in the step of skipping is determined such that the allocated positions do not completely wrap around. 8. The method of claim 1, wherein the step of pseudo-randomly assigning comprises the steps of: dividing the second plurality of bits into blocks of approximately uniform block size; and Place the first plurality of bits in random bit positions within each block, one bit in each block. 9. The method of claim 8, wherein the uniform block size is 2 to the power of 2 to 4. 10. The method of claim 1, wherein the step of pseudo-randomly assigning comprises using a keyed permutation function to derive new bit position step. 11. The method of claim 1, wherein the step of pseudo-randomly assigning comprises the following steps; computing the remainder modulo P of polynomial ^x , where i is an expected bit position in the second plurality of bits and P is a cyclic redundancy check polynomial derived from the third plurality of bits; and For each bit equal to 1 of the first plurality of bits, an "exclusive OR" operation of the third plurality of bits and the calculated remainder is performed bit by bit. 12. A generator configured to generate a message authentication code, comprising: means for pseudo-randomly assigning a first set of message bits to a second set of bits in a key-dependent manner; means for generating a third plurality of bits comprising a cyclic redundancy check of the second plurality of bits; and Means for transmitting a first set of message bits and a message authentication code comprising a third set of bits. 13. A generator as claimed in claim 12, wherein said generating means comprises a microprocessor, a look-up table accessible by the microprocessor and a set of software instructions executable by the microprocessor. 14. A generator as claimed in claim 12, wherein said generating means comprises a shift register. 15. The generator of claim 12, wherein the means for pseudo-randomly assigning comprises: means for placing a first one of the first plurality of bits into an offset bit position in the second plurality of bits; and means for skipping an unpredictable number of bit positions in the second plurality of bits from the offset bit position. 16. The generator of claim 15, further comprising means for placing the next bit of the first plurality of bits in the starting bit position of the third plurality of bits. 17. A generator as claimed in claim 15, further comprising means for determining a maximum number of bit positions to skip so as not to reach or pass through the initial bit positions of the second plurality of bits. 18. A generator as claimed in claim 15, characterized in that the number of bit positions skipped is determined such that the allocated positions do not wrap around completely. 19. The generator of claim 12, wherein the means for pseudo-randomly assigning comprises: means for dividing the second plurality of bits into blocks of approximately uniform block size; and A means for placing a first plurality of bits into random bit positions within each block, one bit per block. 20. A generator as claimed in claim 19, characterized in that the uniform block size is 2 to the power of 2 to 4. 21. The generator of claim 12, wherein the means for pseudo-randomly distributing comprises using a keyed permutation function from a start bit of the first plurality of bits in the second plurality of bits to Position means for deriving new bit positions. 22. The generator of claim 12, wherein the means for pseudo-randomly assigning comprises: means for computing the remainder modulo P of a polynomial ^x , where i is an expected bit position in a second plurality of bits and P is a cyclic redundancy code derived from a third plurality of bits polynomial; and Means for performing, bit by bit, the exclusive OR operation of the third plurality of bits and the calculated remainder for each bit equal to 1 of the first plurality of bits. 23. A generator configured to generate a message authentication code, characterized in that it comprises: a processor configured to pseudo-randomly assign the first set of message bits to the second set of plurality of bits in a key-dependent manner; a generator coupled to the distributor and configured to generate a third plurality of bits comprising a cyclic redundancy check of the second plurality of bits; and A transmitter coupled to the generator and configured to transmit the first set of message bits and a message authentication code comprising a third set of multiple bits. 24. The generator of claim 23, comprising a look-up table accessible by the microprocessor, and a set of software instructions stored in a memory element and executable by the microprocessor. 25. The generator of claim 23, wherein the generator comprises a shift register. 26. The generator of claim 23, wherein the processor is further configured to place a first bit of the first plurality of bits in an offset bit position in the second plurality of bits and to The shifted position skips an unpredictable number of bit positions in the second plurality of bits. 27. The generator of claim 26, wherein the processor is further configured to place a next position of the first plurality of bits in a starting bit position of the second plurality of bits. 28. The generator of claim 23, wherein the processor is further configured to divide the second plurality of bits into blocks of approximately uniform block size and place the first plurality of bits within each block. In random bit positions, one bit is placed in each block. 29. The generator of claim 23, wherein the processor comprises a calculator and a polynomial adder, the calculator being configured to calculate the remainder modulo P of the polynomial ^x i where i is in the second an expected bit position in the first plurality of bits and P is a cyclic redundancy check polynomial derived from the third plurality of bits, and the polynomial adder is configured to equal 1 for each of the first plurality of bits The ones bit executes the "exclusive OR" operation of the third group of bits and the calculated remainder, bit by bit.

Images