Key stream cipher device

[0001] The present invention is directed to key stream ciphers and more particularly to a hardware architecture that supports the RC4 algorithm.

[0002] A cipher is a cryptographic algorithm used for encryption and decryption. A stream cipher is a type of encryption algorithm that encrypts data using a keystream, which is a sequence of bits used as a key. More specifically, a stream cipher, as opposed to a block cipher, processes a variable-length message stream. In a symmetric key algorithm, the same key is used for both encryption and decryption of data. Encryption is accomplished by combining the keystream with the plain text, usually by exclusive-ORing (XOR) the keystream and the plain text. Decryption is accomplished similarly, by combining (XORing) the keystream with the cyphertext.

[0003] The most widely used stream cipher today is RC4 (RC4 is a registered trademark of RSA Security Inc.), which was developed in 1987 by Ron Rivest. RC4 is used in many commercial cryptography products for file encryption and secure communications, including LOTUS NOTES software, Apple Computer's AOCE, and Oracle Secure SQL. It is also part of the Cellular Digital Packet Data specification. LOTUS NOTES is a trademark of International Business Machines Corporation.

[0004] RC4 is a variable-key size stream cipher with byte-oriented operations. The algorithm is based on the use of a random permutation and the period of the cipher is likely to be greater than 10¹⁰⁰. RC4 uses a 256 byte table substitution box (Sbox) that is initialized and permuted with a variable sized key. That is, the table entries are a permutation of the numbers 0 through 255, and the permutation is a function of the variable-length key. Each byte of the plaintext to be encrypted is XORed with a random byte from the table and the table contents are continually shuffled as each byte of the message is processed.

[0005] RC4 is usually implemented in software using one or more general purpose processors. However, an ever growing demand for bulk data encryption in wireless and wire line networks is driving the need for hardware accelerators and co-processors capable of processing data faster than existing software implementations.

[0015] The detailed description set forth below in connection with the appended drawings is intended as a description of the presently preferred embodiments of the invention, and is not intended to represent the only forms in which the present invention may be practiced. It is to be understood that the same or equivalent functions may be accomplished by different embodiments that are encompassed within the spirit and scope of the invention. In the drawings, like numerals are used to indicate like elements throughout.

[0016] The present invention is an encryption engine or hardware accelerator that supports the RC4 algorithm. The encryption engine includes a finite state machine that operates in four modes, initialization, permutation, message processing, and idle/ready. The engine also has an Sbox memory that is accessed using four pointers. A programmable counter is used to select each byte of the variable sized key during Sbox permutation. Preferably, the Sbox is implemented with a dual port RAM and a read-ahead approach is used to maximize data throughput. Additionally, a working register is used to double buffer the input to allow new data to be written while the current sub-message is being processed.

[0017] Referring now to FIG. 1, a high-level flow chart of the RC4 algorithm is shown. The algorithm has three main steps or phases. The first step 10 is an initialization step in which the Sbox or state table is initialized. The Sbox is initialized by setting each location equal to an index value. For example, for a 256 element array, then for i=0 to 255, Sbox[i]=i. A second, key array of the same size is filled with the key value, repeating bytes as necessary.

[0018] The second step 12 generates permutations of the Sbox entries with a variable length key and stores them back into the Sbox. An example of the second, permutation step 20 follows.

[0019] for i=0 to 255:

• • [0020] j=(j+Sbox[i]+Key[i]) mod 256
  • [0021] swap Sbox[i] and Sbox[j].

[0022] The Sbox now contains random permutations of its original entries. Further, the Sbox evolves with use. The index i ensures that every entry changes and the index j ensures that the entries change randomly.

[0023] In a third, message processing step 14, random Sbox entries are used to either convert a message to ciphertext or recreate a message from ciphertext. Pseudo code for the message processing step 30, in which a message is converted to ciphertext follows.

[0024] i=j=0;

• • [0025] for each byte of the message,
  • [0026] begin
    • [0027] i=(i+1) mod 256
    • [0028] j=(j+Sbox[i]) mod 256 swap Sbox[i] and Sbox[j]
    • [0029] k=(Sbox[i]+Sbox[j]) mod 256
    • [0030] ciphertext byte=message byte XOR Sbox[k]end.

[0031] In order to decrypt an encrypted message, only the XOR step is changed, such that a message is equal to ciphertext XORed with Sbox[k].

