Stream cipher having a shuffle network combiner function

A stream cipher is provided with one or more data bit generators to generate a first, second and third set of data bits. The stream cipher is further provided with a combiner function having a network of shuffle units to combine the third set of data bits, using the first and second sets of data bits as first input data bits and control signals respectively of the network of shuffle units. In one embodiment, the shuffle units are binary shuffle units and they are serially coupled to one another.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to the field of cryptography. More specifically, the present invention relates to the robustness of stream ciphers.

2. Background Information

Crytographic ciphers can be broadly divided into block ciphers and stream ciphers. Block ciphers cipher a block of plain text into ciphered text by applying multiple successive rounds of transformation to the plain text, using a cipher key. An example of a block cipher is the well known DES cipher. Stream ciphers cipher a stream of plain data into ciphered data by combining the stream of plain data with a pseudo random sequence dynamically generated using a cipher key. An example of a stream cipher is the well known XPF/KPD cipher.

Most stream ciphers employ one or more linear feedback shift registers (LFSR). In various applications, it is desirable to employ multiple LFSRs to increase the robustness of a stream cipher. However, employment of multiple LFSRs requires employment of a combiner function to recombine the multiple data bits output by the LFSRS. Most combiner functions known in the art are inefficient in their real estate requirement for hardware implementations. Thus, a robust stream cipher with a more efficient combiner function is desired.

SUMMARY OF THE INVENTION

A stream cipher is provided with one or more data bit generators to generate a first, second and third set of data bits. The stream cipher is further provided with a combiner function having a network of shuffle units to combine the third set of data bits, using the first and second sets of data bits as input data bits and control signals respectively of the network of shuffle units.

DETAILED DESCRIPTION OF THE INVENTION

In the following description, various aspects of the present invention will be described, and various details will be set forth in order to provide a thorough understanding of the present invention. However, it will be apparent to those skilled in the art that the present invention may be practiced with only some or all aspects of the present invention, and the present invention may be practiced without the specific details. In other instances, well known features are omitted or simplified in order not to obscure the present invention.

Various operations will be described as multiple discrete steps performed in turn in a manner that is most helpful in understanding the present invention. However, the order of description should not be construed as to imply that these operations are necessarily performed in the order they are presented, or even order dependent. Lastly, repeated usage of the phrase “in one embodiment” does not necessarily refer to the same embodiment, although it may.

Referring now toFIG. 1, wherein a block diagram illustrating the combined block/stream cipher of the present invention, in accordance with one embodiment, is shown. As illustrated, combined block/stream cipher110includes block key section502, data section504, stream key section506, and mapping section508, coupled to one another. Block key section502and data section504are employed in both the block mode as well as the stream mode of operation, whereas stream key section506and mapping section508are employed only in the stream mode of operation.

Briefly, in block mode, block key section502is provided with a block cipher key, such as an authentication key Km or a session key Ks of a video content protection application; whereas data section504is provided with the plain text, such as a basis random number An or a derived random number Mi-1of a video content protection application. “Rekeying enable” signal is set to a “disabled” state, operatively de-coupling block key section502from stream key section506during the block mode of operation.

A video content protection. application that uses Km, Kx, An and Mi is described in copending U.S. patent application Ser. Nos. 09/385,590 and 09/385,592, filed contemporaneously, both entitled “Digital Video Content Transmission Ciphering And Decipher Method an Apparatus” and “Digital Video Content Transmission Ciphering And Deciphering Method And Apparatus” having common assignee and inventorship with the present application.

During each clock cycle, the block cipher key as well as the plain text are transformed. The block cipher key is independently transformed, whereas transformation of the plain text is dependent on the transformation being performed on the block cipher key. After a desired number of clock cycles, the provided plain text is transformed into ciphered text. For the video content protection method disclosed in above mentioned co-pending applications, when block key section502is provided with Km and data section504is provided with the An, ciphered An is read out and used as the session key Ks. When block key section502is provided with Ks and data section504is provided with the Mi-1, ciphered Mi-1is read out and used as the frame key Ki.

