WO2007060587A1

WO2007060587A1 - Mutli-lane high-speed encryption and decryption

Info

Publication number: WO2007060587A1
Application number: PCT/IB2006/054319
Authority: WO
Inventors: Michael A. Epstein; James Ross Goodman
Original assignee: Koninklijke Philips Electronics, N.V.
Priority date: 2005-11-23
Filing date: 2006-11-17
Publication date: 2007-05-31
Also published as: KR20080073348A; EP1955473A1; CN101313509A; JP2009516976A; RU2008125109A

Abstract

An encryption system is configured to include a combination of block (130) and stream (150) cipher generators. The block cipher generator (130) provides a changing key (149) that is used to periodically re-key one or more stream cipher generators (150). Preferably an AES block encryptor (135) provides a set of 128-bit ciphers (139) that are used to provide a stream of 576-bit keys (149) that is used to periodically re-key one or more SNO W-2 stream cipher generators (150). The output (159) of the stream cipher generators (150) are used to encrypt multiple input data streams (263-264), or 'lanes' of data, using an optimized arrangement of the block (130) and stream (150) ciphers relative to these multiple lanes of data (263-264).

Description

MULTI-LANE HIGH-SPEED ENCRYPTION AND DECRYPTION

This application claims the benefit of U.S. Provisional Patent Application 60/739,219 filed 23 November 2005. This invention relates to the field of communications and data security, and in particular to a method and system that facilitates high-speed multi-lane, parallel data channel, encryption and decryption.

A stream cipher is a cipher in which the input stream is encrypted sequentially, generally one data unit (word/byte/bit) at a time, and in which the transformation of subsequent data units varies during the encryption. A block cipher, on the other hand, is a cipher that operates on large blocks of data with a fixed, unvarying transformation. That is, a block cipher of a given block of data and a given encryption key will always produce the same encrypted output block. A stream cipher's output, on the other hand, is dependent upon the state of the cipher system at the time that the data unit is being encrypted. Generally, a stream cipher combines the input stream with a generated keystream, the keystream being pseudorandomly generated based on a given encryption key, or set of keys. Because the sequential generation of a keystream is generally a less complex operation than the block-encryption of a data block, stream ciphers are typically substantially faster than block ciphers, and require substantially fewer hardware components.

Stream ciphers are particularly well suited for the high-speed encryption/decryption of streams of data of unknown length, such as telephone conversations, streaming video, and so on. When block ciphers are used on such data, the design must include provisions for padding input streams that terminate prior to filling a block. Many stream ciphers are configured to produce a multi-bit output at each clock cycle. The SNOW cipher, and it successor SNOW-2, by Ekdahl and Johansson of Lund University, for example, use a linear feedback shift register that drives a state machine that is configured to output a 32-bit word on each cycle. To effectively utilize such a multi-bit cipher output, parallel encryption is often used, wherein an input stream is demultiplexed into a data set that includes the same number of bits as the output cipher, the data set is encrypted using the multi-bit cipher, and then multiplexed into an output stream in the same form as the input stream. For example, if the input stream comprises data bytes on an 8-bit wide bus, and a 32-bit cipher word is available, each set of four 8-bit bytes on the bus are spread into a 32-bit word, the 32-bit word is encrypted using the 32-bit cipher word, and the resultant 32-bit output word is de-spread into four output bytes corresponding to the encryption of the four input bytes. In such an embodiment, the cipher generator can support a throughput rate of the input stream as high as four times the speed of the cipher generation.

In some cases, the input data rate may be substantially less than the maximum speed that a particular cipher generator can support. In such cases, multiple data streams may be supported by a single cipher generator. In the previous example, if the speed of the 8-bit wide input data stream is twice the speed of the 32-bit cipher generator, two such 8- bit data streams can be supported by this 32-bit cipher generator; if the speed of the 8-bit wide input data stream is equal to the speed of the 32-bit cipher generator, four such input data streams can be supported by the cipher generator; and so on.

