RC4
[5] As of 2015[update], there is speculation that some state cryptologic agencies may possess the capability to break RC4 when used in the TLS protocol.
[6] IETF has published RFC 7465 to prohibit the use of RC4 in TLS;[3] Mozilla and Microsoft have issued similar recommendations.
While it is officially termed "Rivest Cipher 4", the RC acronym is alternatively understood to stand for "Ron's Code"[9] (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.
RSA Security has never officially released the algorithm; Rivest has, however, linked to the English Wikipedia article on RC4 in his own course notes in 2008[13] and confirmed the history of RC4 and its code in a 2014 paper by him.
The main factors in RC4's success over such a wide range of applications have been its speed and simplicity: efficient implementations in both software and hardware were very easy to develop.
To generate the keystream, the cipher makes use of a secret internal state which consists of two parts: The permutation is initialized with a variable-length key, typically between 40 and 2048 bits, using the key-scheduling algorithm (KSA).
[24] Many stream ciphers are based on linear-feedback shift registers (LFSRs), which, while efficient in hardware, are less so in software.
Unlike a modern stream cipher (such as those in eSTREAM), RC4 does not take a separate nonce alongside the key.
In March 2013, there were new attack scenarios proposed by Isobe, Ohigashi, Watanabe and Morii,[28] as well as AlFardan, Bernstein, Paterson, Poettering and Schuldt that use new statistical biases in RC4 key table[29] to recover plaintext with large number of TLS encryptions.
This algorithm has a constant probability of success in a time, which is the square root of the exhaustive key search complexity.
[35][36][37] Subhamoy Maitra and Goutam Paul[38] also showed that the Roos-type biases still persist even when one considers nested permutation indices, like S[S[i]] or S[S[S[i]]].
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).
[39] Scott Fluhrer and David McGrew also showed attacks that distinguished the keystream of the RC4 from a random stream given a gigabyte of output.
[40] The complete characterization of a single step of RC4 PRGA was performed by Riddhipratim Basu, Shirshendu Ganguly, Subhamoy Maitra, and Goutam Paul.
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.
[45] In 2005, Andreas Klein presented an analysis of the RC4 stream cipher, showing more correlations between the RC4 keystream and the key.
[46] 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.
[52] At the Black Hat Asia 2015 Conference, Itsik Mantin presented another attack against SSL using RC4 cipher.
Although stronger than RC4, this algorithm has also been attacked, with Alexander Maximov[58] and a team from NEC[59] developing ways to distinguish its output from a truly random sequence.
[61][59] RC4+ is a modified version of RC4 with a more complex three-phase key schedule (taking about three times as long as RC4, or the same as RC4-drop512), and a more complex output function which performs four additional lookups in the S array for each byte output, taking approximately 1.7 times as long as basic RC4.
[64] In 2017, Banik, Isobe, and Morii proprosed a simple fix that removes the distinguisher in the first two keystream bytes, requiring only one additional memory access without diminishing software performance substantially.
