A Survey on RC4 Stream Cipher

Published Online June 2015 in MECS

The concept of security is generally interpreted as the idea of confidentiality of data being transmitted, particularly the digital information transmitted over the wireless network. Most commonly security is provided using cryptographic primitives. As shown in Fig. 1 the cryptographic primitives are classified into three main categories; not using key, symmetric key and asymmetric key [1]. Although Fig. 1 is not presenting an exhaustive list of these primitives but is highlighting the important and relevant areas. In this paper we have focused on symmetric key ciphers which are also known as secret key or single key ciphers. Secret key ciphers are further classified as block ciphers and stream ciphers. In block ciphers, a block of bits/bytes is processed at a time. DES, IDEA, RC5, AES, BLOWFISH, TWOFISH are the different available block ciphers. Whereas in stream ciphers one bit or a byte of data is processed at a time. Stream ciphers are further classified as synchronous and self-synchronous stream ciphers. Synchronous stream ciphers (SSC) are prominently discussed in literature. However, generally due to the design problems, selfsynchronizing stream cipher (SSSC) are not much explored in literature and are less used in practice [2]. Different synchronous stream ciphers available in the literature are RC4, E0 (a stream cipher used in Bluetooth), A5/1 and A5/2 (stream ciphers used in GSM), SNOW 3G, ZUC (4G stream ciphers), Rabbit, FISH, and HC-256 etc. [3-8].

In this paper we have considered stream ciphers. A keystream is produced in stream ciphers which is a pseudorandom sequence of bits. A plaintext (a sequence of bits/bytes) is converted into ciphertext (again a sequence of bits/bytes of same length as that of plaintext) by hiding the plaintext with a generated keystream, using a simple XOR operation. The strength of stream ciphers is a random keystream which ensures the computational security of the cipher. In cryptographic primitives nonrandom events which can be computationally recognized either in the internal states and in the output keystream are generally not desirable. Thus the cryptanalysis of stream ciphers is imperatively focused on the identification of non-random events and hence extensive analysis of stream ciphers is done till date to identify the occurrence of non-random events. Table 1 and Figs. (2, 3) demonstrates the overview of various cryptanalytic attack models, modes of attacks and goals of intruder in stream ciphers respectively. The general classification of the cryptanalytic attacks on stream ciphers with the assumption that what is known to the intruder is shown in Table. 1. These cryptanalytic attacks are also known as attack models. Further on the basis of these attack models and the knowledge of intruder (what is known to intruder), Fig. 2 presents the different modes in which the intruder can attack the cipher. Intruder mount these models and modes of attack on stream ciphers with the goals as shown in Fig. 3 [1-2].

A chronological comprehensive survey of the most prevalent and commercially used RC4 stream cipher along with the countermeasures is presented in this paper. We have focused on RC4 because it outperforms amongst all the modern stream ciphers. Though the algorithm is publicly revealed in 1994 through internet but due to its design simplicity everyone gets attracted towards it and has been adopted worldwide [9]. The cipher is widely adopted in various software and web applications. It is used in different network protocols such as WEP (Wireless equivalent privacy), WPA (Wi-Fi protected access), and SSL (Secure socket layer). Also it is extensively used in Microsoft windows, Apple OCE (Apple Open Collaboration Environment), secure SQL (a server for database management and data warehousing solution) etc. Throughout the paper we have tried to explore the various weaknesses of the cipher till date. It is found that regardless of many efforts made by researchers in improving the flaws of RC4 cipher, still there are number of biases exist in the keystream, key recovery can be made from state and certain sets of keys do exist that can generate similar states. It corroborate the fact that even after the decades of research the RC4 stream cipher continues to offer research problems of interest to researchers.

Rest of the paper is organized as follows. Section 2 gives the brief description of RC4 encryption algorithm. Different weaknesses and their related cryptanalysis is presented in section 3. Section 4 describes existing proposals for the enhancement of the cipher are given in section 5. Conclusion and future scope is drawn in section 6.

• II.    RC4 Description

RC4 follows the design strategy used in stream ciphers. To extract the pseudorandom data bytes from a pseudorandom permutation is the basic design principle of RC4 stream cipher. RC4 has two working modules:

