In a typical wireless LAN configuration, A common model for network processing consists of a multi-level approach. This is common in many Ethernet LAN protocols such as IEEE 802.3. The model typically includes 3 major levels, namely a) Top: Logical-Link control; b) Middle: Medium Access Control (MAC); and c) Bottom: Physical interface (PHY).
A wireless LAN configuration compliant to IEEE 802.11 is similar to its wired counterpart and has the same three levels. Traditionally, the top Logical-Link control tasks are handled by software running on a HOST processor. The middle level is the responsibility of a MAC processor, which handles all frame traffic between the HOST and the PHY level.
In a typical wireless local area network (WLAN) configuration, a portable or mobile device (e.g., a laptop personal computer) normally includes a HOST processor and a PCI card or PCMCIA card. On this card resides a Medium Access Control (MAC) processing system, a PHY (physical layer) processing device (e.g., a digital signal processor), and a main memory. The MAC processing system includes a MAC processor (e.g., an embedded processor), which is a multi-functional processor engine responsible for a variety of different processing tasks associated with the wireless communications. The PHY processing device performs such functions as encoding/decoding waveforms. Data transferred between the PHY processing device and the MAC processing system (i.e., the PHY data stream) may be encrypted using an encryption algorithm, such as RC4. Consequently, encrypted data received by the MAC processing system from the PHY processing device is initially stored to the main memory as encrypted data. At a later time, the MAC processor reads the stored encrypted data from main memory and decrypts the data. The decrypted data is then written to the main memory for subsequent processing by the HOST processor.
Similarly, in the case of a data transmission from the MAC processor to the PHY data processing device, the data originates from the HOST processor that writes the data as plaintext to the main memory. The MAC processor will at a later time read the data from the main memory and encrypt it, using the same RC4 algorithm. Then the encrypted data is transmitted to the PHY processing device.
Encryption algorithm RC4 (developed by RSA Data Security, Inc.) is used to encrypt data in accordance with Wired Equivalent Privacy for the IEEE wireless communications standard 802.11. RC4 is a variable key-size stream cipher with byte-oriented operations. The algorithm is based on the use of a random permutation. Analysis shows that the period of the cipher is overwhelmingly likely to be greater than 10100. Eight to sixteen machine operations are required per output byte, and the cipher can be expected to run very quickly in software. RC4 is commonly used for file encryption and for secure communications, as in the encryption of traffic to and from secure web sites using the secured socket layer (SSL) protocol.
In the prior art, both software and hardware approaches have been used to implement the private key RC4 algorithm. In the case where all operations are performed in software, a simple C program can be used, such as those illustrated herein. The RC4 algorithm can be divided into three basic phases: phase 1 for lookup and loading of a private key; phase 2 having two parts, namely, phase 2a for filling an S-box table linearly and phase 2b for initializing the S-box table with the private key; and phase 3 for the encrypting/decrypting operation (including determination of an X byte and an XOR operation).
It should be understood that Phase 2 of the algorithm includes the two steps of: (phase 2a) filling an S-box table (256×8) linearly: So=0, S1=1, . . . ,S255=255; and then (phase 2b) initializing the S-box table by scrambling the table with the private key, repeating the key as necessary to address all 256 locations in the array. For example, if a 16 byte key is used, the sequence would be: KEYo, KEY1, . . . ,KEY15, KEYo, KEY1, . . . ,KEY15, repeating this sequence a total of 16 times to complete the scrambling. It should be appreciated that the term “key” refers to a plurality of “key values.” In accordance with a preferred embodiment, each key value is a byte, and a key is comprised of 16 key values (i.e., 16 bytes). 16 bytes are required for 128-bit encryption. The key is a private key known only to the transmitter and receiver(s) of the encrypted data.
As indicated above, in Phase 2b of the RC4 algorithm the S-box table is initialized with the private key. In this regard, index j is set to zero, then:
For i=0 to 255:                j=(j+Si+KEYi) mod 256        swap Si and Sj         
In the third phase (phase 3), two counters, i and j, are initialized to zero to index through the 256×8 S-box in a pseudorandom fashion. Thereafter, random bytes X are generated as follows:                i=(i+1) mod 256        j=(j+Si) mod 256        Swap Si and Sj         t=(Si+Si) mod 256        X=St The foregoing code sequence is performed for every byte to be encrypted/decrypted. Being a symmetric cryptosystem, the same algorithm is used to decrypt or encrypt data depending on how the XOR data is used. In this regard, the byte X is XORed with plaintext to produce ciphertext or XORed with ciphertext to produce plaintext.        
Although the software implementation of the foregoing encryption algorithm appears simple in high level code, the software approach is slow. The software approach is too slow to meet the tight turn around time requirements of IEEE 802.11.
In view of the deficiencies of the software implementation, hardware modifications to the MAC processor have been used to accelerate operation of the algorithm. Referring now to FIG. 2, there is shown a MAC processor 10 according to the prior art. MAC processor 10 is generally comprised of a CPU 20, a key register 30, data path hardware engine 40, microcode controller system 50 (which includes a microcode controller and RAM), and S-Box RAM 100.
CPU 20 is the main processing device of MAC processor 10, and provides signals for controlling operation of key register 30 and microcode controller system 50. Keys are commonly stored in “off-chip” RAM since they are large (often 128 bits or more), and there are many keys that might be used to decrypt and encrypt data depending on the source and destination of the packet address. Therefore, in the prior art a small on-chip key register 30 is used to hold the current key bytes being used. Key register 30 is loaded by using register decodes under the direction of software. Therefore, once the proper key is found, software can load the key and start phase 2 of the encryption algorithm discussed above. Data path hardware engine 40 provides an 8-bit wide data path for performing data manipulation for the RC4 algorithm. Data path hardware engine 40 includes elements such as registers, adders, multiplexers, etc., used to read key register 30 and read/write the S-box table RAM 100. Microcode controller system 50 is used to control the data path to execute the operations needed to execute the RC4 algorithm. S-box table RAM 100 is an “on-chip” RAM (i.e., RAM located on the MAC processor chip) which stores the S-box table. The use of an “on-chip” RAM allows for faster initialization and XOR byte generation than obtained with off-chip memory access.
By using the above-mentioned hardware, the prior art takes a total of 1280 (R/W) microcode operations in order to perform the initialization of the S-box table. In addition, the prior art requires that key loading is totally complete before starting the phase 2b initialization operation. However, phase 2a can be executed at any time since the linear fill of the S-box table does not depend on the key. It should be understood that phase 2a must complete before launching phase 2b.
The present invention provides enhancements to the hardware arrangement in order to further improve the speed of the encryption/decryption operations.
USPTO Backgrounds
USPTO Backgrounds