It is generally known, however, that stream ciphers are less secure than block ciphers, in that they are more susceptible to distinguishing attacks that use less than an exhaustive search. Further, all stream ciphers are vulnerable to attack if the keystream is repeated. Ideally, with a 128-bit key, the keystream's repeat-length is 2¹²⁸ bits, which is acceptable in most applications, but at an encryption rate of 100Mb per second, the recycle time of such a cipher amounts to under 25 minutes, which renders the cipher unsuitable for long-running applications, such as streaming video. On the other hand, the complexity of block ciphers renders them either too costly or too slow for such consumer applications. It would be advantageous to provide a cipher that provides the speed of a stream cipher and the security of a block cipher.

In accordance with one embodiment of the present invention, a cipher system comprises a combination of block and stream ciphers. The block cipher provides a changing key that is used to periodically re-key one or more stream ciphers. Preferably an AES (Advanced Encryption Standard, from the U.S. National Institute of Standards and Technology (NIST)) block cipher provides a set of 128-bit keys that are used to provide a stream of 576-bit keys that is used to re-key one or more SNO W-2 stream ciphers. The output of the stream ciphers are used to encrypt multiple input data streams, or 'lanes' of data, using an optimized arrangement of the block and stream ciphers relative to these multiple lanes of data. The invention is explained in further detail, and by way of example, with reference to the accompanying drawings wherein:

FIGs. IA- 1C illustrate an example multi-bit stream encryption system, in accordance with one embodiment of the present invention, that is systematically re-keyed using keys provided by a block cipher generator.

FIGs. 2A-2B and 3A-3B illustrate other example multi-bit stream encryption systems, in accordance with other embodiments of the present invention, that are systematically re- keyed using keys provided by a block cipher generator. FIGs. 4A and 4B illustrate mixing systems, in accordance with various embodiments of the present invention, for encrypting data bytes using a cipher output that spans multiple bytes. Throughout the drawings, the same reference numeral refers to the same element, or an element that performs substantially the same function. The drawings are included for illustrative purposes and are not intended to limit the scope of the invention. In the following description, for purposes of explanation rather than limitation, specific details are set forth such as the particular architecture, interfaces, techniques, etc., 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 in other embodiments, which depart from these specific details. For purposes of simplicity and clarity, detailed descriptions of well-known devices, circuits, and methods are omitted so as not to obscure the description of the present invention with unnecessary detail.

FIG. IA illustrates an example block and stream cipher system, in accordance with one embodiment of the present invention, for multi-bit parallel encryption of an input stream 163 having a word size that is less than the word size of the stream cipher generator 150. For example, the input stream comprises 8-bit data bytes, and a SNO W-2 stream cipher generator is used to provide the stream cipher. As is known in the art, the SNO W-2 process uses a 576-bit key 149 as an initial state for generating a sequence of 32-bit wide cipher output words 159.

A mixing unit 160 is used to perform the encryption of the input stream 163 by mixing the cipher output words 159 of the stream cipher generator 150 with the input stream 163. To optimize the use of the sequence of 32-bit wide cipher words 159 from the stream cipher generator 150, the 8-bit input bytes 163 are 'spread' by a one-input, four- output demultiplexer 164 to form four 8-bit channels. The 32-bit cipher word 159 is similarly partitioned into four 8-bit cipher bytes, one cipher byte for each channel. At each channel, a mixer 165 combines the 8-bit data byte on the channel with the cipher byte assigned to the channel to produce an encrypted byte. Preferably, the mixer 165 performs an exclusive-OR function to combine the data and cipher bytes. The encrypted bytes of the four channels are provided to a four- input, one-output multiplexer 164' to form a sequence of encrypted output bytes 169 corresponding to each byte in the input stream 163. FIG. IB illustrates a timing diagram corresponding to the operation of the encryption system of FIG. IA. The first line illustrates the sequence of bytes in the input stream 163. The second line illustrates the sequence of cipher output words 159 of the stream cipher generator 150. Because each cipher output word 159 is used to encode four bytes of the input stream 163, the sequence of output words from the stream cipher generator has a frequency of one-quarter the input byte rate. That is, in FIG. IA, the cipher clock CLK-2 151 that is used to provide each cipher word is operated at one-quarter the frequency of the clock CLK-3 161 that is used to input each input data byte.

