| General | |
|---|---|
| Designers | Ron Rivest (RSA Security) |
| First published | Leaked in 1994 (designed in 1987) |
| Cipher detail | |
| Key sizes | 40–2048 bits |
| State size | 2064 bits (1684 effective) |
| Rounds | 1 |
| Speed | 7 cycles per byte onoriginal Pentium[1] Modified Alleged RC4 on Intel Core 2: 13.9 cycles per byte[2] |
Incryptography,RC4 (also known asARC4 orARCFOUR, meaning Alleged RC4, see below) is astream cipher. While it is remarkable for its simplicity and speed in software, multiple vulnerabilities have been discovered in RC4, rendering it insecure.[3][4] It is especially vulnerable when the beginning of the outputkeystream is not discarded, or when nonrandom or related keys are used. Particularly problematic uses of RC4 have led to very insecureprotocols such asWEP.[5]
As of 2015[update], there is speculation that some state cryptologic agencies may possess the capability to break RC4 when used in theTLS protocol.[6]IETF has published RFC 7465 to prohibit the use of RC4 in TLS;[3]Mozilla andMicrosoft have issued similar recommendations.[7][8]
A number of attempts have been made to strengthen RC4, notably Spritz, RC4A,VMPC, and RC4+.
RC4 is a stream cipher designed by Ronald Rivest of RSA Security in 1987. According to Rivest, the letters RC stand for “Ron's Code”[9], though in general it is simply referred to as RC4. The same naming convention applies to RC2, RC5, and RC6.
RC4 was initially atrade secret, but in September 1994, a description of it was anonymously posted to theCypherpunks mailing list.[10] It was soon posted on thesci.cryptnewsgroup, where it wasbroken within days byBob Jenkins.[11] From there, it spread 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 nameRC4 is trademarked, so RC4 is often referred to asARCFOUR orARC4 (meaningalleged RC4)[12] to avoid trademark problems.RSA Security has never officially released the algorithm; Rivest has, however, linked to theEnglish 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.[14]
RC4 became part of some commonly used encryption protocols and standards, such asWEP in 1997 andWPA in 2003/2004 for wireless cards; andSSL in 1995 and its successorTLS in 1999, until it was prohibited for all versions of TLS by RFC 7465 in 2015, due to theRC4 attacks weakening or breaking RC4 used in SSL/TLS. 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.
RC4 generates apseudorandom stream of bits (akeystream). As with any stream cipher, these can be used for encryption by combining it with the plaintext using bitwiseexclusive or; decryption is performed the same way (since exclusive or with given data is aninvolution). This is similar to theone-time pad, except that generatedpseudorandom 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:
The permutation is initialized with a variable-lengthkey, typically between 40 and 2048 bits, using thekey-scheduling algorithm (KSA). Once this has been completed, the stream of bits is generated using thepseudo-random generation algorithm (PRGA).
Thekey-scheduling 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 akey length of 40–128 bits. First, the array "S" is initialized to theidentity 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 ifrom 0to 255 S[i] := iendforj := 0for ifrom 0to 255 j := (j + S[i] + key[imod keylength]) mod 256 swap values of S[i] and S[j]endfor
For as many iterations as are needed, the PRGA modifies the state and outputs a byte of the keystream. In each iteration, the PRGA:
Each element of S is swapped with another element at least once every 256 iterations.
i := 0j := 0while GeneratingOutput: i := (i + 1) mod 256 j := (j + S[i]) mod 256swap values of S[i] and S[j] t := (S[i] + S[j]) mod 256 K := S[t] output Kendwhile
Thus, this produces a stream ofK[0], K[1], ... which areXORed with theplaintext to obtain theciphertext. Sociphertext[l] = plaintext[l] ⊕ K[l].
Severaloperating systems includearc4random, an API originating inOpenBSD providing access to a random number generator originally based on RC4. The API allows no seeding, as the function initializes itself using/dev/random. The use of RC4 has been phased out in most systems implementing this API.Man pages for the new arc4random include thebackronym "A Replacement Call for Random" for ARC4 as a mnemonic, as it provides better random data thanrand() does.[15]
arc4random was modified to useChaCha20.[16][17] The implementations of arc4random inFreeBSD,NetBSD[18][19] also use ChaCha20.Proposed new random number generators are often compared to the RC4 random number generator.[22][23]
Several attacks on RC4 are able todistinguish its output from a random sequence.[24]
Many stream ciphers are based onlinear-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[k−1], and integer variables, i, j, and K. Performing a modular reduction of some value modulo 256 can be done with abitwise AND with 255 (which is equivalent to taking the low-order byte of the value in question).
These test vectors are not official, but convenient for anyone testing their own RC4 program. The keys and plaintext areASCII, the keystream and ciphertext are inhexadecimal.
| Key | Keystream | Plaintext | Ciphertext |
|---|---|---|---|
| Key | EB9F7781B734CA72A719… | Plaintext | BBF316E8D940AF0AD3 |
| Wiki | 6044DB6D41B7… | pedia | 1021BF0420 |
| Secret | 04D46B053CA87B59… | Attack at dawn | 45A01F645FC35B383552544B9BF5 |
Unlike a modern stream cipher (such as those ineSTREAM), RC4 does not take a separatenonce 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 byhashing a long-term key with anonce. However, many applications that use RC4 simply concatenate key and nonce; RC4's weakkey schedule then gives rise torelated-key attacks, like theFluhrer, Mantin and Shamir attack (which is famous for breaking theWEP standard).[25]
Because RC4 is astream cipher, it is moremalleable than commonblock ciphers. If not used together with a strongmessage authentication code (MAC), then encryption is vulnerable to abit-flipping attack. The cipher is also vulnerable to astream cipher attack if not implemented correctly.[26]
It is noteworthy, however, that RC4, being a stream cipher, was for a period of time the only common cipher that was immune[27] to the 2011BEAST attack onTLS 1.0. The attack exploits a known weakness in the waycipher-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,[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.[30][31]
The use of RC4 in TLS is prohibited by RFC 7465 published in February 2015.
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.[32] These biases remained unexplained until 2007, when Goutam Paul, Siddheshwar Rathi and Subhamoy Maitra[33] proved the keystream–key correlation and, in another work, Goutam Paul and Subhamoy Maitra[34] 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 orinitialization 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.[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, likeS[S[i]] orS[S[S[i]]]. These types of biases are used in some of the later key reconstruction methods for increasing the success probability.
The keystream generated by the RC4 is biased to varying degrees towards certain sequences, making it vulnerable todistinguishing attacks. The best such attack is due to Itsik Mantin andAdi 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.[24]
Souradyuti Paul andBart Preneel ofCOSIC 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.[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.[41] 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.
In 2001, a new and surprising discovery was made byFluhrer,Mantin andShamir: 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.[42] This and related effects were then used to break theWEP ("wired equivalent privacy") encryption used with802.11wireless networks. This caused a scramble for a standards-based replacement for WEP in the 802.11 market and led to theIEEE 802.11i effort andWPA.[43]
Protocols can defend against this attack by discarding the initial portion of the keystream. Such a modified algorithm is traditionally called "RC4-drop[n]", wheren is the number of initial keystream bytes that are dropped. The SCAN default isn = 768 bytes, but a conservative value would ben = 3072 bytes.[44]
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.[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, andAndrei Pychkine used this analysis to create aircrack-ptw, a tool that cracks 104-bit RC4 used in 128-bit WEP in under a minute.[47] 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.
A combinatorial problem related to the number of inputs and outputs of the RC4 cipher was first posed byItsik Mantin andAdi Shamir in 2001, whereby, of the total 256 elements in the typical state of RC4, ifx number of elements (x ≤ 256) areonly known (all other elements can be assumed empty), then the maximum number of elements that can be produced deterministically is alsox in the next 256 rounds. This conjecture was put to rest in 2004 with a formal proof given bySouradyuti Paul andBart Preneel.[48]
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.[49][50][51] While yet not 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.[6] Given that, as of 2013[update], a large amount ofTLS traffic uses RC4 to avoid attacks on block ciphers that usecipher block chaining, if these hypothetical better attacks exist, then this would make the TLS-with-RC4 combination insecure against such attackers in a large number of practical scenarios.[6]
In March 2015, researcher to Royal Holloway announced improvements to their attack, providing a 226 attack against passwords encrypted with RC4, as used in TLS.[52]
At the Black Hat Asia 2015 Conference, Itsik Mantin presented another attack against SSL using RC4 cipher.[53][54]
In 2015, security researchers fromKU Leuven presented new attacks against RC4 in bothTLS andWPA-TKIP.[55] Dubbed the Numerous Occurrence MOnitoring & Recovery Exploit (NOMORE) attack, it is the first attack of its kind that was demonstrated in practice. Their attack againstTLS can decrypt a secureHTTP 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.
As mentioned above, the most important weakness of RC4 comes from the insufficient key schedule; the first bytes of output reveal information about the key. This can be corrected by simply discarding some initial portion of the output stream.[56] This is known as RC4-dropN, whereN is typically a multiple of 256, such as 768 or 1024.
A number of attempts have been made to strengthen RC4, notably Spritz, RC4A,VMPC, and RC4+.
Souradyuti Paul andBart Preneel have proposed an RC4 variant, which they call RC4A.[57]
RC4A uses two state arraysS1 andS2, and two indexesj1 andj2. Each timei is incremented, two bytes are generated:
Thus, the algorithm is:
All arithmetic is performed modulo 256i := 0j1 := 0j2 := 0while GeneratingOutput: i := i + 1 j1 := j1 + S1[i]swap values of S1[i] and S1[j1]output S2[S1[i] + S1[j1]] j2 := j2 + S2[i] swap values of S2[i] and S2[j2]output S1[S2[i] + S2[j2]]endwhile
Although the algorithm required the same number of operations per output byte, there is greater parallelism than RC4, providing a possible speed improvement.
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.
Variably Modified Permutation Composition (VMPC) is another RC4 variant.[60] It uses similar key schedule as RC4, withj := S[(j + S[i] + key[i mod keylength]) mod 256] iterating 3 × 256 = 768 times rather than 256, and with an optional additional 768 iterations to incorporate an initial vector. The output generation function operates as follows:
All arithmetic is performed modulo 256.i := 0while GeneratingOutput: j := S[j + S[i]]output S[S[S[j]] + 1] Swap S[i] and S[j](b := S[j]; S[j] := S[i]; S[i] := b)) i := i + 1endwhile
This was attacked in the same papers as RC4A, and can be distinguished within 238 output bytes.[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.[62]
All arithmetic modulo 256.<< and>> are left and right shift,⊕ is exclusive ORwhile GeneratingOutput: i := i + 1 a := S[i] j := j + a Swap S[i] and S[j](b := S[j]; S[j] := S[i]; S[i] := b;) c := S[i<<5 ⊕ j>>3] + S[j<<5 ⊕ i>>3]output (S[a+b] + S[c⊕0xAA]) ⊕ S[j+b]endwhile
This algorithm has not been analyzed significantly.
In 2014, Ronald Rivest gave a talk and co-wrote a paper[14] on an updated redesign called Spritz. A hardware accelerator of Spritz was published in Secrypt, 2016[63] and shows that due to multiple nested calls required to produce output bytes, Spritz performs rather slowly compared to other hash functions such as SHA-3 and the best known hardware implementation of RC4.
Like othersponge functions, Spritz can be used to build a cryptographic hash function, a deterministic random bit generator (DRBG), an encryption algorithm that supportsauthenticated encryption with associated data (AEAD), etc.[14]
In 2016, Banik and Isobe proposed an attack that can distinguish Spritz from random noise.[64] In 2017, Banik, Isobe, and Morii proposed a simple fix that removes the distinguisher in the first two keystream bytes, requiring only one additional memory access without diminishing software performance substantially.[65]
Where a protocol is marked with "(optionally)", RC4 is one of multiple ciphers the system can be configured to use.
ChaCha based random number generator for OpenBSD.
Legacy arc4random(3) API from OpenBSD reimplemented using the ChaCha20 PRF, with per-thread state.
