What is RC4?
The RC4 Encryption Algorithm, developed by Ronald Rivest of RSA, is a shared key stream cipher algorithm requiring a secure exchange of a shared key. RC4 is no longer considered secure and careful consideration should be taken regarding it’s use. The symmetric key algorithm is used identically for encryption and decryption such that the data stream is simply XORed with the generated key sequence. The algorithm is serial as it requires successive exchanges of state entries based on the key sequence. Hence implementations can be very computationally intensive. The RC4 encryption algorithm is used by standards such as IEEE 802.11 within WEP (Wireless Encryption Protocol) using 40 and 128-bit keys. Published procedures exist for cracking the security measures as implemented in WEP.
- IEEE 802.11
- Wireless Encryption Protocol
- Communications Software
- Communications Design
- Secure Reference Designs
RC4 Algorithm
In the RC4 encryption algorithm, the key stream is completely independent of the plaintext used. An 8 * 8 S-Box (S0 S255), where each of the entries is a permutation of the numbers 0 to 255, and the permutation is a function of the variable length key. There are two counters i, and j, both initialized to 0 used in the algorithm.
The algorithm uses a variable length key from 1 to 256 bytes to initialize a 256-byte state table. The state table is used for subsequent generation of pseudo-random bytes and then to generate a pseudo-random stream which is XORed with the plaintext to give the ciphertext. Each element in the state table is swapped at least once.
The key is often limited to 40 bits, because of export restrictions but it is sometimes used as a 128 bit key. It has the capability of using keys between 1 and 2048 bits. RC4 is used in many commercial software packages such as Lotus Notes and Oracle Secure SQL.
The algorithm works in two phases, key setup and ciphering. Key setup is the first and most difficult phase of this encryption algorithm. During a N-bit key setup (N being your key length), the encryption key is used to generate an encrypting variable using two arrays, state and key, and N-number of mixing operations. These mixing operations consist of swapping bytes, modulo operations, and other formulas. A modulo operation is the process of yielding a remainder from division. For example, 11/4 is 2 remainder 3; therefore eleven mod four would be equal to three.
Strengths of RC4
- The difficulty of knowing where any value is in the table.
- The difficulty of knowing which location in the table is used to select each value in the sequence.
- Encryption is about 10 times faster than DES.
Limitations of RC4
- RC4 is no longer considered secure.
- One in every 256 keys can be a weak key. These keys are identified by cryptanalysis that is able to find circumstances under which one of more generated bytes are strongly correlated with a few bytes of the key.
- A particular RC4 Algorithm key can be used only once.
Performance
- Each of the UDI implementations is a hardware block specifically designed for the implementation. RAM space is required by the key byte generator to locally maintain the state table for key generation. This state would need to be preserved and restored in case of a context switch if other processes would need the same functionality. This overhead is not considered in the above performance projections. Encryption and decryption state data may be stored in separate state memories to allow for independent processes.
- The following table summarizes the number of MIPS required for the algorithm encryption/decryption for 1 million bits per second for each of the three implementations.
| MIPS | RAM | |
|---|---|---|
| Optimized MIPS Assembly | 2.5 | none |
| RC4 Operation Support UDI Primitives | 1.75 | 0 bytes |
| RC4 Key Byte Generator UDI Accelerator | 0.22 | 256 bytes |
RC4 Software
The VOCAL implementation of the RC4 algorithm is available in several forms. The forms include pure optimized software and varying levels of hardware complexity utilizing UDI instructions for improved performance. When special assistance hardware is not available (as is the case on most general purpose processors), the byte manipulation/exchange operations are implemented via software.