One of ordinary skill in the art will recognize that the encryption-channel structure of FIG. IA is merely provided for ease of reference, and other structures may be used as well. For example, if the input stream 163 comprises 16-bit words, the demultiplexer 164 will be structured to provide two 16-bit channels. In this case, the cipher clock CLK-2 151 will be operated at half the frequency of the clock CLK-3 161 that is used to input each input data word. In like manner, a serial register configuration or other structures may be used in lieu of the illustrated multiplexer structure as discussed further below with regard to FIGs. 4 and 5.

In accordance with one aspect of this invention, the stream cipher generator 150 receives its 576-bit key 149 from a block cipher generator 130. Preferably, the block cipher generator 130 receives its key from a session key generator 110 that generates a different key each time a user initiates an encryption session. Preferably, the session key is updated regularly to improve security.

In the example encryption system of FIG. IA, an AES encryptor 135 generates a 128-bit block cipher output 139 that is an encryption of the current contents of a running counter 132 at each cycle of a controlling clock CLK-I 131. As noted above, the example SNO W-2 stream cipher generator uses a 576-bit key; as such, five cycles of the controlling clock CLK- 1 131 are required to provide a sufficient number of bits to form this key. The 576-bit key corresponds to four and a half 128-bit cipher words from the AES encryptor 135, and the block cipher generator 130 includes a register 140 that is configured to store three and a half of these cipher words. When the fifth 128-bit cipher word is produced, a 576-bit output is provided using this current word and the previously stored three and a half words in the register 140.

As noted above, although stream cipher generators are generally significantly faster than block cipher generators, stream ciphers are less secure than block ciphers because the stream cipher repeats itself. If an attacker is able to determine some or all of the cipher sequences produced, and the repeat rate, the attacker would be able decrypt the encrypted material at each repetition of the determined sequence. Preferably, to avoid this vulnerability of the stream cipher generator 150, a new 576-bit key 149 is generated by the block cipher generator 130 and used to re-key the stream cipher generator 150 before the stream cipher generator 150 repeats itself. In this manner, a decryption of a prior segment of a stream-cipher-encrypted output cannot be used to facilitate decryption of a future segment.

FIG. 1C illustrates an example timing sequence for the generation and use of keys 149 in the example embodiment of FIG. IA. The 128-bit block cipher output 139 of the AES encryptor 135 at each clock cycle CLK-I is identified as cipher words A₀, A₁, A₂, etc. The content of the register 140 of FIG. IA is identified for ease of reference as a stream 142 in FIG. 1C. At the cycle after the fourth output A₃, the current output A₄ and the stream 142 are available for keying the stream cipher generator 150. Thereafter, another five cipher words A5-A9 are generated, and are used to re-key the stream cipher generator 150. As noted above, this re-keying preferably occurs before the stream cipher generator 150 repeats itself.

One of ordinary skill in the art will recognize that after the first generation of five cipher words, a new key can be made available to the stream cipher generator 150 as each new cipher word is generated, the new cipher word replacing a subset of the bits of the prior key. However, optimal security is obtained by re-keying after all of the bits of the prior key are replaced by new cipher words. FIG. 2A illustrates an example embodiment of a "dual-lane" encryption system wherein two input streams 263, 264 are encrypted using a single block-stream cipher system comprising the session key generator 110, block cipher generator 130 and stream cipher generator 150 as detailed above. In the embodiment of FIG. 2A, the rate of the clock CLK-2 251 is doubled, so that two cipher words 259 are available for encrypting the two input streams 263, 264 of the dual-lane mixing unit 260. However, in lieu of applying each word alternatively to each lane, which might introduce an undesirable latency at each lane, each cipher word 259 is demultiplexed across respective lanes corresponding to the input streams 263, 264. A one- input two-output demultiplexer 220 provides each even cipher word 259 to the first two bytes of each of the input streams 263, 264, and each odd cipher word 259 to the next two bytes of each of the input streams 263, 264.