first there is a KSA with key K as input (with typical size of 40-256 bits), and second is PRGA which generates a pseudo-random output sequence. The pseudo code for RC4. Fig 4 presents the complete working of RC4 encryption algorithm. KSA generates the 256 byte initial state vector S, by scrambling input state vector with a random key K. The S contains a permutation of 8 bit words i.e. 256 bytes. The secret key k is generally of length between 8 to 2048 bits and the expanded key K (K of length N=256 bytes) is produced by performing simple repetitions. The expanded key is generated in the manner such that if secret key k is of length l bytes, the expanded key will be K[i] = k [ i mod l ] for 0 ≤ i ≤ N-1 . Further S pairs are swapped and an initial state S_N-1 is achieved at the end which is the input to the second module PRGA. It generates the keystream of words and is further XORed with the plaintext to produce a ciphertext. To figure axis labels, use words rather than symbols. Do not label axes only with units. Do not label axes with a ratio of quantities and units. Figure labels should be legible, about 9-point type. It is to be noted that each time a new keystream byte O is required, RC4 runs the loop of PRGA and each time with the generation of new keystream the internal state S is updated.

Fig. 1. Cryptographic primitives

Fig. 2. Modes of attack in stream ciphers

Table 1. Classification of the Cryptanalytic attacks on Stream ciphers (RC4)

Fig. 3 Goal of Intruder

Fig. 4. RC4 Stream Cipher

• III.    Existing Weaknesses of RC4 and the Related Cryptanalysis

  RC4 is known to be one of the simplest and widely adopted cipher. However the simplicity of RC4 makes it vulnerable to different security attacks. The cipher was designed in 1984 and was anonymously released on mails and news groups in 1994. Since then many cryptanalyst have exploited the weaknesses of the cipher for having access on either input state or key. From the basic structure of RC4 it is observed that PRGA generates a pseudorandom output sequence (bytes) from the permuted internal state which itself is a random sequence. The cryptanalyst is always in search of the statistical weaknesses of the output sequence. Statistical weaknesses are the biases in the random keystream that

can be exploited with a very high probability of success, to differentiate the generated RC4 keystream from a truly random sequence of bytes. Hence the main goal of an intruder while attacking RC4 is to investigate the nonrandom behavior either in the internal state or in the output keystream. The brief summary of security attacks on RC4 since its first public appearance to date is shown in Table 2. Various weaknesses of RC4 algorithm which are the roots to several attacks are detailed as below:

• A.    Weak Keys

  Weak keys are the small set of keys in RC4 which leaves some traces in the keystream generated after KSA or in the output bytes after PRGA. If such traces are followed by the intruder he/she can easily recover the key from the internal state or the output stream. In 1995, the first attack

first attack was made by Roos after discovering first set of weak keys in the RC4 algorithm. He found experimentally that there is significant probability for the first byte produced by RC4 to be O 1 =K [2] + 3 for a given key length K [0]....K[l] , where K [0]+K[1]=0 . He found that this event occurs with the probability ranges from 0.12 to 0.16 [10]. These results were later proved theoretically by authors in [11]. Roos also extended his research for first biased output byte to first two output bytes. Some more observations regarding the weak keys were given by Wagner in [12].

• B.    Key Collisions

  In RC4 KSA, it may be possible to generate a similar state even if two different keys are used and hence a similar output keystream will be produced. Such a scenario is known as key collision or related key pairs. Construction of such key pairs is the goal of attacker. Such key pairs were constructed by Grosul and Wallach in [13]. They constructed the key pair in a manner such that the second key of the pair is made by simply making two complementary modifications in the first key with an objective of not disturbing the state update process. A similar cryptanalysis was made by authors in [14], where key collision was obtained by varying the key bytes in two places such that during KSA the effect of one modification is nullified by the other. In 2009, a more practical way of constructing colliding key pairs by making the modification only in one key byte instead of two of RC4 stream cipher is given in [15]. The author also reported a 20 byte colliding key pairs for which the generated sate after KSA changed only in two places. Similarly a 22 byte key collision was obtained in [16]. Recently in 2013 authors have proposed certain ways to construct colliding key pairs such that the states produced after KSA vary only in few bytes [17].

• C.    Key Recovery From State

  RC4 PRGA is reversible in nature. From any given state of PRGA it is easy to reach the internal state and it is quite easy to recover the secret key from the internal state. If one could be able to efficiently reverse the KSA and obtain the secret key, it becomes possible to convert state recovery attack to key recovery attack. This weakness of RC4 was remained unexplored till the year 2007, when key recovery was done by solving modular equations for the first time by Paul and Maitra in [18]. As revealed by Roos in [10] that key bytes and the PRGA state bytes are correlated, the work presented in [18] was motivated from the same observation. The idea behind the work presented by Paul and Maitra is to select suitable equations, with known values from S, and solve those methodically for the key bytes. An improved key recovery approach with high probability of success as compared to [18] is achieved by Biham and Carmeli in [19], where authors have used differential equations instead of basic modular equations. The key recovery from state was further improved by authors in [20] by using equation solving approach. The technique discussed by authors in [20] is known to be the more efficient and