[0032] Referring now to FIG. 2, a flow chart of the permutation step in accordance with the present invention is shown. The present invention recognizes and takes advantage of the fact while the value of index “j” is dependent on the index “i”, the index “i” is a simple counter from 0 to 255. Thus, using the appropriate hardware, Sbox[i+1] can be read at substantially the same time as Sbox[j]. Although the algorithm becomes more complex, a hardware implementation using a dual-port RAM eliminates the need to read Sbox[i] and Sbox[j] in separate cycles.

[0033] In a first step 20, certain variables and the indexes i and j are initialized. That is, indexes i and j are set to zero and variable K is set to Sbox[0]. The variable K is used later during a swapping step. In a next step 22, the RC4 permutation calculation is performed. The permutation calculation is performed according to equation 1.
j=(j+K+key[i mod(key_length+1)])mod 256  (1)
The difference from the standard RC4 algorithm is the use of the variable K instead of Sbox[i]. In the first iteration, K=Sbox[0]. However, in subsequent iterations, K is equal to sbox_next_i, which is Sbox[i+1], as defined at step 30. It will be understood by those of skill in the art that “key[i mod(key_length+1)]” could be replaced with key[i].

[0034] In a next step 24, Sbox[i+1] is fetched and the variable sbox_next_i is set to Sbox[i+1]. Step 24 is followed by step 26, which is a swapping step. In step 26, Sbox[i] is set to Sbox[j] and Sbox[j] is set to Sbox[i+1]. In the hardware implementation described below, an Sbox register L is used to facilitate the swapping function.

[0035] Then, at a next step 28, the value of the index j is compared to (i+1). If the index j is not equal to (i+1), then step 30 is executed, which sets K equal to sbox_next_i (i.e. Sbox[i+1]). After step 28, or step 30 if j is not equal to (i+1), the index i is incremented and the algorithm is repeated until the index i is greater than 255, as indicated by steps 32 and 34. It is understood by those of skill in the art that the loop is not necessarily repeated 255 times, but that the value of i is determined by the size of the Sbox and that the modulo arithmetic also depends on the size of the Sbox.

[0036] FIG. 3 is a flow chart of a message processing step with read-ahead in accordance with the present invention. A first step 36 is the same as the first step 20 in FIG. 2, in which certain variables and the indexes i and j are initialized. That is, indexes i and j are set to zero and variable K is set to Sbox[0]. In a next step 38, standard RC4 processing calculations are performed, followed by a swapping step 40. The standard RC4 processing calculations are setting the index i equal to ((i+1) mod 256) and the index j equal to ((j+k) mod 256). In the swapping step 40, Sbox[i] is set to Sbox[j]. However, rather than setting Sbox[j] equal to Sbox[i], Sbox[j] is set to the variable K, which has a value of Sbox[i+1] or sbox_next_i. As in the permutation step, the Sbox register L is used to facilitate the swapping function.

[0037] Step 40 is followed by step 42, which determines a pseudorandom byte in accordance with the RC4 algorithm. That is, M=(Sbox[i]+Sbox[j]) mod 256. Next, in step 44, a byte of the ciphertext is generated by XORing a byte of the message with the pseudorandom byte from the Sbox, i.e., Sbox[M]. In a decrypting process, a byte of the ciphertext is XORed with the pseudorandom Sbox byte to recreate a byte of the message. Step 44 is followed by step 46, which checks to determine whether or not j is equal to i+1. If j is not equal to i+1, then the variable K is equated to Sbox[i+1] using the variable Sbox_next_i at step 48. Alternatively, if j is equal to i+1, then if the last byte of the message has not yet been processed, as determined at step 50, the algorithm is repeated by looping back to step 38. Step 48 is also followed by step 50.

[0038] Referring now to FIG. 4, a schematic block diagram of a symmetric key stream processor 60 in accordance with an embodiment of the invention is shown. The symmetric key stream processor 60 is a hardware accelerator having a main processing block 62 and a host interface 64. The main processing block 62 includes a status register 66, a control register 68, an address decoder 70, a key register logic 72, a message block 74, an Sbox registers block 76, an Sbox memory 78 and an encryption logic block 80.

