RC4
In cryptography, RC4 is a stream cipher. While it is remarkable for its simplicity and speed in software, multiple vulnerabilities have been discovered in RC4, rendering it insecure. It is especially vulnerable when the beginning of the output keystream is not discarded, or when nonrandom or related keys are used. Particularly problematic uses of RC4 have led to insecure protocols such as the obsolete WEP protocol historically used to secure WiFi networks.
There has long been speculation that some state cryptologic agencies may possess the capability to break RC4 when used in the TLS protocol. In response, the IETF published to prohibit the use of RC4 in TLS; Mozilla and Microsoft have issued similar recommendations.
A number of attempts have been made to strengthen RC4, notably Spritz, RC4A, VMPC, and RC4+.
History
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", though in general it is simply referred to as RC4. The same naming convention applies to 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. It was soon posted on the sci.crypt newsgroup, where it was broken within days by Bob Jenkins. 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 name RC4 is trademarked, so RC4 is often referred to as ARCFOUR or ARC4 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 in 2008 and confirmed the history of RC4 and its code in a 2014 paper.
RC4 became part of some commonly used encryption protocols and standards, such as WEP in 1997 and WPA in 2003/2004 for wireless cards; and SSL in 1995 and its successor TLS in 1999, until it was prohibited for all versions of TLS in 2015 by, due to the RC4 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.
Description
RC4 generates a pseudorandom stream of bits. As with any stream cipher, these can be used for encryption by combining it with the plaintext using bitwise exclusive or; decryption is performed the same way. This is similar to the one-time pad, 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.
- Two 8-bit index-pointers.
Key-scheduling algorithm (KSA)
The key-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 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. Note that many different keys like 'Text' and 'TextText' lead to the same cipher.for i from 0 to 255
S := i
endfor
j := 0
for i from 0 to 255
j := mod 256
swap values of S and S
'''endfor'''
Pseudo-random generation algorithm (PRGA)
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 ;
- looks up the th element of,, and adds that to ;
- exchanges the values of and, then uses the sum as an index to fetch a third element of ;
- then bitwise exclusive ORed with the next byte of the message to produce the next byte of either ciphertext or plaintext.
i := 0
j := 0
while GeneratingOutput:
i := mod 256
j := mod 256
swap values of S and S
t := mod 256
K := S
output K
endwhile
Thus, this produces a stream of which are XORed with the to obtain the. So.
RC4-based random number generators
Several operating systems include, an API originating in OpenBSD 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 the backronym "A Replacement Call for Random" for ARC4 as a mnemonic, as it provided better random data than the original and highly insecure rand function based on a linear congruential pseudo-random number generator with a 32-bit internal state.Several attacks on RC4 are able to distinguish its output from a random sequence. As a result the use of ARC4 in was eventually replaced with better pseudo-random number generators:
- In OpenBSD 5.5, released in May 2014, was modified to use the superior stream cipher ChaCha20. The implementations of arc4random in FreeBSD, NetBSD also use ChaCha20.
- Linux typically uses glibc, which did not offer arc4random until 2022. Instead, a separate library, libbsd, offers the function; it was updated to use ChaCha20 in 2016. In 2022, glibc added its own version of arc4random, also based on ChaCha20.
- According to manual pages shipped with the operating system, in the 2017 release of macOS and iOS operating systems, Apple replaced RC4 with AES in its implementation of arc4random.
Implementation
Many stream ciphers are based on linear-feedback shift registers, 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 through S, k bytes of memory for the key, key through key, and integer variables, i, j, and K. Performing a modular reduction of some value modulo 256 can be done with a bitwise AND with 255.Test vectors
These test vectors are not official, but convenient for anyone testing their own RC4 program. The keys and plaintext are ASCII, the keystream and ciphertext are in hexadecimal.| Key | Keystream | Plaintext | Ciphertext |
| ... | |||
| ... | |||
| ... |
Security
Unlike a modern stream cipher, 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.Because RC4 is a stream cipher, it is more malleable than common block ciphers. If not used together with a strong message authentication code, 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.