faster approach form key recovery from state. Another key recovery approach was discussed in [21] which is again an improvement over the technique given by [19]. Authors have used the same differential equation as in [19], but key was recovered using bit by bit approach. A new bidirectional search algorithm for key recovery given in [22], is a faster and efficient as well.

• D.    Key Recovery From Keystream

Key can be easily recovered from output keystream and this weakness of RC4 was exploited when used in WEP (Wired equivalent privacy) and WPA (Wi-Fi protected access). RC4 based WEP was the first security protocol used for Wi-Fi security in IEEE 802.11 LANs and thus always remained a target for cryptanalysis. As reported in the literature the adversary attack the WEP protocol by recovering the secret key K from the known values of IV (initialization vector) and known values of the RC4 keystream bytes found from the plaintext and ciphertext pairs. The number of attacks on WEP reported in the literature are Fluhrer, Mantin and Shamir attack (FMS) [23], Korek practical attacks [24-25], Mantin attack on RC4 [26] and WEP, Klien attack [27], Tews, Weinmann and Pyshkin (TWP) attack [28], Vaudenay and Vuagnoux (VV) attacks [29], Tews and Beck (TB) attack [30], Shepehrdad, Vaudenay and Vuagnoux (SVV) attack [31-33], and Shepehrdad, Susil, Vaudenay and Vuagnoux (SSVV) attack [34], WEP was declared as an insecure protocol. Later it is replaced by WPA (Wi-Fi protected access) which also make use of RC4 as its core element. WPA defended against many attacks in WEP. WPA has again proved to be a weak protocol due to TB data injection attacks [30], and SVV attacks [33]. Further a new protocol WPA2 was proposed by the Wi-Fi alliance which uses AES block cipher as an encryption algorithm instead of RC4. Though WPA2 is a secure protocol, removing many weaknesses of WEP and WPA but it’s hardware based applications are not cost effective as compare to WEP and WPA where RC4 was used as a basic module. Inspite of so many attacks and weaknesses in WEP, it is enormously opted in large number of applications due to its simplicity over WPA and WPA2. Different WEP attacks on the basis of packet complexity are summarized in Table 3.

• E.    State Recovery

  The state-space size in RC4 is N! × N², where N! = 0 is the space of N bytes in the internal state S and N² comes from the all possible combinations of indices i and j. Hence in RC4, for N=256 the total state-space available is, 256! × 265² ≈ 2¹⁷⁰⁰. Inspite of such a big state-space, the state recovery is possible in the cipher. The first state recovery attack on RC4 was proposed Knudsen, Meier and Preneel [35] in 1998 where the attack complexity was found to be 2⁷⁷⁹ for N=256. In the same year 1998, another state recovery attack was analyzed using some cycle –structures of RC4 [36] and observed that for N=32, state recovery can be done in 2⁴² steps. A probabilistic approach was used for RC4 state recovery in [37], having attack complexity similar to the one obtained in [35]. A

  slightly different attempt to recover state of RC4 on the basis of the partial knowledge of state is proposed in [38]. Initially they presented that the attack complexity given in [35] would be 2²²⁰ with the knowledge of 112 known states and further it was proposed that similar search complexity can be obtained with the knowledge of only 73 state values. Again the attack complexity of [35] was further reduced to 2⁷³¹ in [39]. In [40] a new state recovery approach based on the use of generative patterns, revealing the value of j in consecutive rounds, was discussed. The authors have claimed the search complexity to be reduced from 2⁷³¹ to 2²⁴¹. The improved attack based on guess and determine policy proposed in [41] claimed the data complexity to be reduced further to 2²¹¹.

• F.    Biased Bytes

In stream ciphers the event or bytes are said to be biased if an event occurs with different probability as that from the uniformly random sequence of bits/bytes. To study the non-random behavior of bytes is the goal of attacker. Several biases or correlation related to secret key, state variables, and short term and long term biases related to keystream bytes are in RC4 KSA and PRGA are available in literature.

• •    The first bias related to secret key was experimentally observed in [10], named as Roos key correlation, where the correlation between of the secret key bytes and the initial state bytes. Several key length dependent biases with their partial and conclusive proofs are presented in [42, 43] and [44] respectively. The first statement on the any bias in the first byte based on key length of RC4 is given by authors in [45].