FIG. 2B illustrates an example timing arrangement for the embodiment of FIG. 2A. As illustrated, each cipher word 259 is applied to a pair of input data bytes of each of the input streams 263, 264. As noted above, the block cipher generator 130 is preferably clocked to produce a new key 249 for the stream cipher generator using five new AES words (designated by reference numeral 139 of FIG. IA) before the stream cycle repeats itself.

One of ordinary skill in the art will recognize that alternative arrangements can be used to encrypt two streams of input data using a single block-stream encoder of this invention, depending upon the timing and structural constraints of the given application. For example, each lane may be structured as a two-byte lane, as contrast to the four-byte lanes of FIGs. IA and 2 A. In such an embodiment, the odd/even demultiplexer 220 would not be required. An advantage of the four-byte-lane embodiment of FIG. 2A, on the other hand, is the use of the same lane structure independent of whether one or two (or, as detailed below, four) input streams are being encrypted using the block-stream encryption system of this invention.

FIG. 3 A illustrates the use of multiple stream cipher generators with a single block cipher generator to encode, for example, four lanes of input data. As noted above, it is often advantageous to use/re-use common circuitry in different applications. In this example, the dual-lane mixing unit 260 of FIG. 2A is used to encrypt each pair of the four-lanes of input data, and two stream cipher generators 150, 150' are used to provide the stream ciphers to these two mixing units 260. Because of the dual structure, the encryption of the four lanes can be effected at the same rate (CLK-2 251) as the encryption of the two lanes of FIG. 2 A. However, because the re-keying of each of the stream cipher generators 150, 150' occurs at a much lower rate than the rate of generating the stream cipher, the dual structure need not include a pair of block cipher generators to supply the keys to the pair of stream cipher generators.

As also noted above, the 576-bit key 349 that is used for the stream cipher generator 150 requires four and a half 128-bit cipher words 339 from an AES encryptor 135. In the example embodiment of FIG. 3A, a multiplexer 342 is used to provide alternative half words 344 to the register 340. In this manner, two complete keys 349 may be produced from nine cipher words 339, instead of ten words 339. That is, instead of requiring a doubling of the rate of CLK-I 331 to support the two stream cipher generators 150, 150', the rate of CLK-I 331 need only be increased by a factor of 1.8. Because power consumption is generally related to speed, this 10% reduction in speed for the AES components may be significant. Alternatively, if the speed of the AES encryptor 135 is the limiting factor in the overall speed of the block-stream encryption system, this 10% effective increase in speed may also be significant. Additionally, by alternating the re- keying of each stream cipher system 150, 150', a single 576-bit wide register 340 can be used to provide the 576-bit key 349 to both of the stream cipher systems 150, 150', thereby saving a significant amount of circuitry and layout area.

FIG. 3B illustrates an example timing diagram for the embodiment of FIG. 3A. As in the prior embodiments, upon generation of five 128-bit cipher words 339, a 576-bit key 349 can be generated using four of these words and half 344 of the cipher word that is stored in the register 341. This first key is used to key the "even" stream cipher generator 150. Upon generation of four additional cipher words 339, another key 349 can be generated, using these four new words and the half of the cipher word 344 that had not been used for the first key. This second key is used to key the "odd" stream cipher generator 150'. This five- word/four- word sequence repeats to provide alternative unique keys for each of the cipher generators 150, 150' every nine cycles of CLK-I 331. One of ordinary skill in the art will recognize that alternative structures are feasible in view of this disclosure. For example, the use of nine cipher words 339 to provide two keys 349 could be applied to the embodiments of FIGs. IA, 2A as well. However, the relative speed of block and stream cipher generators generally do not demand such efficiency when the block cipher generator is coupled to a single stream cipher generator. In like manner, a single 32-bit stream cipher generator could be simply configured to directly encrypt each of the four data 8-bit input streams, but this would require that the stream cipher generator operate at twice the speed of the generators of FIG. 3 A, or that the data rate of the input data of FIG. 3 A be reduced in half.