To decipher the ciphered plain text, block key section502and data section504are used in like manner as described above to generate the intermediate “keys”, which are stored away (in storage locations not shown). The stored intermediate “keys” are then applied to the ciphered text in reversed order, resulting in the deciphering of the ciphered text back into the original plain text. Another approach to deciphering the ciphered text will be described after block key section502and data section504have been further described in accordance with one embodiment each, referencingFIGS. 2-3.

In stream mode, stream key section506is provided with a stream cipher key, such as a session key Ks or a frame key Ki of a video content protection application. Block key section502and data section504are provided with random numbers, such as a session/frame keys Ks/Ki and a derived random numbers Mi-1of a video content protection application. “Rekeying enable” signal is set to an “enabled” state, operatively coupling block key section502to stream key section506. Periodically, at predetermined intervals, such as the horizontal blanking intervals of a video frame, stream key section506is used to generate one or more data bits to dynamically modify the then current state of the random number stored in block data section502. During each clock cycle, in between the predetermined intervals, both random numbers stored in block key section502and data section504are transformed. The random number provided to block key section502is independently transformed, whereas transformation of the random number provided to data section504is dependent on the transformation being performed in block key section502. Mapping block506retrieves a subset each, of the newly transformed states of the two random numbers, and reduces them to generate one bit of the pseudo random bit sequence. Thus, in a desired number of clock cycles, a pseudo random bit sequence of a desired length is generated.

For the illustrated embodiment, by virtue of the employment of the “rekeying enable” signal, stream key section506may be left operating even during the block mode, as its outputs are effectively discarded by the “rekeying enable” signal (set in a “disabled” state).

FIG. 2illustrates the block key section ofFIG. 1in further detail, in accordance with one embodiment. As illustrated, block key section502includes registers602a-602c, substitution boxes604, and linear transformation unit606. In block mode, registers602a-602care collectively initialized to a block cipher key, e.g. the earlier mentioned authentication key Km or session key Ks. In stream mode, registers602a-602care collectively initialized to a random number, e.g. the earlier mentioned session key Ks or frame key Ki. Each round, substitution boxes604and linear transformation unit606modify the content of registers602a-602c. More specifically, substitution boxes604receive the content of register602a, modify it, and then store the substituted content into register602c. Similarly, linear transformation unit606receives the content of registers602band602c, linearly transforms them, and then correspondingly stores the linearly transformed content into registers602aand602b.

Substitution boxes604and linear transformation unit606may be implemented in a variety of ways in accordance with well known cryptographic principles. One specific implementation is given in more detail below after the description of FIG.3.

FIG. 3illustrates the block data section ofFIG. 1in further detail, in accordance with one embodiment. For the illustrated embodiment, data section504is similarly constituted as block key section502, except linear transformation unit706also takes into consideration the content of register602b, when transforming the contents of registers702b-702c. In block mode, registers702a-702care collectively initialized with the target plain text, e.g. earlier described random number An or derived random number Mi-1. In stream mode, registers702a-702care collectively initialized with a random number. Each round, substitution boxes704and linear transformation unit706modify the content of registers702a-702cas described earlier for block key section502except for the differences noted above.

Again, substitution boxes604and linear transformation unit606may be implemented in a variety of ways in accordance with well known cryptographic principles.

In one implementation for the above described embodiment, each register602a,602b,602c,702a,702b,702cis 28-bit wide. [Whenever registers602a-602cor702a-702cbcollectively initialized with a key value or random number less than 84 bits, the less than 84-bit number is initialized to the lower order bit positions with the higher order bit positions zero filled.] Additionally, each set of substitution boxes604or704are constituted with seven 4 input by 4 output substitution boxes. Each linear transformation unit606or706produces56output values by combining outputs from eight diffusion networks (each producing seven outputs). More specifically, the operation of substitution boxes604/704and linear transformation unit6061706are specified by the four tables to follow. For substitution boxes604/704, the Ith input to box J is bit1*7+J of register602a/702a, and output I of box J goes to bit1*7+j of register602c/702c. [Bit0is the least significant bit.] For each diffusion network (linear transformation unit606as well as706), the inputs are generally labeled10-16and the outputs are labeled O0-O6. The extra inputs for each diffusion network of the linear transformation unit706is labeled K0-K6.