[0039] The host interface 64 is a bridge between a host computer or processor or external circuitry and the main processing block 62. However, it is understood that a host or other circuitry may be formed on the same substrate as the host interface 64 and the main processing block 62. The host interface 64 resynchronizes the timing signals from the host. That is, the host interface 64 converts the timing signals to a synchronous interface for the main processing block 62. The resynchronization of the timing signals allows for a consistent, generic interface to the key stream processor 60 from different hosts. The host interface 64 passes all data, address and control signals between a host and the main processing block 62. The host interface 64 presents a simple, memory mapped architecture, which minimizes the need for special glue logic outside of the key stream processor 60.

[0040] The status register 66 is connected to the encryption logic block 80 and to the host interface 64 by way of the address decoder 70. The status register 66 is used to indicate the state of the key stream processor 60 and includes such information as busy, initialization complete, permutation stage complete, message processing complete, ready to receive next sub-message, and interrupt pending. In the presently preferred embodiment, the status register has seven bits as shown in Table 1.

[0041] Bit 0 indicates that the main processing block 62 is busy. Bit 1 indicates an interrupt is pending. The cause of the interrupt can be determined from the bit condition bits 2–6.

[0042]

TABLE 1
Bit	Name	Cause of Assertion
0	Busy	Initializing, permuting, processing or
		writing to memory
1	IRQ	Interrupt pending
2	Init. Complete	Sbox initialization complete
3	Permute complete	Sbox permutation complete
4	Sub-msg complete	Sub-message processing complete
5	Full-msg complete	Last sub-message processing complete
6	Input buffer empty	Next sub-message may be written to main
		processing block 62

[0043] The control register 68 is connected to the host interface 64 by way of the address decoder 70. The control register 64 is used to reset the main processing block 62 and to mask interrupts. In the presently preferred embodiment, the control register 68 has two bits. A first bit is for masking or disabling interrupts and a second bit is for triggering a software reset. Similar to the software reset, the preferred embodiment also includes a hardware reset that is triggered via an input to the host interface 64, e.g., a reset pin (not shown).

[0044] Referring now to FIG. 5, the Sbox memory 78 preferably comprises a 256×8-bit synchronous dual-port RAM having 8-bit wide address and data lines. The Sbox memory 78 is connected to the address decoder 70. Further, the Sbox memory 78 includes a read/write controller 79. The dual port RAM can be treated as two separate RAMs (A and B), with each having an address (ADDR_A, ADDR_B), a data-in port (DIN_A, DIN_B), data-out port (DO_A, DO_B), and independent write enables (WE_A, WE_B) and chip enables (CE_A, CE_B). The A and B RAMs share a common clock signal. The dual port architecture is used for efficiency during permutation and message processing, as described above with reference to FIGS. 2 and 3. Since dual port RAMs are understood by those of skill in the art, further description of the RAM architecture is not required for a complete understanding of the invention.

[0045] The Sbox registers block 76 includes four 8-bit registers Sbox I, Sbox J, Sbox K, and Sbox L that store Sbox pointers I, J, K and L. The Sbox I and Sbox J registers are used to store the i and j indexes or pointers (see FIGS. 1–3) and the Sbox K and Sbox L registers are temporary storage registers used to perform the swapping functions of the modified RC4 algorithm. That is, the K and L registers are used to swap the data stored in any two locations in the Sbox memory 78. The Sbox I and J registers are accessible to the host for the purpose of context reads and context writes in order to restore the I and J pointers to their current values, in the case of an interrupt, after the interrupt processing is finished.

[0046] Although FIG. 4 shows a bus structure connecting the different functional blocks of the main processing block 62, the status and control registers 66 and 68 and the Sbox registers 76 preferably are connected by a virtual bus defined by numerous internal signals and controlled by the encryption logic block 80 and an internal address signal IADDR.

[0047] Referring now to FIG. 6, a high level block diagram of a portion of the address decoder 70 is shown. The address decoder 70 includes an input buffer 710, an output buffer 712, a decoder 714 and a selector 716. The input buffer 710 receives input data IDATA from the host interface 64. The input data IDATA represents sbox_wr_data_a and sbox_wr_data_b shown in FIG. 5. The input data IDATA can include key data, message text, ciphertext and control information. The input buffer 710 is enabled by an IWRITE signal (i.e., wen_a and wen_b of FIG. 5) received from the host interface 64. The decoder 714 is connected to the input buffer 710 and receives the input data IDATA. The decoder 710 also receives the internal address signal IADDR from the host interface 64. As is understood by those of skill in the art, the sbox address can also be designated by the index registers i and j. The decoder 714 formats and specifies the input data as key information, Sbox information, a message, or control register data, depending on the value of the internal address signal IADDR. The key information includes key data and key length and is provided to the key register logic 72 and to the message block 714. The Sbox information includes Sbox I and J index values and data to be written to the Sbox memory 78. The decoder 714 can also pass message bytes to the message block 74 by way of the encryption logic block 80. The decoder 714 also identifies information to be stored in the control register 68.