• •    Some biases do exist that relate bytes in the output keystream to the internal state and make the state recovery attack possible. The relation between output keystream and initial state was first recognized in [46] but without proving it and later the bias is proved in [47, 48]. The results

  presented in [48, 49] proved that the internal state S₀ after KSA for the very first time is highly nonuniform. Mantin’s correlation in S₀ distribution is known to be the most beneficial internal bias of RC4 to date and give rise to more non-uniformities in the output keystream. Later in 2010 [32] to find all the linear correlations in a single round of the algorithm the authors performed an exhaustive search of all relations between states and indices ( i_r, j_r, S_r [i_r], S_r [j_r], Z_r, where r represents the round) on the space. Several new biases in RC4 relating the internal state S to the output keystream were obtained. The work presented in [32] was further extended in [50] with the goal to mount an attack on WEP and WPA by using these obtained biases.

• •    Another area of analysis is the identification of short term and long term biases in the keystream bytes. The keystream biases that do not linger on to the future rounds are named as short term biases.

The first and the second keystream byte bias was analyzed in [43, 51] and [47, 52] respectively. Authors in [47] claimed that except for Z 2 , there exist no significant initial keystream byte bias towards zero in RC4. But in [43, 53] it was proved that all the initial bytes ranging from Z 3 to Z 255 are significantly biased towards zero. Several recent short term biases are discussed and proved in [44, 51, 53, 54]. Due to the existence of number of short term biases it was suggested by many researchers to discard the initial N to 6N bytes of the output keystream. The bytes generated thereafter are to be used for encryption. The remained keystream biases even after the removal of initial bytes are termed as long term biases. Different studies related to the long term biases in the keystream are discussed in [51, 55, 56].

The available literature reveals that although there had been many successful security breaches in the RC4, but the striking combination of robustness and design elegance of RC4 has made it most preferred cipher for last two decades.

Different researchers have proposed variety of its implementations to make the cipher more secure (discussed in section 4), But the available literature demonstrate the insecurity of RC4 till date. The most recent weaknesses observed in the year 2013 and 2014 on RC4 and its applications in WEP, WPA and TLS reveals the fact that the RC4 is not secure till date and is still an attraction for community.

• IV.    Enhancements In RC4 Stream Cipher

  Due to the RC4 weaknesses and related cryptanalytic attempts as discussed in section 3, many variants of RC4 have been proposed by researchers. We have reported several enhancements of RC4 algorithm. A modified 32-bit RC4, named as RC4 (n, m) keystream generator, with good randomness and uniform distribution was proposed in [58]. The authors have claimed the resistance of cipher against all the attacks that were successful on conventional RC4. In [59] authors have developed two attacks against RC4 (n, m) on the basis of nonrandomness of internal states . In [60] authors have studied theoretically the RC4 KSA. It is found that the expected number of times each value of the state permutation is moved by the indices i, j is not uniform and proposed a modified RC4 KSA+ and PRGA+ with three layers of scrambling. Analysis of RC4+ illustrates that although the modified algorithm destroys the correlation between the state and the key but the running time of KSA+ is approximately 2.94 times than that of original RC4 KSA and the running time of one round of our PRGA+ is 1.70 times than that of original RC4 PRGA. Recently in 2013 [61] authors have successfully mounted a distinguishing attack on RC4+. To increase the security of RC4, a new PRGA, based on conventional RC4 is proposed in [62, 63]. It is revealed that the

proposed proposed RC4 has two internal states and has    foundation of many security attacks on RC4 and is also removed some of the byte biases which are the    faster than the existing conventional RC4.

Table 2. Cryptanalysis on RC4 stream cipher

Year	Weak keys and key recovery from state	Key recovery from key stream	State recovery attack	Biases and Distinguishers
1995	-Roos weak keys[10] -Wagner weak keys [12]	-	-	-Roos biases [10]
1996	-	-	-	-Glimpse bias [46]
1997	-	-	-	-Golic long term bias [53]
1998	-	-	- KMP branch and bound approach [35]
2000	-Related key-pairs[13]	-	-Iterative probabilistic cryptanalysis [36-37]	-Digraph biases [55]
2001	-	FMS WEP attack.[23]	-	Broadcast attack [47]
2002	-	-	-	-
2003	-	-	State part known [38]
2004	-	Korek WEP attack [24-25]	-
2005	-	Mantin WEP attack [26]	-
2006	-	Klein WEP attack [27]	-	-
2007	- short related keys attack [14]	-TWP WEP attack [28] -VV WEP attack [29]	Hill climb search attack [39]
2008	-Difference equations[19] -bit by bit approach attack [21]	-	-generative pattern[40] -iterative probabilistic attack [41]	Maitra and Paul conditional Bias [56]
2009	-key collision attacks[15] -bidirectional search attacks	-TB WEP and WPA attacks [30]	-	-
2010		SVV WEP attack [31]	-	SVV biases in key and state variables [32]
2011	-New key collisions [16]	SVV WEP and WPA attack [32]	-	-keylength biases [42]
2012		SVV WEP and WPA attack [33]	-
2013	-Near colliding keys [17]	SSVV passive attack on WEP [34]	-	-TLS and WPA attack [45,52] -Full Broadcast attack [44] - TLS related bias [45]
2014	-	-	-	-biased bytes [43]

