RC4

General
RC4 is a stream cipher designed in RSA laboratories by Ron Rivest in 1987. This cipher is widely used in commercial applications including Oracle SQL, Microsoft Windows and the SSL. The algorithm is kept as a trade secret until these days. The external analysis of RC4 was invoked by the leakage of its source code in 1994 to cypherpunks mailing list. The key stream generated by RC4 is a stream of pseudo-random bytes.

Conferences Papers

• Linear Statistical Weakness of Alleged RC4 Key stream Generator, Golic, EUROCRYPT 1997 - this paper includes analysis of RC4 stream distribution in the linear model, and indicates a small linear statistical bias in the second derivative of the LSB.
• Analysis Methods for (Alleged) RC4,  Knudsen, Meier, Preneel, Rijmen and Verdoolaege, ASIACRYPT 1998 - this paper applies several analysis methods to RC4. Non of these methods seem to be applicable to the real RC4. One of the methods described in this paper is a tracking algorithm, which is actually the real brute force attack, that should be considered on RC4. Anyone who is interested in RC4, and would like to understand the difficulties of RC4, should consider this paper.
• Cryptanalysis of RC4-like Ciphers, Mister and Tavares, SAC 1998 - like the previous one (that were published almost together) this paper analyzes applying the tracking algorithm to RC4. This paper also includes an analysis of the cycles structure of RC4 round operation, within the domain of RC4 states.
• Statistical Analysis of the Alleged RC4 Key stream Generator, Fluhrer and McGrew, FSE 2000 - this paper describes the best known distinguisher of a single RC4 stream from a random stream ($2^{30}$). The statistical behavior for which this distinguisher is based on, is the biased distribution of triplets, which are the index ($i$) and pairs of outputs, which are negatively or positively biased. An interesting and useful observation made in this paper, is the discovery of a class special states denoted as fortuitous states, which are the origin of the above biases. These states can be used to reveal non negligible parts of RC4 internal state, with non-trivial probability.
• A Practical Attack on Broadcast RC4, Mantin and Shamir, FSE 2001 - the main result mentioned in this paper, is the discovery of the exceptionally biased behavior of the second word of RC4 streams, which takes 0 with probability that is twice the expected (1/128 instead of 1/256). This paper also generalizes the definition of fortuitous states, and defines $b$-predictive $a$-states, that is partial states that are sufficient for determining some of the outputs.
• Weaknesses in the Key Scheduling Algorithm of RC4, Fluhrer, Mantin and Shamir, SAC 2001 - this paper describes two weaknesses in the KSA of RC4 (the mechanism that extends a short key into a huge key of 1700 bits), denoted as the invariance weakness and the IV weakness. The invariance weakness is the existence of specific patterns, which are invariant with respect to the KSA. In other words, when these patterns appear in RC4 keys, they are probable to appear also in the generated permutation. Furthermore, these patterns propagate into the generated stream and consequently their occurrences (in the secret key) can be easily isolated by simple analysis of the stream (sometimes the ciphertext itself suffice). The IV weakness, is related to a popular mode of operation of stream ciphers, where in order to avoid reusing the key, it is combined with a known vector (denoted the initialization vector or the IV) and this combination is used as the seed to the key stream generator. This paper describes a practical ciphertext only attack on this mode of operation of RC4, when the combination of the key and the IV is made in a simple method such as concatenation. An interesting point is that this mode of operation is commonly used in the WEP (wired equivalent protocol) which is a part of the 802.11 standard, and this attack is applicable not only on the current (at that time) version of WEP, but also on the enhanced version WEP2.
• Using the Fluhrer, Mantin, and Shamir Attack to Break WEP, Stubblefield, Loannidis, and Rubin, AT&T Labs Technical Report 2001 - An immediate consequence of the above paper was an implementation of the methods described there by a team from AT&T. This paper describes this implementation and its bottom line is that from analyzing 6,000,000 encrypted messages, the algorithm completely recovered the secret key.
• Analysis of the Stream Cipher RC4, Itsik Mantin, Master’s Thesis, Weizmann Institute of Science, 2001 – My Master’s thesis. Except of a detailed description of my work (some of which was never formally published), it overviews all the published results on the security of RC4 in details. The introduction (the document is almost 100 pages long) is a great starting point for anyone who wants to understand the weaknesses on one hand and the robustness on the other hand of RC4. A double-space version is also available. 
• Attacks on RC4 and WEP, Fluhrer, Mantin and Shamir, Cryptobytes 2002 – A shortened version of the WEP attack. 

·ISAAC and RC4, Robert J. Jenkins

·Paul Crowley's RC4 page

Others

• An RC4 cycle that can't happen, H. Finney, 1994 - the domain of RC4 states contains a class of states which are concatenated through a set of short cycles, of size $256 \cdot 255$. A fraction approximately $2^{-16}$ of RC4 states belong to this class. These states are classified by: $i=a$, $j=a+1$, $S[a+1]=1$. Since RC4 initial state is not in the class, RC4 can never enter these cycles.
• My RC4 Weak Keys, D. Wagner, sci.crypt, 1995, A Class of Weak Keys in the RC4 Stream Cipher, A. Roos, 1995 - Wagner and Roos identified the connection between the first KSA rounds and the first output bytes. They formalized this connection in two different ways, when I state here only the one of Roos. Roos found that whenever $K[0]+K[1]=0$, the first output word is $K[2]+3$ with probability $2^{-3}$. The consequence is that 2 bytes of the key can be recovered with probability $2^{-11}$ which means that the exhaustive search on the key is reduced by 5 bits.
• A Related-Key Cryptanalysis of RC4, A. L. Grosul and D. S. Wallach, 200 - This paper describes related key attacks on RC4, when the secret key is extremely long.