[0048] The output buffer 712 transmits output data ODATA from the selector 716 to the host interface 64. The output buffer 712 is enabled by an IREAD signal received from the host interface 64. The selector 716, under the control of the IADDR signal, passes data to the ouput buffer 712. The data transmitted to the output buffer 712 from the selector 716 includes data read from the Sbox memory 78 (dout_a and dout_b shown in FIG. 5), data read from the status register 66, data from the control register 68, data from the Sbox registers 76, and message or cipher text. As previously discussed, the internal address signal IADDR is generated by the host interface 64.

[0049] FIG. 7 is a high level schematic block diagram of one embodiment of the key register logic 72 in accordance with a preferred embodiment of the invention. The key register logic 72 includes a key register 720 that in the preferred embodiment is a 16 byte (128 bits) write-only register that holds the encryption key. The key register 720 includes separately addressable blocks. That is, each byte of the key data stored in the key register 720 is separately addressable, as specificed by a pointer signal, key_select. Since the key can vary in length, the key register logic 72 includes a 4 bit write-only register 722 that holds the key length, i.e., the number of bytes in the current key. In a preferred embodiment, the key length register 722 is independently addressed. The key register 720 and the key length register 722 receive key data and key length data, respectively, from the host interface 64 by way of the address decoder 70.

[0050] The key register logic 72 also includes a first counter 724, which in the preferred embodiment is a 4-bit counter. The first counter 724 is used to generate the pointer signal, key_select, which is used to select a new byte of the key during Sbox permutation (FIG. 2). Each time the first counter 724 is incremented, a new byte of the key stored in the key register 720 is selected. Since the key length can vary, the first counter 724 is programmable. In order to implement the following equations (2) and (3), the key register logic 72 includes a second counter 726 and a comparator 730.
key_select=count mod(key_length+1)  (2)
key_byte=key_data[key_select]  (3)

[0051] A buffer 728 is connected between the counter 726 and a 4-bit key_select register 732. The buffer 728 is enabled when fetching the next key byte. The key_select register 732 stores the current key_select pointer.

[0052] Referring now to FIG. 8, the message block 74 includes a message register 740 and a cipher register 742. In a preferred embodiment, the message register 740 is a 32-bit write-only register that stores plain text and the cipher register 742 is a 32-bit read-only register that stores encrypted text or ciphertext. The opposite is true for the inverse cipher (decryption). In the presently preferred embodiment, each 32 bits of message data, referred to herein as a sub-message, stored in the message register 740 is processed one byte at a time. The message byte read from the message register 740 is XORed with one byte from the Sbox memory 78 (sbox_xor_byte) by a plurality of XOR gates 744 and the resulting ciphertext is stored in the cipher register 742. In FIG. 8, the XOR gates 744 each represents plural XOR gates, such as 8 XOR gates.

[0053] To reduce idle time between sub-messages, a working register 746 is used to hold the sub-message while it is being processed, which allows the host to write the next sub-message to the message register 740 while the current sub-message is being processed. Upon receiving a new sub-message from the host, an internal new message flag is set. The new message flag in turn clears an input empty status bit. When the sub-message in the working register 746 has been processed and is stored in the cipher register 742, the contents of the message register 740 are transferred to the working register 746 and processed. At this point, the input empty status bit is set, indicating to the host that the next sub-message may be written to the message register 740. Although the implementation shown in FIG. 8 processes the message text a byte at a time, the number of XOR gates could be increased as desired. For example, the message text could be processed two bytes at a time or even a word at a time.

