RC4
this wiki
Template:Infobox Encryption method
In cryptography, RC4 (also known as ARC4 or ARCFOUR meaning Alleged RC4, see below) is the most widelyused software stream cipher and is used in popular protocols such as Secure Sockets Layer (SSL) (to protect Internet traffic) and WEP (to secure wireless networks). While remarkable for its simplicity and speed in software, RC4 has weaknesses that argue against its use in new systems.^{[1]} It is especially vulnerable when the beginning of the output keystream is not discarded, or nonrandom or related keys are used; some ways of using RC4 can lead to very insecure cryptosystems such as WEP.
HistoryEdit
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"^{[2]} (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.^{[3]} It was soon posted on the sci.crypt newsgroup, and from there to many sites on the Internet. The leaked code was confirmed to be genuine as its output was found to match that of proprietary software using licensed RC4. Because the algorithm is known, it is no longer a trade secret. The name "RC4" is trademarked, so RC4 is often referred to as "ARCFOUR" or "ARC4" (meaning Alleged RC4) to avoid trademark problems. RSA Security has never officially released the algorithm; Rivest has, however, linked to the English Wikipedia article. on RC4 in his own course notes.^{[4]} RC4 has become part of some commonlyused encryption protocols and standards, including WEP and WPA for wireless cards and TLS.
The main factors in RC4's success over such a wide range of applications are its speed and simplicity: efficient implementations in both software and hardware are very easy to develop.
DescriptionEdit
RC4 generates a pseudorandom stream of bits (a keystream). As with any stream cipher, these can be used for encryption by combining it with the plaintext using bitwise exclusiveor; decryption is performed the same way (since exclusiveor is a symmetric operation). (This is similar to the Vernam cipher except that generated pseudorandom bits, rather than a prepared stream, are used.) To generate the keystream, the cipher makes use of a secret internal state which consists of two parts:
 A permutation of all 256 possible bytes (denoted "S" below).
 Two 8bit indexpointers (denoted "i" and "j").
The permutation is initialized with a variable length key, typically between 40 and 256 bits, using the keyscheduling algorithm (KSA). Once this has been completed, the stream of bits is generated using the pseudorandom generation algorithm (PRGA).
The keyscheduling algorithm (KSA)Edit
The keyscheduling algorithm is used to initialize the permutation in the array "S". "keylength" is defined as the number of bytes in the key and can be in the range 1 ≤ keylength ≤ 256, typically between 5 and 16, corresponding to a key length of 40 – 128 bits. First, the array "S" is initialized to the identity permutation. S is then processed for 256 iterations in a similar way to the main PRGA, but also mixes in bytes of the key at the same time.
for i from 0 to 255 S[i] := i endfor j := 0 for i from 0 to 255 j := (j + S[i] + key[i mod keylength]) mod 256 swap values of S[i] and S[j] endfor
The pseudorandom generation algorithm (PRGA)Edit
For as many iterations 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 element of S at the location S[i] + S[j] (modulo 256). Each element of S is swapped with another element at least once every 256 iterations.i := 0 j := 0 while GeneratingOutput: i := (i + 1) mod 256 j := (j + S[i]) mod 256 swap values of S[i] and S[j] K := S[(S[i] + S[j]) mod 256] output K endwhile
ImplementationEdit
Many stream ciphers are based on linear feedback shift registers (LFSRs), which while efficient in hardware are less so in software. The design of RC4 avoids the use of LFSRs, and is ideal for software implementation, as it requires only byte manipulations. It uses 256 bytes of memory for the state array, S[0] through S[255], k bytes of memory for the key, key[0] through key[k1], and integer variables, i, j, and y. Performing a modular reduction of some value modulo 256 can be done with a bitwise AND with 255 (which is equivalent to taking the loworder byte of the value in question).
Here is a simple implementation in C: Template:Section OR
unsigned char S[256]; unsigned int i, j; void swap(unsigned char *s, unsigned int i, unsigned int j) { unsigned char temp = s[i]; s[i] = s[j]; s[j] = temp; } /* KSA */ void rc4_init(unsigned char *key, unsigned int key_length) { for (i = 0; i < 256; i++) S[i] = i; for (i = j = 0; i < 256; i++) { j = (j + key[i % key_length] + S[i]) & 255; swap(S, i, j); } i = j = 0; } /* PRGA */ unsigned char rc4_output() { i = (i + 1) & 255; j = (j + S[i]) & 255; swap(S, i, j); return S[(S[i] + S[j]) & 255]; } #include <stdio.h> int main() { int k, output_length; unsigned char key[] = "Secret"; // key hardcoded to "Secret" output_length = 10; // number of bytes of output desired rc4_init(key, 6); // length of key is 6 in this case k = 0; while (k < output_length) { printf("%c", rc4_output()); k++; } }
Test vectorsEdit
These test vectors are not official, but convenient for anyone testing their own RC4 program. The keys and plaintext are ASCII, the ciphertext is in hexadecimal.
Key  Keystream  Plaintext  Ciphertext 