One of ordinary skill in the art will also recognize that the concepts presented herein are not limited to the examples, and can be applied in a more general sense. For example, depending upon the relative speeds of the input data, stream cipher rate, and block cipher rate, a single block cipher generator may be used to provide keys to more than two stream cipher generators; a single stream cipher generator may be used to encrypt more than four data lanes, and so on.

FIGs. 4A and 4B illustrate example alternative embodiments of a mixing system that applies a 32-bit cipher word to a lane of 8-bit data words. In FIG. 4A, four shift registers R1-R4 420 are used to sequentially receive the 8-bit words of the data input stream, clocked in by the input data clock CLK-3. The 32-bit cipher output 450 is partitioned into four 8-bit segments that are provided to the registers R1-R4 420 via encryption multiplexer 410. Each encryption multiplexer 410 determines whether each register receives the unencrypted data input from the previous stage, or an encryption of the data input from the previous stage. Each encryption multiplexer 410 includes an 8- bit wide XOR gate 412, and an input switch 411 that determines one of the inputs of the XOR gate. To effect a pass-through of the input data without encryption, the switch 411 provides a fixed "0" output, so that the XOR gate 412 has no effect on the input data. When the "encrypt" signal is enabled, the input switch 411 provides eight bits of the cipher to the XOR gate 412 to effect an encryption of the input data. The encrypt signal is enabled after three input data words are clocked into the registers R1-R3 420 and the fourth data word is available at the input of the first encryption multiplexer 410. The registers are next clocked while the encrypt signal is enabled, and each register R1-R4 420 will be loaded with an encrypted data word. The encrypt signal is then disabled, and the process is repeated. As each subsequent data input word is being clocked into the registers, the encrypted data words are being clocked out, thereby effecting a continuous encryption with minimal latency. As noted, the encrypt signal is enabled once for every four data clock CLK-3 cycles, and thus the cipher output 450 need only be provided at one-quarter the data-input rate, as expected.

In FIG. 4B, a switch 440 is used to sequentially select each of the four 8-bit segments of the cipher output 450. The selected cipher segment is XOR'd with the current 8-bit data-input word, and preferably clocked into a register 420 to avoid switching transients. In this embodiment, a single 8-bit encryption stage comprising XOR gate 412 and register 420 provides an encrypted output at the data input rate of clock CLK-3. The cipher output 450 is preferably updated every four cycles of the data input clock CLK-3, so that no 8-bit cipher segment from the switch 440 is reused. One of ordinary skill in the art will recognize that alternative encryption schemes may be used to assure the optimal/efficient use of each of the cipher bits provided by the stream cipher generator.

The foregoing merely illustrates the principles of the invention. It will thus be appreciated that those skilled in the art will be able to devise various arrangements which, although not explicitly described or shown herein, embody the principles of the invention and are thus within the spirit and scope of the following claims.

In interpreting these claims, it should be understood that: a) the word "comprising" does not exclude the presence of other elements or acts than those listed in a given claim; b) the word "a" or "an" preceding an element does not exclude the presence of a plurality of such elements; c) any reference signs in the claims do not limit their scope; d) several "means" may be represented by the same item or hardware or software implemented structure or function; e) each of the disclosed elements may be comprised of hardware portions (e.g., including discrete and integrated electronic circuitry), software portions (e.g., computer programming), and any combination thereof; f) hardware portions may be comprised of one or both of analog and digital portions; g) any of the disclosed devices or portions thereof may be combined together or separated into further portions unless specifically stated otherwise; h) no specific sequence of acts is intended to be required unless specifically indicated; and i) the term "plurality of an element includes two or more of the claimed element, and does not imply any particular range of number of elements; that is, a plurality of elements can be as few as two elements.

Claims

CLAIMS We claim:

1. A system for encrypting data, comprising: a block cipher unit (130) that is configured to generate at least one cipher key (149, 249, 349); a stream cipher unit (150) that is configured to generate a sequence of cipher words (159, 259, 358-359) based on the at least one cipher key (149, 249, 349); and a mixer unit (160, 260) that is configured to combine, in parallel, multiple bits of each of the cipher words (159, 259, 358-359) and multiple bits of data input items (163, 263-264).