[0054] The function of the encryption logic block 80 can be broken into three separate tasks: SBox initialization, SBox permutation, and message processing. By nature, the RC4 algorithm allows some overlap of hardware elements for these three tasks, such as counters, adders and the XOR gates 744 (FIG. 8). The encryption logic block 80 is responsible for controlling the Sbox memory address and input data and controlling the Sbox I, J, K and L registers. In the presently preferred embodiment, the host interface 64 uses a 32-bit data bus, which allows four sequential bytes of the Sbox memory 78 to be accessed during one host bus cycle. The Sbox memory 78 can be accessed to retrieve or restore the message context (state) at any point in the message stream. The address written to the key stream processor 60 denotes the starting address/offset in the Sbox memory 78. A 2-bit counter's value is added to the base address as each sequential byte is read/written to the Sbox memory 78.

[0055] As discussed with reference to FIGS. 2 and 3, to increase performance of permutation and message processing, the value i+1 is used in the modified algorithm. Accordingly, an i_plus_—1 register (not shown) is used to hold the value of index i plus one. The i_plus_—1 register is used to read the contents of the Sbox memory 78 at location i+1. This read-ahead approach is possible because the value of i is always known because it is simply the output of an 8-bit counter.

[0056] At the start of the permutation or message processing phases, a one-time read is performed to obtain the contents of the Sbox memory 78 at location i=0. The contents are stored in a “dout_next_i” register. This value is used to calculate the index j for the first iteration. For each subsequent iteration, the Sbox memory 78 contents at location i+1 are read in the same cycle as the contents of j. This approach makes full use of the dual-port RAM and eliminates one read cycle. The calculated value of j and the data written to location j during the swap uses the value of “dout_next_i” from the previous iteration. In the event that j=i+1, “dout_next_i” holds its value from the previous iteration. Table 2 shows the memory usage and data flow.

[0057]

TABLE 2
STATE	INIT	PERMUTE	SUB-MESSAGE PROCESS
Cnt_2_3	xx	0**	0	1	0**	0	1	2
ADDR_A	I	I	I + 1	I	I	I + 1	J	K + L
DIN_A	I	—	—	L	—	—	L	—
WEN_A	1	0	0	1	0	0	1	0
DO_A	xxx	next i	next i	xxx	next i	next i	xxx	XOR
								w/MSG
ADDR_B	—	—	J	J	—	J	J	—
DIN_B	—	—	—	K	—	—	L	—
WEN_B	0	0	0	1	0	0	1	0
DO_B	xxx	xxx	L	xxx	xxx	L	xxx	xxx

[0058] At the locations in the table including a “**” one time reads are performed to calculate j in the next iteration. Each subsequent iteration's k value is “next i” from the previous iteration.

[0059] The encryption logic block 80 operates in accordance with a finite state machine (FSM) that has 7 states: reset, S-box initialization, initialization done/wait for key, S-box permutation, permutation done/wait for message, sub/full message process, and sub-message done. The state machine is dependent on the variables: Reset, Sbox write, Busy (Intializing, permuting, message processing), Full message done (last sub-message complete), and Current state. The state definitions are shown in Table 3.

[0060] As is apparent, the present invention provides a symmetric key stream-cipher architecture implemented in a heterogeneous integrated circuit. More particularly, the key stream-cipher architecture implements the RC4 algorithm. In one embodiment, the encryption engine is suitable for multi-mode and multi-band cellular telephones. It is to be understood, however, that this invention is not limited to the particular embodiments disclosed, but covers modifications within the spirit and scope of the present invention as defined by the appended claims.

[0061]

TABLE 3
	Context		Full	From	To
Reset_B	Write	Busy	Done	State	State	Description
0	?	?	?	?	0	Reset
1	0	0	0	0	0	Idle (reset done)
1	0	1	0	0	1	Start Sbox init
1	0	1	0	1	1	Sbox init (busy)
1	0	0	0	1	2	Sbox init done
1	0	0	0	2	2	Wait for key
1	0	1	0	2	3	Start Sbox perm
1	0	1	0	3	3	Sbox perm (busy)
1	0	0	0	3	4	Perm/sub done
1	0	0	0	4	4	Wait for sub-msg
1	1	?	?	?	4	Context write
1	0	1	0	4	5	Start-msg proc
1	0	1	0	6	5	Next-msg proc
1	0	1	0	5	5	Sub-msg proc
1	0	0	0	5	6	Sub-msg done
1	0	0	0	6	6	Wait for next msg
1	0	0	1	5	0	Full msg done