Key  eb9f7781b734ca72a719...  Plaintext  BBF316E8D940AF0AD3 
Wiki  6044db6d41b7...  pedia  1021BF0420 
Secret  04d46b053ca87b59...  Attack at dawn  45A01F645FC35B383552544B9BF5 
SecurityEdit
Unlike a modern stream cipher (such as those in eSTREAM), RC4 does not take a separate nonce alongside the key. This means that if a single longterm key is to be used to securely encrypt multiple streams, the cryptosystem must specify how to combine the nonce and the longterm key to generate the stream key for RC4. One approach to addressing this is to generate a "fresh" RC4 key by hashing a longterm key with a nonce. However, many applications that use RC4 simply concatenate key and nonce; RC4's weak key schedule then gives rise to a variety of serious problems.
Encryption using RC4 as described earlier is malleable (this is not a weakness of RC4, but a weakness of the encryption scheme itself), and vulnerable to a bitflipping attack. To prevent this, the encryption scheme should be used together with a strong message authentication code.
Roos' Biases and Key Reconstruction from PermutationEdit
In 1995, Andrew Roos experimentally observed that the first byte of the keystream is correlated to the first three bytes of the key and the first few bytes of the permutation after the KSA are correlated to some linear combination of the key bytes.^{[5]} These biases remained unproved until 2007, when Paul, Rathi and Maitra^{[6]} proved the keystreamkey correlation and Paul and Maitra proved the permutationkey correlations.^{[7]} The latter work also used Roos' permutationkey correlations to design the first algorithm for complete key reconstruction from the final permutation after the KSA, without any assumption on the key or IV. This algorithm has a constant probability of success in a time which is the square root of the exhaustive key search complexity. Subsequently, many other works have been done on key reconstruction from RC4 internal states.^{[8]}^{[9]}^{[10]} In another work, Maitra and Paul^{[11]} showed that the Roos type biases still persist even when one considers nested permutation indices, like S[S[i]]
or S[S[S[i]]]
. These types of biases are used in some of the later key reconstruction methods for increasing the success probability.
Biased Outputs of the RC4Edit
The keystream generated by the RC4 is biased in varying degrees towards certain sequences. The best such attack is due to Itsik Mantin and Adi Shamir who showed that the second output byte of the cipher was biased toward zero with probability 1/128 (instead of 1/256). This is due to the fact that if the third byte of the original state is zero, and the second byte is not equal to 2, then the second output byte is always zero. Such bias can be detected by observing only 256 bytes.^{[12]}
Souradyuti Paul and Bart Preneel of COSIC showed that the first and the second bytes of the RC4 were also biased. The number of required samples to detect this bias is 2^{25} bytes.^{[13]}
Fluhrer and McGrew also showed such attacks which distinguished the keystream of the RC4 from a random stream given a gigabyte of output.^{[14]}
The complete characterization of a single step of RC4 PRGA was performed by Basu, Ganguly, Maitra and Paul.^{[15]} Considering all the permutations, they prove that the distribution of the output is not uniform given i and j, and as a consequence, information about j is always leaked from the output.
Fluhrer, Mantin and Shamir attackEdit
 Main article: Fluhrer, Mantin and Shamir attack
