RC4
Encyclopedia
In cryptography
, RC4 (also known as ARC4 or ARCFOUR meaning Alleged RC4, see below) is the most widely used software stream cipher
and is used in popular protocols such as Secure Sockets Layer (SSL) (to protect Internet traffic) and WEP
(to secure wireless networks). While remarkable for its simplicity and speed in software, RC4 has weaknesses that argue against its use in new systems. It is especially vulnerable when the beginning of the output keystream
is not discarded, or nonrandom or related keys are used; some ways of using RC4 can lead to very insecure cryptosystem
s such as WEP
. For a detailed exposition on RC4 stream cipher, refer to the book by Goutam Paul and Subhamoy Maitra.
of RSA Security
in 1987. While it is officially termed "Rivest Cipher 4", the RC acronym is alternatively understood to stand for "Ron's Code" (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. It was soon posted on the sci.crypt newsgroup
, and from there 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 trademark
ed, so RC4 is often referred to as "ARCFOUR" or "ARC4" (meaning Alleged RC4) 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. RC4 has become part of some commonly used encryption protocols and standards, including WEP
and WPA
for wireless cards and TLS
.
The main factors in RC4's success over such a wide range of applications are its speed and simplicity: efficient implementations in both software and hardware are very easy to develop.
). As with any stream cipher, these can be used for encryption by combining it with the plaintext using bit-wise exclusive-or; decryption is performed the same way (since exclusive-or is a symmetric operation). (This is similar to the Vernam cipher 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:
The permutation is initialized with a variable length key
, typically between 40 and 256 bits, using the key-scheduling
algorithm (KSA). Once this has been completed, the stream of bits is generated using the pseudo-random generation algorithm (PRGA).
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.
for i from 0 to 255
S[i] := i
endfor
j := 0
for i from 0 to 255
j := (j + S[i] + key[i mod
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 increments i, looks up the ith element of S, S[i], and adds that to j, exchanges the values of S[i] and S[j], and then uses the sum S[i] + S[j] (modulo 256) as an index to fetch a third element of S which is the output of the algorithm. Each element of S is swapped with another element at least once every 256 iterations.
i := 0
j := 0
while GeneratingOutput:
i := (i + 1) mod 256
j := (j + S[i]) mod 256
swap values of S[i] and S[j]
K := S[(S[i] + S[j]) mod 256]
output K
endwhile
s (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 y. Performing a modular reduction of some value modulo 256 can be done with a bitwise AND with 255 (which is equivalent to taking the low-order byte of the value in question).
, the keystream and ciphertext are in hexadecimal
.
), 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 cryptosystem 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 a variety of serious problems.
Because RC4 is a stream cipher
, it is more malleable
than common block cipher
s. If not used together with a strong message authentication code
(MAC), then encryption is vulnerable to a bit-flipping attack
. It is noteworthy, however, that RC4, being a stream cipher, is the only common cipher which is immune to the 2011 BEAST attack on TLS 1.0, which exploits a known weakness in the cipher block chaining mode used with all of the other ciphers supported by TLS 1.0, which are all block ciphers.
. 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
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 such attacks which 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 prove 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.
: over all possible RC4 keys, the statistics for the first few bytes of output keystream are strongly non-random, leaking information about the key. If the long-term key and nonce 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 network
s. 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
.
Cryptosystems can defend against this attack by discarding the initial portion of the keystream. Such a modified algorithm is traditionally called "RC4-drop[n]", where n is the number of initial keystream bytes that are dropped. The SCAN default is n = 768 bytes, but a conservative value would be n = 3072 bytes.
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 x in the next 256 rounds. This conjecture was put to rest in 2004 with a formal proof given by Souradyuti Paul
and Bart Preneel
.
A number of attempts have been made to strengthen RC4, notably RC4A, VMPC
, and RC4+.
and Bart Preneel
have proposed an RC4 variant, which they call RC4A.
RC4A uses two state arrays S1 and S2, and two indexes j1 and j2. Each time i is incremented, two bytes are generated:
Thus, the algorithm is:
All arithmetic is performed modulo 256
i := 0
j1 := 0
j2 := 0
while 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 and a team from NEC developing ways to distinguish its output from a truly random sequence.
All arithmetic is performed modulo 256.
i := 0
while GeneratingOutput:
a := S[i]
j := S[j + a]
b := S[j]
output S[S[b] + 1]
S[i] := b (Swap S[i] and S[j])
S[j] := a
i := i + 1
endwhile
This was attacked in the same papers as RC4A.
All arithmetic modulo 256. << and >> are left and right shift, ⊕ is exclusive OR
while GeneratingOutput:
i := i + 1
a := S[i]
j := j + a
b := S[j]
S[i] := b (Swap S[i] and S[j])
S[j] := a
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.
Where a cryptosystem is marked with "(optionally)", RC4 is one of several ciphers the system can be configured to use.
RC4 in WEP
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, RC4 (also known as ARC4 or ARCFOUR meaning Alleged RC4, see below) is the most widely used software stream cipher
Stream cipher
In cryptography, a stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream . In a stream cipher the plaintext digits are encrypted one at a time, and the transformation of successive digits varies during the encryption...
and is used in popular protocols such as Secure Sockets Layer (SSL) (to protect Internet traffic) and WEP
Wired Equivalent Privacy
Wired Equivalent Privacy is a weak security algorithm for IEEE 802.11 wireless networks. Introduced as part of the original 802.11 standard ratified in September 1999, its intention was to provide data confidentiality comparable to that of a traditional wired network...
(to secure wireless networks). While remarkable for its simplicity and speed in software, RC4 has weaknesses that argue against its use in new systems. It is especially vulnerable when the beginning of the output keystream
Keystream
In cryptography, a keystream is a stream of random or pseudorandom characters that are combined with a plaintext message to produce an encrypted message ....
is not discarded, or nonrandom or related keys are used; some ways of using RC4 can lead to very insecure cryptosystem
Cryptosystem
There are two different meanings of the word cryptosystem. One is used by the cryptographic community, while the other is the meaning understood by the public.- General meaning :...
s such as WEP
Wired Equivalent Privacy
Wired Equivalent Privacy is a weak security algorithm for IEEE 802.11 wireless networks. Introduced as part of the original 802.11 standard ratified in September 1999, its intention was to provide data confidentiality comparable to that of a traditional wired network...
. For a detailed exposition on RC4 stream cipher, refer to the book by Goutam Paul and Subhamoy Maitra.
History
RC4 was designed by Ron RivestRon Rivest
Ronald Linn Rivest is a cryptographer. He is the Andrew and Erna Viterbi Professor of Computer Science at MIT's Department of Electrical Engineering and Computer Science and a member of MIT's Computer Science and Artificial Intelligence Laboratory...
of RSA Security
RSA Security
RSA, the security division of EMC Corporation, is headquartered in Bedford, Massachusetts, United States, and maintains offices in Australia, Ireland, Israel, the United Kingdom, Singapore, India, China, Hong Kong and Japan....
in 1987. While it is officially termed "Rivest Cipher 4", the RC acronym is alternatively understood to stand for "Ron's Code" (see also RC2
RC2
In cryptography, RC2 is a block cipher designed by Ron Rivest in 1987. "RC" stands for "Ron's Code" or "Rivest Cipher"; other ciphers designed by Rivest include RC4, RC5 and RC6....
, RC5
RC5
In cryptography, RC5 is a block cipher notable for its simplicity. Designed by Ronald Rivest in 1994, RC stands for "Rivest Cipher", or alternatively, "Ron's Code"...
and RC6
RC6
In cryptography, RC6 is a symmetric key block cipher derived from RC5. It was designed by Ron Rivest, Matt Robshaw, Ray Sidney, and Yiqun Lisa Yin to meet the requirements of the Advanced Encryption Standard competition. The algorithm was one of the five finalists, and was also submitted to the...
).
RC4 was initially a trade secret
Trade secret
A trade secret is a formula, practice, process, design, instrument, pattern, or compilation of information which is not generally known or reasonably ascertainable, by which a business can obtain an economic advantage over competitors or customers...
, 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
Newsgroup
A usenet newsgroup is a repository usually within the Usenet system, for messages posted from many users in different locations. The term may be confusing to some, because it is usually a discussion group. Newsgroups are technically distinct from, but functionally similar to, discussion forums on...
, and from there to many sites on the Internet
Internet
The Internet is a global system of interconnected computer networks that use the standard Internet protocol suite to serve billions of users worldwide...
. 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
Trade secret
A trade secret is a formula, practice, process, design, instrument, pattern, or compilation of information which is not generally known or reasonably ascertainable, by which a business can obtain an economic advantage over competitors or customers...
. The name "RC4" is trademark
Trademark
A trademark, trade mark, or trade-mark is a distinctive sign or indicator used by an individual, business organization, or other legal entity to identify that the products or services to consumers with which the trademark appears originate from a unique source, and to distinguish its products or...
ed, so RC4 is often referred to as "ARCFOUR" or "ARC4" (meaning Alleged RC4) to avoid trademark problems. RSA Security
RSA Security
RSA, the security division of EMC Corporation, is headquartered in Bedford, Massachusetts, United States, and maintains offices in Australia, Ireland, Israel, the United Kingdom, Singapore, India, China, Hong Kong and Japan....
has never officially released the algorithm; Rivest has, however, linked to the English Wikipedia
English Wikipedia
The English Wikipedia is the English-language edition of the free online encyclopedia Wikipedia. Founded on 15 January 2001 and reaching three million articles by August 2009, it was the first edition of Wikipedia and remains the largest, with almost three times as many articles as the next...
article on RC4 in his own course notes. RC4 has become part of some commonly used encryption protocols and standards, including WEP
Wired Equivalent Privacy
Wired Equivalent Privacy is a weak security algorithm for IEEE 802.11 wireless networks. Introduced as part of the original 802.11 standard ratified in September 1999, its intention was to provide data confidentiality comparable to that of a traditional wired network...
and WPA
Wi-Fi Protected Access
Wi-Fi Protected Access and Wi-Fi Protected Access II are two security protocols and security certification programs developed by the Wi-Fi Alliance to secure wireless computer networks...
for wireless cards and TLS
Transport Layer Security
Transport Layer Security and its predecessor, Secure Sockets Layer , are cryptographic protocols that provide communication security over the Internet...
.
The main factors in RC4's success over such a wide range of applications are its speed and simplicity: efficient implementations in both software and hardware are very easy to develop.
Description
RC4 generates a pseudorandom stream of bits (a keystreamKeystream
In cryptography, a keystream is a stream of random or pseudorandom characters that are combined with a plaintext message to produce an encrypted message ....
). As with any stream cipher, these can be used for encryption by combining it with the plaintext using bit-wise exclusive-or; decryption is performed the same way (since exclusive-or is a symmetric operation). (This is similar to the Vernam cipher 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 permutationPermutationIn mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...
of all 256 possible bytes (denoted "S" below). - Two 8-bit index-pointers (denoted "i" and "j").
The permutation is initialized with a variable length key
Key (cryptography)
In cryptography, a key is a piece of information that determines the functional output of a cryptographic algorithm or cipher. Without a key, the algorithm would produce no useful result. In encryption, a key specifies the particular transformation of plaintext into ciphertext, or vice versa...
, typically between 40 and 256 bits, using the key-scheduling
Key schedule
[[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES [[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES [[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES ("[[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES ("...
algorithm (KSA). Once this has been completed, the stream of bits is generated using the pseudo-random generation algorithm (PRGA).
The key-scheduling algorithm (KSA)
The key-schedulingKey schedule
[[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES [[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES [[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES ("[[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES ("...
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
Identity (mathematics)
In mathematics, the term identity has several different important meanings:*An identity is a relation which is tautologically true. This means that whatever the number or value may be, the answer stays the same. For example, algebraically, this occurs if an equation is satisfied for all values of...
. 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 i from 0 to 255
S[i] := i
endfor
j := 0
for i from 0 to 255
j := (j + S[i] + key[i mod
Modulo operation
In computing, the modulo operation finds the remainder of division of one number by another.Given two positive numbers, and , a modulo n can be thought of as the remainder, on division of a by n...
keylength]) mod 256
swap values of S[i] and S[j]
endfor
The pseudo-random generation algorithm (PRGA)
i := 0
j := 0
while GeneratingOutput:
i := (i + 1) mod 256
j := (j + S[i]) mod 256
swap values of S[i] and S[j]
K := S[(S[i] + S[j]) mod 256]
output K
endwhile
Implementation
Many stream ciphers are based on linear feedback shift registerLinear feedback shift register
A linear feedback shift register is a shift register whose input bit is a linear function of its previous state.The most commonly used linear function of single bits is XOR...
s (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 y. Performing a modular reduction of some value modulo 256 can be done with a bitwise AND with 255 (which is equivalent to taking the low-order byte of the value in question).
Test vectors
These test vectors are not official, but convenient for anyone testing their own RC4 program. The keys and plaintext are ASCIIASCII
The American Standard Code for Information Interchange is a character-encoding scheme based on the ordering of the English alphabet. ASCII codes represent text in computers, communications equipment, and other devices that use text...
, the keystream and ciphertext are in hexadecimal
Hexadecimal
In mathematics and computer science, hexadecimal is a positional numeral system with a radix, or base, of 16. It uses sixteen distinct symbols, most often the symbols 0–9 to represent values zero to nine, and A, B, C, D, E, F to represent values ten to fifteen...
.
| Key | Keystream | Plaintext | Ciphertext |
|---|---|---|---|
Key |
eb9f7781b734ca72a719... |
Plaintext |
BBF316E8D940AF0AD3 |
Wiki |
6044db6d41b7... |
pedia |
1021BF0420 |
Secret |
04d46b053ca87b59... |
Attack at dawn |
45A01F645FC35B383552544B9BF5 |
Security
Unlike a modern stream cipher (such as those in eSTREAMESTREAM
eSTREAM is a project to "identify new stream ciphers suitable for widespread adoption", organised by the EU ECRYPT network. It was set up as a result of the failure of all six stream ciphers submitted to the NESSIE project. The call for primitives was first issued in November 2004. The project was...
), RC4 does not take a separate nonce
Cryptographic nonce
In security engineering, nonce is an arbitrary number used only once to sign a cryptographic communication. It is similar in spirit to a nonce word, hence the name. It is often a random or pseudo-random number issued in an authentication protocol to ensure that old communications cannot be reused...
alongside the key. This means that if a single long-term key is to be used to securely encrypt multiple streams, the cryptosystem 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
Cryptographic hash function
A cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...
a long-term key with a nonce
Cryptographic nonce
In security engineering, nonce is an arbitrary number used only once to sign a cryptographic communication. It is similar in spirit to a nonce word, hence the name. It is often a random or pseudo-random number issued in an authentication protocol to ensure that old communications cannot be reused...
. However, many applications that use RC4 simply concatenate key and nonce; RC4's weak key schedule
Key schedule
[[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES [[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES [[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES ("[[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES ("...
then gives rise to a variety of serious problems.
Because RC4 is a stream cipher
Stream cipher
In cryptography, a stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream . In a stream cipher the plaintext digits are encrypted one at a time, and the transformation of successive digits varies during the encryption...
, it is more malleable
Malleability (cryptography)
Malleability is a property of some cryptographic algorithms. An encryption algorithm is malleable if it is possible for an adversary to transform a ciphertext into another ciphertext which decrypts to a related plaintext...
than common block cipher
Block cipher
In cryptography, a block cipher is a symmetric key cipher operating on fixed-length groups of bits, called blocks, with an unvarying transformation. A block cipher encryption algorithm might take a 128-bit block of plaintext as input, and output a corresponding 128-bit block of ciphertext...
s. If not used together with a strong message authentication code
Message authentication code
In cryptography, a message authentication code is a short piece of information used to authenticate a message.A MAC algorithm, sometimes called a keyed hash function, accepts as input a secret key and an arbitrary-length message to be authenticated, and outputs a MAC...
(MAC), then encryption is vulnerable to a bit-flipping attack
Bit-flipping attack
A bit-flipping attack is an attack on a cryptographic cipher in which the attacker can change the ciphertext in such a way as to result in a predictable change of the plaintext, although the attacker is not able to learn the plaintext itself...
. It is noteworthy, however, that RC4, being a stream cipher, is the only common cipher which is immune to the 2011 BEAST attack on TLS 1.0, which exploits a known weakness in the cipher block chaining mode used with all of the other ciphers supported by TLS 1.0, which are all block ciphers.
Roos' Biases and Key Reconstruction from Permutation
In 1995, Andrew Roos experimentally observed that the first byte of the keystream is correlated to the first three bytes of the key and the first few bytes of the permutation after the KSA are correlated to some linear combination of the key bytes. These biases remained unproved 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 IVInitialization vector
In cryptography, an initialization vector is a fixed-size input to a cryptographic primitive that is typically required to be random or pseudorandom...
. 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
S[S[i]] or S[S[S[i]]]. 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 in varying degrees towards certain sequences. The best such attack is due to Itsik Mantin and Adi ShamirAdi Shamir
Adi Shamir is an Israeli cryptographer. He is a co-inventor of the RSA algorithm , a co-inventor of the Feige–Fiat–Shamir identification scheme , one of the inventors of differential cryptanalysis and has made numerous contributions to the fields of cryptography and computer...
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
Souradyuti Paul
Souradyuti Paul is an Indian cryptologist . Formerly a member of COSIC, he is currently working as a Guest Researcher for the National Institute of Standards and Technology in the United States...
and Bart Preneel
Bart Preneel
Bart Preneel is a Belgian cryptographer and cryptanalyst. He is a professor at Katholieke Universiteit Leuven, in the COSIC group, president of the International Association for Cryptologic Research, and project manager of ECRYPT....
of COSIC
COSIC
The Computer Security and Industrial Cryptography research group, commonly called COSIC, is a research group at the Department of Electrical Engineering of the Katholieke Universiteit Leuven, which is headed by Professor Bart Preneel, Vincent Rijmen, and Professor Ingrid Verbauwhede.The goal of...
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 such attacks which 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 prove 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 ShamirAdi Shamir
Adi Shamir is an Israeli cryptographer. He is a co-inventor of the RSA algorithm , a co-inventor of the Feige–Fiat–Shamir identification scheme , one of the inventors of differential cryptanalysis and has made numerous contributions to the fields of cryptography and computer...
: over all possible RC4 keys, the statistics for the first few bytes of output keystream are strongly non-random, leaking information about the key. If the long-term key and nonce 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
Wired Equivalent Privacy is a weak security algorithm for IEEE 802.11 wireless networks. Introduced as part of the original 802.11 standard ratified in September 1999, its intention was to provide data confidentiality comparable to that of a traditional wired network...
("wired equivalent privacy") encryption used with 802.11 wireless network
Wireless network
Wireless network refers to any type of computer network that is not connected by cables of any kind. It is a method by which homes, telecommunications networks and enterprise installations avoid the costly process of introducing cables into a building, or as a connection between various equipment...
s. This caused a scramble for a standards-based replacement for WEP in the 802.11 market, and led to the IEEE 802.11i
IEEE 802.11i
IEEE 802.11i-2004 or 802.11i, implemented as WPA2, is an amendment to the original IEEE 802.11. The draft standard was ratified on 24 June 2004. This standard specifies security mechanisms for wireless networks. It replaced the short Authentication and privacy clause of the original standard with...
effort and WPA
Wi-Fi Protected Access
Wi-Fi Protected Access and Wi-Fi Protected Access II are two security protocols and security certification programs developed by the Wi-Fi Alliance to secure wireless computer networks...
.
Cryptosystems can defend against this attack by discarding the initial portion of the keystream. Such a modified algorithm is traditionally called "RC4-drop[n]", where n is the number of initial keystream bytes that are dropped. The SCAN default is n = 768 bytes, but a conservative value would be n = 3072 bytes.
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 which 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 ShamirAdi Shamir
Adi Shamir is an Israeli cryptographer. He is a co-inventor of the RSA algorithm , a co-inventor of the Feige–Fiat–Shamir identification scheme , one of the inventors of differential cryptanalysis and has made numerous contributions to the fields of cryptography and computer...
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 x in the next 256 rounds. This conjecture was put to rest in 2004 with a formal proof given by Souradyuti Paul
Souradyuti Paul
Souradyuti Paul is an Indian cryptologist . Formerly a member of COSIC, he is currently working as a Guest Researcher for the National Institute of Standards and Technology in the United States...
and Bart Preneel
Bart Preneel
Bart Preneel is a Belgian cryptographer and cryptanalyst. He is a professor at Katholieke Universiteit Leuven, in the COSIC group, president of the International Association for Cryptologic Research, and project manager of ECRYPT....
.
RC4 variants
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. This is known as RC4-dropN, where N is typically a multiple of 256, such as 768 or 1024.A number of attempts have been made to strengthen RC4, notably RC4A, VMPC
Variably Modified Permutation Composition
VMPC is encryption technology designed by Bartosz Zoltak, publicly presented in 2004 at an international cryptography conference Fast Software Encryption in Delhi, India....
, and RC4+.
RC4A
Souradyuti PaulSouradyuti Paul
Souradyuti Paul is an Indian cryptologist . Formerly a member of COSIC, he is currently working as a Guest Researcher for the National Institute of Standards and Technology in the United States...
and Bart Preneel
Bart Preneel
Bart Preneel is a Belgian cryptographer and cryptanalyst. He is a professor at Katholieke Universiteit Leuven, in the COSIC group, president of the International Association for Cryptologic Research, and project manager of ECRYPT....
have proposed an RC4 variant, which they call RC4A.
RC4A uses two state arrays S1 and S2, and two indexes j1 and j2. Each time i is incremented, two bytes are generated:
- First, the basic RC4 algorithm is performed using S1 and j1, but in the last step, S1[i] + S1[j1] is looked up in S2.
- Second, the operation is repeated (without incrementing i again) on S2 and j2, and S1[S2[i]+S2[j2]] is output.
Thus, the algorithm is:
All arithmetic is performed modulo 256
i := 0
j1 := 0
j2 := 0
while 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 and a team from NEC developing ways to distinguish its output from a truly random sequence.
VMPC
"Variably Modified Permutation Composition" is another RC4 variant. It uses the same key schedule as RC4, but iterating 768 times rather than 256 (it is not the same as RC4-drop512 because all iterations incorporate key material), and with an optional additional 768 iterations to incorporate an initial vector. Written to highlight the similarity to RC4 as much as possible, the output generation function operates as follows:All arithmetic is performed modulo 256.
i := 0
while GeneratingOutput:
a := S[i]
j := S[j + a]
b := S[j]
output S[S[b] + 1]
S[i] := b (Swap S[i] and S[j])
S[j] := a
i := i + 1
endwhile
This was attacked in the same papers as RC4A.
RC4+
RC4+ is a modified version of RC4 with a more complex three-phase key schedule (taking about 3× 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× as long as basic RC4.All arithmetic modulo 256. << and >> are left and right shift, ⊕ is exclusive OR
while GeneratingOutput:
i := i + 1
a := S[i]
j := j + a
b := S[j]
S[i] := b (Swap S[i] and S[j])
S[j] := a
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.
RC4-based cryptosystems
- WEPWired Equivalent PrivacyWired Equivalent Privacy is a weak security algorithm for IEEE 802.11 wireless networks. Introduced as part of the original 802.11 standard ratified in September 1999, its intention was to provide data confidentiality comparable to that of a traditional wired network...
- WPAWi-Fi Protected AccessWi-Fi Protected Access and Wi-Fi Protected Access II are two security protocols and security certification programs developed by the Wi-Fi Alliance to secure wireless computer networks...
(default algorithm, but can be configured to use AES-CCMP instead of RC4) - BitTorrent protocol encryptionBitTorrent protocol encryptionProtocol encryption , message stream encryption , or protocol header encrypt are related features of some peer-to-peer file-sharing clients, including BitTorrent clients. They attempt to enhance privacy and confidentiality...
- Microsoft Point-to-Point Encryption
- Opera MiniOpera MiniOpera Mini is a web browser designed primarily for mobile phones, smartphones and personal digital assistants. Until version 4 it used the Java ME platform, requiring the mobile device to run Java ME applications. From version 5 it is also available as a native application for Android, iOS, Symbian...
- Secure Sockets Layer (optionally)
- Secure shellSecure ShellSecure Shell is a network protocol for secure data communication, remote shell services or command execution and other secure network services between two networked computers that it connects via a secure channel over an insecure network: a server and a client...
(optionally) - Remote Desktop ProtocolRemote Desktop ProtocolRemote Desktop Protocol is a proprietary protocol developed by Microsoft, which provides a user with a graphical interface to another computer. The protocol is an extension of the ITU-T T.128 application sharing protocol. Clients exist for most versions of Microsoft Windows , Linux, Unix, Mac OS...
- Kerberos (optionally)
- SASLSimple Authentication and Security LayerSimple Authentication and Security Layer is a framework for authentication and data security in Internet protocols. It decouples authentication mechanisms from application protocols, in theory allowing any authentication mechanism supported by SASL to be used in any application protocol that uses...
Mechanism Digest-MD5 (optionally) - Gpcode.AK, an early June 2008 computer virus for Microsoft Windows, which takes documents hostage for ransomRansomRansom is the practice of holding a prisoner or item to extort money or property to secure their release, or it can refer to the sum of money involved.In an early German law, a similar concept was called bad influence...
by obscuring them with RC4 and RSA-1024 encryption - PDFPortable Document FormatPortable Document Format is an open standard for document exchange. This file format, created by Adobe Systems in 1993, is used for representing documents in a manner independent of application software, hardware, and operating systems....
- SkypeSkypeSkype is a software application that allows users to make voice and video calls and chat over the Internet. Calls to other users within the Skype service are free, while calls to both traditional landline telephones and mobile phones can be made for a fee using a debit-based user account system...
(in modified form)
Where a cryptosystem is marked with "(optionally)", RC4 is one of several ciphers the system can be configured to use.
See also
- eSTREAMESTREAMeSTREAM is a project to "identify new stream ciphers suitable for widespread adoption", organised by the EU ECRYPT network. It was set up as a result of the failure of all six stream ciphers submitted to the NESSIE project. The call for primitives was first issued in November 2004. The project was...
- An evaluation of new stream cipherStream cipherIn cryptography, a stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream . In a stream cipher the plaintext digits are encrypted one at a time, and the transformation of successive digits varies during the encryption...
s being conducted by the EU. - TEATiny Encryption AlgorithmIn cryptography, the Tiny Encryption Algorithm is a block cipher notable for its simplicity of description and implementation, typically a few lines of code...
, Block TEAXTEAIn cryptography, XTEA is a block cipher designed to correct weaknesses in TEA. The cipher's designers were David Wheeler and Roger Needham of the Cambridge Computer Laboratory, and the algorithm was presented in an unpublished technical report in 1997...
also known as eXtended TEAXTEAIn cryptography, XTEA is a block cipher designed to correct weaknesses in TEA. The cipher's designers were David Wheeler and Roger Needham of the Cambridge Computer Laboratory, and the algorithm was presented in an unpublished technical report in 1997...
and Corrected Block TEAXXTEAIn cryptography, Corrected Block TEA is a block cipher designed to correct weaknesses in the original Block TEA.XXTEA is vulnerable to a chosen-plaintext attack requiring 259 queries and negligible work...
- A family of block cipherBlock cipherIn cryptography, a block cipher is a symmetric key cipher operating on fixed-length groups of bits, called blocks, with an unvarying transformation. A block cipher encryption algorithm might take a 128-bit block of plaintext as input, and output a corresponding 128-bit block of ciphertext...
s that, like RC4, are designed to be very simple to implement. - Advanced Encryption StandardAdvanced Encryption StandardAdvanced Encryption Standard is a specification for the encryption of electronic data. It has been adopted by the U.S. government and is now used worldwide. It supersedes DES...
- CipherSaberCipherSaberCipherSaber is a simple symmetric encryption protocol based on the RC4 stream cipher. Its goals are both technical and political: it gives reasonably strong protection of message confidentiality, yet it's designed to be simple enough that even novice programmers can memorize the algorithm and...
External links
- RC4 Implementation in C
- RC4 Implementation in Delphi
- IETF Draft - A Stream Cipher Encryption Algorithm "Arcfour"
- Original posting of RC4 algorithm to Cypherpunks mailing list, Archived version
- SCAN's entry for RC4
- Attacks on RC4
- RC4 - Cryptology Pointers by Helger Lipmaa
- RSA Security Response to Weaknesses in Key Scheduling Algorithm of RC4
- T-SQL implementation
RC4 in WEP