Table 3. Summary of WEP attacks

Year	WEP Attack	Type	Packets required to recover WEP secret key
2001	FMS attack [23] FMS attack [57]	Passive attack and Theoretically estimated Passive attack and Proved practically	4 Lacs 5.5 Lacs
2004	Korek attack [24]	Practical attack with Aircrack-ng	1 lac
2006	Klien attack [27] Klien attack [32,33]	Passive attack and Theoretically estimated Passive attack and Proved practically	25000 60000
2007	TWP attack [28]	Passive attack and implemented Practically attack	10000
2007	VV attack [29]	Passive attack and implemented Practically attack	32700
2009	TB attack [30] TB attack [32,33]	Interactive with Aircrack-ng Non-interactive (proved) with Aircrack-ng	24200 30000
2010	SVV attack [31]	Passive attack and Theoretically estimated	9800
2011	SVV attack [32]	Passive attack and Theoretically estimated	4000
2013	SSVV attack [33]	Passive attack and Proved practically	27500
2013	SSVV attack [34]	Non-interactive (proved) with Aircrack-ng	22500
2013	SSVV attack [34]	Interactive with Aircrack-ng	19800

In [64] authors have proposed a new variant of RC4 called Quad-RC4 without changing the basic structure of conventional RC4. The proposed RC4 structure promises the reasonable security and a high throughput. In term of speed the proposed cipher performs much better in comparison with HC-128, the fastest software stream cipher amongst the e-STREAM finalists. A new variant of RC4 known as FJ-RC4 is proposed by authors in [65]. In FJ-RC4 is designed in a manner such that in KSA input key is divided into three parts and the structure of

PRGA is same as with conventional RC4. A new keystream after KSA is generated in three rounds whereas PRGA performs only single round. Another variant of RC4 known as effective RC4 cipher is proposed in [66] where the security analysis is performed by using Shannon’s Secrecy theory and numerical values are obtained to analyze the secrecy. It is proposed that the improved RC4 cipher can be used in software applications where there is requirement of both the throughput and secrecy. Further a new PRGA RC4B is proposed in [67], which provides better immunity against the known attacks. The new variant of RC4 is proposed in [68] which provides high security along with long period of KSA keystream, large complexity and having good statistical properties.

From the available literature it is found that many recent RC4 variants have been proposed by researchers. Some are targeted towards achieving better security by removing the non-uniformity of bytes or by removing the correlation between key and the state bytes and some towards better performance in terms of time or throughput. Some of the proposals have entirely changed the basic structure of RC4 which is generally not desirable because the robust design of RC4 is the basic strength of the cipher. However, inspite of so many proposals on RC4, many open issues exists on RC4 till date and are mentioned below:

• •    RC4 keystream key collisions

• •    Key recovery attacks on WPA

• •    Keylength dependent anomalies in RC4.

• •    State recovery attacks on RC4

• •    Searches of more biases,

Therefore there is a strong need of the enhanced RC4 algorithm. It is recommended that while retaining the basic structure of RC4, one can design a new enhanced RC4 stream cipher exhibiting a sufficient resistance against the existing weaknesses of the cipher.

• V. Conclusion

In this paper, a chronological survey of the cryptanalysis on RC4 was presented beginning with its first public appearance to date. We have identified and presented the various weaknesses of RC4 cipher followed by the measure taken by various researchers to improve the security of the cipher. It is found that though extensively deployed in the field, there are still certain flaws in its security. Although many improved variants of RC4 which removes the existing weaknesses and enhance the security of the cipher may be found in the literature, but the question about which is the best solution still remain unanswered, since each of them focus on specific attack or weakness. Further in spite of all the developments reported in the literature, there are still many open research challenges and issues related to searches of more biases, key collisions in keystream, and key recovery attack on WPA. Therefore it is concluded that there is ample scope to further investigate the issues in RC4 particularly the non-random behavior of bytes in the state permutation, and to develop a new, more efficient and effective RC4 encryption algorithm.