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 long-term key is to be used to securely encrypt multiple streams, the protocol must specify how to combine the nonce and the long-term key to generate the stream key for RC4. One approach to addressing this is to generate a "fresh" RC4 key by
hashing a long-term key with a
nonce. However, many applications that use RC4 simply concatenate key and nonce; RC4's weak
key schedule then gives rise to
related-key attacks, like the
Fluhrer, Mantin and Shamir attack (which is famous for breaking the
WEP standard). Because RC4 is a
stream cipher, it is more
malleable than common
block ciphers. If not used together with a strong
message authentication code (MAC), then encryption is vulnerable to a
bit-flipping attack. The cipher is also vulnerable to a
stream cipher attack if not implemented correctly. It is noteworthy, however, that RC4, being a stream cipher, was for a period of time the only common cipher that was immune to the 2011
BEAST attack on
TLS 1.0. The attack exploits a known weakness in the way
cipher-block chaining mode is used with all of the other ciphers supported by TLS 1.0, which are all block ciphers. In March 2013, there were new attack scenarios proposed by Isobe, Ohigashi, Watanabe and Morii, as well as AlFardan, Bernstein, Paterson, Poettering and Schuldt that use new statistical biases in RC4 key table to recover plaintext with large number of TLS encryptions. The use of RC4 in TLS is prohibited by RFC 7465 published in February 2015.
Roos' biases and key reconstruction from permutation In 1995, Andrew Roos experimentally observed that the first byte of the keystream is correlated with the first three bytes of the key, and the first few bytes of the permutation after the KSA are correlated with some linear combination of the key bytes. These biases remained unexplained until 2007, when Goutam Paul, Siddheshwar Rathi and Subhamoy Maitra proved the keystream–key correlation and, in another work, Goutam Paul and Subhamoy Maitra proved the permutation–key correlations. The latter work also used the permutation–key correlations to design the first algorithm for complete key reconstruction from the final permutation after the KSA, without any assumption on the key or
initialization vector. 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 performed on key reconstruction from RC4 internal states. Subhamoy Maitra and Goutam Paul also showed that the Roos-type biases still persist even when one considers nested permutation indices, like or . These types of biases are used in some of the later key reconstruction methods for increasing the success probability.
Biased outputs of the RC4 The keystream generated by the RC4 is biased to varying degrees towards certain sequences, making it vulnerable to
distinguishing attacks. 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.
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 225 bytes.
Scott Fluhrer and David McGrew also showed attacks that distinguished the keystream of the RC4 from a random stream given a gigabyte of output. The complete characterization of a single step of RC4 PRGA was performed by Riddhipratim Basu, Shirshendu Ganguly, Subhamoy Maitra, and Goutam Paul. Considering all the permutations, they proved that the distribution of the output is not uniform given i and j, and as a consequence, information about j is always leaked into the output.
Fluhrer, Mantin and Shamir attack In 2001, a new and surprising discovery was made by
Fluhrer,
Mantin and
Shamir: over all the possible RC4 keys, the statistics for the first few bytes of output keystream are strongly non-random, leaking information about the key. If the nonce and long-term key are simply concatenated to generate the RC4 key, this long-term key can be discovered by analysing 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. 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. Protocols can defend against this attack by discarding the initial portion of the keystream. Such a modified algorithm is traditionally called "RC4-drop[]", where is the number of initial keystream bytes that are dropped. The SCAN default is = 768 bytes, but a conservative value would be = 3072 bytes. The Fluhrer, Mantin and Shamir attack does not apply to RC4-based SSL, since SSL generates the encryption keys it uses for RC4 by hashing, meaning that different SSL sessions have unrelated keys.
Klein's attack In 2005, Andreas Klein presented an analysis of the RC4 stream cipher, showing more correlations between the RC4 keystream and the key.
Erik Tews,
Ralf-Philipp Weinmann, and
Andrei Pychkine used this analysis to create aircrack-ptw, a tool that cracks 104-bit RC4 used in 128-bit WEP in under a minute. Whereas the Fluhrer, Mantin, and Shamir attack used around 10 million messages, aircrack-ptw can break 104-bit keys in 40,000 frames with 50% probability, or in 85,000 frames with 95% probability.
Combinatorial problem 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 in the next 256 rounds. This conjecture was put to rest in 2004 with a formal proof given by
Souradyuti Paul and
Bart Preneel.
Royal Holloway attack In 2013, a group of security researchers at the Information Security Group at
Royal Holloway, University of London reported an attack that can become effective using only 234 encrypted messages. While not yet a practical attack for most purposes, this result is sufficiently close to one that it has led to speculation that it is plausible that some state cryptologic agencies may already have better attacks that render RC4 insecure. Given that a large amount of
TLS traffic in 2013 used RC4 to avoid attacks on block ciphers that use
cipher block chaining, if these hypothetical better attacks existed, then typical TLS encryption would be insecure against such attackers in a large number of practical scenarios.
Bar mitzvah attack At the Black Hat Asia 2015 Conference, Itsik Mantin presented another attack against SSL using RC4 cipher.
NOMORE attack In 2015, security researchers from
KU Leuven presented new attacks against RC4 in both
TLS and
WPA-TKIP. Dubbed the Numerous Occurrence MOnitoring & Recovery Exploit (NOMORE) attack, it is the first attack of its kind that was demonstrated in practice. Their attack against
TLS can decrypt a secure
HTTP cookie within 75 hours. The attack against WPA-TKIP can be completed within an hour and allows an attacker to decrypt and inject arbitrary packets. ==RC4 variants==