In 2001, a new and surprising discovery was made by Fluhrer, Mantin and Shamir: over all possible RC4 keys, the statistics for the first few bytes of output keystream are strongly nonrandom, leaking information about the key. If the longterm key and nonce are simply concatenated to generate the RC4 key, this longterm key can be discovered by analysing a large number of messages encrypted with this key.^{[16]} This and related effects were then used to break the WEP ("wired equivalent privacy") encryption used with 802.11 wireless networks. This caused a scramble for a standardsbased replacement for WEP in the 802.11 market, and led to the IEEE 802.11i effort and WPA.^{[17]}
Cryptosystems can defend against this attack by discarding the initial portion of the keystream. Such a modified algorithm is traditionally called "RC4drop[n]", where n is the number of initial keystream bytes that are dropped. The SCAN default is n = 768 bytes, but a conservative value would be n = 3072 bytes.^{[18]}
Klein's Attack Edit
In 2005, Andreas Klein presented an analysis of the RC4 stream cipher showing more correlations between the RC4 keystream and the key.^{[19]} Erik Tews, RalfPhilipp Weinmann, and Andrei Pychkine used this analysis to create aircrackptw, a tool which cracks 104bit RC4 used in 128bit WEP in under a minute.^{[20]} Whereas the Fluhrer, Mantin, and Shamir attack used around 10 million messages, aircrackptw can break 104bit keys in 40,000 frames with 50% probability, or in 85,000 frames with 95% probability.
Combinatorial problem Edit
A combinatorial problem related to the number of inputs and outputs of the RC4 cipher was first posed by Itsik Mantin and Adi Shamir in 2001, whereby, of the total 256 elements in the typical state of RC4, if x number of elements (x ≤ 256) are only known (all other elements can be assumed empty), then the maximum number of elements that can be produced deterministically is also x in the next 256 rounds. This conjecture was put to rest in 2004 with a formal proof given by Souradyuti Paul and Bart Preneel.^{[21]}
RC4based cryptosystemsEdit
 WEP
 WPA (default algorithm, but can be configured to use AESCCMP instead of RC4)
 BitTorrent protocol encryption
 Microsoft PointtoPoint Encryption
 Opera Mini^{[22]}
 Secure Sockets Layer (optionally)
 Secure shell (optionally)
 Remote Desktop Protocol
 Kerberos (optionally)
 SASL Mechanism DigestMD5 (optionally)
 Gpcode.AK, an early June 2008 computer virus for Microsoft Windows, which takes documents hostage for ransom by obscuring them with RC4 and RSA1024 encryption
 Skype (in modified form)^{[23]}
Where a cryptosystem is marked with "(optionally)", RC4 is one of several ciphers the system can be configured to use.
See alsoEdit
 eSTREAM  An evaluation of new stream ciphers being conducted by the EU.
 TEA, Block TEA also known as eXtended TEA and Corrected Block TEA  A family of block ciphers that, like RC4, are designed to be very simple to implement.
 Advanced Encryption Standard
 CipherSaber