TABLE ISubstitution performed by each of the seven constituting substitutionboxes of substitution boxes 604/704.0123456789101112131415SK08145930126111152471013SK11641583115100912713142SK21311867421511214010395SK30141171232131548191056SK41271581114146103509132SK51127283414115015136109SK61076101431312911215548SB01293011513624147815110SB13814152111310497615120SB27411011131431215602895SB36314101215251411897013SB43615124192581071113014SB51114685212714153101390SB61117425129136815140310

TABLE IIIDiffusion networks for linear transformation unit 606/706(continued in Table IV).K1K2K3K4K5K6K7K8I0Kz0Ky0Ky4Ky8Ky12Ky16Ky20Ky24I1Kz1Ky1Ky5Ky9Ky13Ky17Ky21Ky25I2Kz2Ky2Ky6Ky10Ky14Ky18Ky22Ky26I3Kz3Ky3Ky7Ky11Ky15Ky19Ky23Ky27I4Kz4Kz7Kz10Kz13Kz16Kz19Kz22Kz25I5Kz5Kz8Kz11Kz14Kz17Kz20Kz23Kz26I6Kz6Kz9Kz12Kz15Kz18Kz21Kz24Kz27O0Kx0Ky0Ky1Ky2Ky3Kx7Kx8Kx9O1Kx1Ky4Ky5Ky6Ky7Kx10Kx11Kx12O2Kx2Ky8Ky9Ky10Ky11Kx13Kx14Kx15O3Kx3Ky12Ky13Ky14Ky15Kx16Kx17Kx18O4Kx4Ky16Ky17Ky18Ky19Kx19Kx20Kx21O5Kx5Ky20Ky21Ky22Ky23Kx22Kx23Kx24O6Kx6Ky24Ky25Ky26Ky27Kx25Kx26Kx27

TABLE IVDiffusion networks for linear transformation unit 606/706(continued from Table III).B1B2B3B4B5B6B7B8I0Bz0By0By4By8By12By16By20By24I1Bz1By1By5By9By13By17By21By25I2Bz2By2By6By10By14By18By22By26I3Bz3By3By7By11By15By19By23By27I4Bz4Bz7Bz10Bz13Bz16Bz19Bz22Bz25I5Bz5Bz8Bz11Bz14Bz17Bz20Bz23Bz26I6Bz6Bz9Bz12Bz15Bz18Bz21Bz24Bz27K0Ky0————Ky7Ky14Ky21K1Ky1————Ky8Ky15Ky22K2Ky2————Ky9Ky16Ky23K3Ky3————Ky10Ky17Ky24K4Ky4————Ky11Ky18Ky25K5Ky5————Ky12Ky19Ky26K6Ky6————Ky13Ky20Ky27O0Bx0By0By1By2By3Bx7Bx8Bx9O1Bx1By4By5By6By7Bx10Bx11Bx12O2Bx2By8By9By10By11Bx13Bx14Bx15O3Bx3By12By13By14By15Bx16Bx17Bx18O4Bx4By16By17By18By19Bx19Bx20Bx21O5Bx5By20By21By22By23Bx22Bx23Bx24O6Bx6By24By25By26By27Bx25Bx26Bx27

Referring now back toFIG. 5, recall that a ciphered text may be deciphered by generating the intermediate “keys” and applying them backward. Alternatively, for an embodiment where either the inverse of substitution boxes604/704and linear transformation units606/706are included or they may be dynamically reconfigured to operate in an inverse manner, the ciphered text may be deciphered as follows. First, the cipher key used to cipher the plain text is loaded into block key section502, and block key section502is advanced by R−1 rounds, i.e. one round short of the number of rounds (R) applied to cipher the plain text. After the initial R−1 rounds, the ciphered text is loaded into data section504, and both sections, block key section502and data section504, are operated “backward”, i.e. with substitution boxes604/704and linear transformation units6061706applying the inverse substitutions and linear transformations respectively.

