RC4 Guide, Meaning , Facts, Information and Description
- For the Vietnam road named RC4, see Route Coloniale 4.
History
RC4 was designed by Ron Rivest of RSA Security in 1987; while it is officially termed "Rivest Cipher 4", the RC acronym is alternatively understood to stand for "Ron's Code" (see also RC2, RC5 and RC6).
RC4 was initially a trade secret, but in September 1994 a description of it was anonymously posted to the Cypherpunks mailing list. It was soon posted on the sci.crypt newsgroup, and from there to many sites on the Internet. Because the algorithm is known, it is no longer a trade secret. The name "RC4" is trademarked, however. The current status seems to be that "unofficial" implementations are legal, but cannot use the RC4 name. RC4 is often referred to as "ARCFOUR", to avoid possible trademark problems. It has become part of some commonly used encryption protocols and standards, including WEP and WPA for wireless cards and SSL.
RC4 generates a pseudorandom stream of bits (a "keystream") which, for encryption, is combined with the plaintext using XOR; decryption is performed the same way. To generate the keystream, the cipher makes use of a secret internal state which consists of two parts:
Description
The permutation is initialised with a variable length key, typically between 40 and 256 bits, using the key-scheduling algorithm (KSA). Once this has been completed, the stream of bits is generated using the pseudo-random generation algorithm (PRGA).
The pseudo-random generation algorithm (PRGA)
For as many iteration as are needed, the PRGA modifies the state and outputs a byte of the keystream. In each iteration, the PRGA increments i, adds the value of S pointed to by i to j, exchanges the values of S[i] and S[j], and then outputs the value of of S at the location S[i] + S[j] (modulo 256). Each value of S is swapped at least once every 256 iterations. i := 0
j := 0
while GeneratingOutput:
i := (i + 1) mod 256
j := (j + S[i]) mod 256
swap(S[i],S[j])
output S[(S[i] + S[j]) mod 256]The key-scheduling algorithm (KSA)
The key-scheduling algorithm is used to initialise the permutation in the array "S". "l" is defined as the number of bytes in the key and can be in the range 1 ≤ l ≤ 255, typically between 5 and 32, corresponding to a key length of 40–128 bits. First, the array "S" is initialised to the identity permutation. S is then processed for 256 iterations in a similar way to the main PRGA algorithm, but also mixes in bytes of the key at the same time.
for i from 0 to 255
S[i] := i
j: = 0
for i from 0 to 255
j := (j + S[i] + key[i mod l]) mod 256
swap(S[i],S[j])
Implementation
Many stream ciphers are based on linear feedback shift registers (LFSRs), and, while efficient in hardware, are much slower in software. The design of RC4 is quite different, and is ideal for software implementations, as it requires only byte-length manipulations. It uses 256 bytes of memory for the state array, S[0] through S[255], n bytes of memory for the key, key[0] through key[n-1], and integer variables, i, j, and k. Performing a modulus 256 can be done with a bitwise AND with 255 (or on some platforms, simple addition of bytes ignoring overflow). Note that it is strongly recommended that the first outputs of this generator be discarded and not used to encrypt messages (at least 256 discards are recommended for maximum security.) Failure to do so can expose messages to an attack in which the RC4 key can be exposed (see "Fluhrer, Mantin and Shamir Attack" below).
Cryptanalysis of RC4 is at a rather uncertain stage. When correctly used, theoretical breaks may be possible if gigabytes of the keystream is available, but this is not necessarily a major problem in practice.
In 2001 a new and surprising discovery was made: over all possible RC4 keys, the statistics for the first few bytes of output keystream are strongly non-random. As a result, it is possible to discover the RC4 key if one possesses a large number of messages encrypted with this key. This and related effects were then used to break the WEP ("wired equivalent privacy") encryption used with 802.11 wireless networks. WEP employed RC4 with many similar keys, opening it to attack. This caused a scramble for a standards-based replacement for WEP in the 802.11 market, and led to the IEEE 802.11i effort and WPA.
One way to avoid these problems is to discard the first 256 bytes or more of the RC4 cipher stream.
As with all stream ciphers, RC4 is easily broken if the same key is used twice. This problem is usually solved by hashing the key with a unique initialization vector (IV) each time it is used, and sending the IV along with the message.
This is an Article on RC4. Page Contains Information, Facts Details or Explanation Guide About RC4 Security
Fluhrer, Mantin and Shamir Attack
See also
References
External links
RC4
RC4 in WEP
Implementations