2. The system of claim 1, wherein each cipher word (159, 259, 358-359) comprises 'n' bits, and the mixer unit (160, 260) is configured to arrange the data input items (163, 263- 264) to facilitate a parallel encryption of 'n' bits of the data input items (163, 263-264).

3. The system of claim 1, wherein each data input item (163, 263-264) comprises 'm' bits that arrive at an input data rate (CLK-3), and the mixer unit (160, 260) is configured to arrange the cipher words (159, 259, 358- 359) to facilitate a parallel encryption of the 'm' bits of the data input items (163, 263-264) at the input data rate (CLK-3).

4. The system of claim 1, wherein the stream cipher unit (150) is characterized by a repeat cycle rate, and the block cipher unit (130) is configured to provide a different cipher key (149, 249,

349) at a cipher key rate (CLK-I) that is less than or equal to the repeat cycle rate, and the stream cipher unit (150) is configured to be re-keyed by the different cipher keys (149, 249, 349) at a re-key rate that is less than or equal to the cipher key rate (CLK-

I)-

5. The system of claim 4, wherein the cipher key rate (CLK-I) is equal to the repeat cycle rate.

6. The system of claim 4, wherein the re-key rate is equal to the cipher key rate (CLK-I).

7. The system of claim 4, wherein the block cipher unit (130) is configured to generate a plurality of block cipher outputs (139, 339) that form each different cipher key (149, 249, 349).

8. The system of claim 7, wherein at least one different cipher key (349) includes one or more of the block cipher outputs (339) of a prior cipher key (349).

9. The system of claim 1, wherein the block cipher unit (130) is configured to generate a plurality of block cipher outputs (139, 339) that form each different cipher key (149, 249, 349).

10. The system of claim 8, wherein at least one different cipher key (349) includes one or more of the block cipher outputs (339) of a prior cipher key (349).

11. The system of claim 1, wherein the block cipher unit (130) includes an AES encryptor (135).

12. The system of claim 11, wherein the stream cipher unit (150) includes a SNO W-2 stream cipher generator.

13. A method for encrypting data comprising: generating (130) at least one block cipher key (149, 249, 349), generating (150) a sequence of cipher words (159, 259, 358-359) based on the at least one cipher key (149, 249, 349), and parallel encrypting (160, 260) multiple bits of data input items (163, 263-264) using multiple bits of each of the cipher words (159, 259, 358-359).

14. The method of claim 13, including arranging (164) the data input items (163, 263-264) to facilitate the parallel encrypting of 'n' bits of the data input items (163, 263-264), where 'n' is a bit-width of each cipher word (159, 259, 358-359).

15. The method of claim 13, including generating (130) other block cipher keys (149, 249, 349) at a cipher key rate (CLK- 1) that is less than or equal to a repeat cycle rate of the sequence of cipher words (159, 259, 358-359), and generating (150) additional sequences of cipher words (159, 259, 358-359) based on the other block cipher key (149, 249, 349)s.

16. The method of claim 13, including generating (135) a plurality of block cipher outputs (139, 339) to provide the at least one block cipher key (149, 249, 349).

17. The method of claim 13, wherein generating (135) the at least one block cipher key (149, 249, 349) includes generating an AES cipher.

18. The method of claim 13, wherein generating (130) the sequence of cipher words (159, 259, 358-359) includes generating a SNO W-2 cipher.

19. A computer program provided on a computer readable media that, when executed on a processing system is configured to cause the processing system to: generate (130) at least one block cipher key (149, 249, 349), generate (150) a sequence of cipher words (159, 259, 358-359) based on the at least one cipher key (149, 249, 349), and encrypt (160), in parallel, multiple bits of data input items (163, 263-264) using multiple bits of each of the cipher words (159, 259, 358-359).

20. The computer program of claim 19 that causes the processing system to: generate (130) the at least one block cipher key (149, 249, 349) using an AES cipher, and generate (150) the sequence of cipher words (159, 259, 358-359) using a SNOW-2 cipher.