ReferencesEdit
 ↑ "RC4 Page" lists some of the biases
 ↑ Rivest FAQ
 ↑ Template:Cite mailing listTemplate:Dead link
 ↑ 6.857 Computer and Network Security Spring 2008: Lectures and Handouts
 ↑ Andrew Roos. A Class of Weak Keys in the RC4 Stream Cipher. Two posts in sci.crypt, messageid 43u1eh$1j3@hermes.is.co.za and 44ebge$llf@hermes.is.co.za, 1995. Available at http://groups.google.com/group/sci.crypt.research/msg/078aa9249d76eacc?dmode=source.
 ↑ Goutam Paul, Siddheshwar Rathi and Subhamoy Maitra. On Nonnegligible Bias of the First Output Byte of RC4 towards the First Three Bytes of the Secret Key. Proceedings of the International Workshop on Coding and Cryptography (WCC) 2007, pages 285294 and Designs, Codes and Cryptography Journal, pages 123134, vol. 49, no. 13, December 2008.
 ↑ Goutam Paul and Subhamoy Maitra. Permutation after RC4 Key Scheduling Reveals the Secret Key. SAC 2007, pages 360377, vol. 4876, Lecture Notes in Computer Science, Springer.
 ↑ Eli Biham and Yaniv Carmeli. Efficient Reconstruction of RC4 Keys from Internal States. FSE 2008, pages 270288, vol. 5086, Lecture Notes in Computer Science, Springer.
 ↑ Mete Akgun, Pinar Kavak, Huseyin Demirci. New Results on the Key Scheduling Algorithm of RC4. INDOCRYPT 2008, pages 4052, vol. 5365, Lecture Notes in Computer Science, Springer.
 ↑ Riddhipratim Basu, Subhamoy Maitra, Goutam Paul and Tanmoy Talukdar. On Some Sequences of the Secret Pseudorandom Index j in RC4 Key Scheduling. Proceedings of the 18th International Symposium on Applied Algebra, Algebraic Algorithms and Error Correcting Codes (AAECC), June 8–12, 2009, Tarragona, Spain, pages 137148, vol. 5527, Lecture Notes in Computer Science, Springer.
 ↑ Subhamoy Maitra and Goutam Paul. New Form of Permutation Bias and Secret Key Leakage in Keystream Bytes of RC4. Proceedings of the 15th Fast Software Encryption (FSE) Workshop, February 10–13, 2008, Lausanne, Switzerland, pages 253269, vol. 5086, Lecture Notes in Computer Science, Springer.
 ↑ Itsik Mantin and Adi Shamir, A Practical Attack on Broadcast RC4. FSE 2001, pp152 – 164 (PS).
 ↑ Souradyuti Paul and Bart Preneel, Analysis of Nonfortuitous Predictive States of the RC4 Keystream Generator. INDOCRYPT 2003, pp52 – 67 (PDF).
 ↑ Scott R. Fluhrer and David A. McGrew, Statistical Analysis of the Alleged RC4 Keystream Generator. FSE 2000, pp19 – 30 (PDF)
 ↑ Riddhipratim Basu, Shirshendu Ganguly, Subhamoy Maitra, and Goutam Paul. A Complete Characterization of the Evolution of RC4 Pseudo Random Generation Algorithm. Journal of Mathematical Cryptology, pages 257289, vol. 2, no. 3, October, 2008.
 ↑ Scott R. Fluhrer, Itsik Mantin and Adi Shamir, Weaknesses in the Key Scheduling Algorithm of RC4. Selected Areas in Cryptography 2001, pp1 – 24 (PS).
 ↑ Interim technology for wireless LAN security: WPA to replace WEP while industry develops new security standard
 ↑ "RC4drop(nbytes)" in the "Standard Cryptographic Algorithm Naming" database
 ↑ A. Klein, Attacks on the RC4 stream cipher, Designs, Codes and Cryptography (2008) 48:269286
 ↑ Erik Tews, RalfPhilipp Weinmann, Andrei Pyshkin. Breaking 104bit WEP in under a minute.
 ↑ Souradyuti Paul and Bart Preneel, A New Weakness in the RC4 Keystream Generator and an Approach to Improve the Security of the Cipher. Fast Software Encryption  FSE 2004, pp245 – 259 (PDF).
 ↑ http://www.opera.com/mobile/help/faq/#security
 ↑ Template:Cite web
External linksEdit
RC4
 IETF Draft  A Stream Cipher Encryption Algorithm "Arcfour"
 Original posting of RC4 algorithm to Cypherpunks mailing list
 SCAN's entry for RC4
 Attacks on RC4
 RC4  Cryptology Pointers by Helger Lipmaa
 RSA Security Response to Weaknesses in Key Scheduling Algorithm of RC4
 TSQL implementation
RC4 in WEP

cs:RC4 de:RC4 es:RC4 fr:RC4 ko:RC4 hr:RC4 it:RC4 he:RC4 nl:RC4 (encryptie) ja:RC4 pl:RC4 pt:RC4 ru:RC4 simple:RC4 sl:RC4 fi:RC4