FIGS. 4a-4cillustrate the stream key section ofFIG. 1in further detail, in accordance with one embodiment. As illustrated inFIG. 4a, stream key section506includes a number of linear feedback shift registers (LFSRs)802and combiner function804, coupled to each other as shown. LFSRs802are collectively initialized with a stream cipher key, e.g. earlier described frame key Ki. During operation, the stream cipher key is successively shifted through LFSRs802. Selective outputs are taken from LFSRs802, and combiner function804is used to combine the selective outputs. In stream mode (under which, rekeying is enabled), the combined result is used to dynamically modify a then current state of a block cipher key in block key section502.

For the illustrated embodiment, four LFSRs of different lengths are employed. Three sets of outputs are taken from the four LFSRs. The polynomials represented by the LFSR and the bit positions of the three sets of LFSR outputs are given by the table to follows:

The combined result is generated from the third set of LFSR outputs, using the first and second set of LFSR outputs as data and control inputs respectively to combiner function802. The third set of LFSR outputs are combined into a single bit. In stream mode (under which, rekeying is enabled), the combined single bit is then used to dynamically modify a predetermined bit of a then current state of a block cipher key in block key section502.

FIG. 4billustrates combiner function804in further detail, in accordance with one embodiment. As illustrated, combiner function804includes shuffle network806and XOR808a-808b, serially coupled to each other and LFSRs802as shown. For the illustrated embodiment, shuffle network806includes four binary shuffle units810a-810dserially coupled to each other, with first and last binary shuffle units810aand810dcoupled to XOR808aand808brespectively. XOR808atakes the first group of LFSR outputs and combined them as a single bit input for shuffle network806. Binary shuffle units810a-810dserially propagate and shuffle the output of XOR808a. The second group of LFSR outputs are used to control the shuffling at corresponding ones of binary shuffle units810a-810d. XOR808bcombines the third set of LFSR outputs with the output of last binary shuffle unit810d.

FIG. 4cillustrates one binary shuffle unit810* (where * is one of a-d) in further detail, in accordance with one embodiment. Each binary shuffle unit810* includes two flip-flops812aand812b, and a number of selectors814a-814c, coupled to each other as shown. Flip-flops812aand812bare used to store two state values (A, B). Each selector814a,814bor814creceives a corresponding one of the second group of LFSR outputs as its control signal. Selector814a-814balso each receives the output of XOR808aor an immediately preceding binary shuffle unit810* as input. Selector814a-814bare coupled to flip-flops812a-812bto output one of the two stored state values and to shuffle as well as modify the stored values in accordance with the state of the select signal. More specifically, for the illustrated embodiment, if the stored state values are (A, B), and the input and select values are (D, S), binary shuffle unit810* outputs A, and stores (B, D) if the value of S is “0”. Binary shuffle unit810* outputs B, and stores (D, A) if the value of S is “1”.

Referring now to back toFIG. 1, as illustrated and described earlier, mapping function508generates the pseudo random bit sequence based on the contents of selected registers of block key section502and data section504. In one embodiment, where block key section502and data section504are implemented in accordance with the respective embodiments illustrated inFIG. 2-3, mapping function508generates the pseudo random bit sequence at 24-bit per clock based on the contents of registers (Ky and Kz)602b-602cand (By and Bz)702b-702c. More specifically, each of the 24 bits is generated by performing the XOR operation on nine terms in accordance with the following formula:
(B0•K0)⊕(B1•K1)⊕(B2•K2)⊕(B3•K3)⊕(B4•K4)⊕(B5•K5)⊕(B6•K6)⊕B7⊕K7

Where “⊕” represents a logical XOR function, “•” represents a logical AND function, and the input values B and K for the 24 output bits are

Accordingly, a novel dual use block or stream cipher has been described.

Epilogue

From the foregoing description, those skilled in the art will recognize that many other variations of the present invention are possible. In particular, while the sent invention has been described with the illustrated embodiments, non-LFSR based stream key section, more or less block key registers, larger or smaller block key registers, more or less substitution units, including alternative substitution patterns, as well as different linear transformation units may be employed. Thus, the present invention is not limited by the details described, instead, the present invention can be practiced with modifications and alterations within the spirit and scope of the appended claims.