This paper presents new key correlations of the keystream bytes generated from RC4 and their application to plaintext recovery on WPA-TKIP. We first observe new key correlations between two bytes of the RC4 key pairs and a keystream byte in each round, and provide their proofs. We refer to these correlations as iterated RC4 key correlations since two bytes of the RC4 key pairs are iterated every 16 rounds. We then extend the existing attacks by Isobe et al. at FSE 2013 and AlFardan et al. at USENIX Security 2013, 0and finally propose an efficient attack on WPA-TKIP. We refer to the proposed attack as chosen plaintext recovery attack (CPRA) since it chooses the best approach for each byte from a variety of the existing attacks. In order to recover the first 257 bytes of a plaintext on WPA-TKIP with success probability of at least 90%, CPRA requires approximately 230 ciphertexts, which are approximately half the number of ciphertexts for the existing attack by Paterson et al. at FSE 2014.

In this paper we present proofs for the new biases in RC4 which were experimentally found and listed out (without theoretical justifications and proofs) in a paper by Vanhoef et al. in USENIX 2015. Their purpose was to exploit the vulnerabilities of RC4 in TLS using the set of new biases found by them. We also show (and prove) new results on couple of very strong biases residing in the joint distribution of three consecutive output bytes of the RC4 stream cipher. These biases provides completely new distinguisher for RC4 taking roughly O(224) samples to distinguish streams of RC4 from a uniformly random stream. We also provide a list of new results with proofs relating to some conditional biases in the keystreams of the RC4 stream cipher.

Spritz is a stream cipher proposed by Rivest and Schuldt at the rump session of CRYPTO 2014. It is intended to be a replacement of the popular RC4 stream cipher. In this paper we propose distinguishing attacks on the full Spritz, based on a short-term bias in the first two bytes of a keystream and a long-term bias in the first two bytes of every cycle of N keystream bytes, where N is the size of the internal permutation. Our attacks are able to distinguish a keystream of the full Spritz from a random sequence with samples of first two bytes produced by 244.8 multiple key-IV pairs or 260.8 keystream bytes produced by a single key-IV pair. These biases are also useful in the event of plaintext recovery in a broadcast attack. In the second part of the paper, we look at a state recovery attack on Spritz, in a special situation when the cipher enters a class of weak states. We determine the probability of encountering such a state, and demonstrate a state recovery algorithm that betters the 21400 step algorithm of Ankele et al. at Latincrypt 2015. Finally we propose a simple fix that removes the bias in the first two keystream bytes. The countermeasure requires only one additional memory access and hence does not diminish software performance substantially, and in fact the loss in software speed is only around 1.5%.

RC4 is a well-known stream cipher designed by Rivest. Due to considerable cryptanalysis efforts over past 20 years, several kinds of statistic biases in a key stream of RC4 have been observed so far. Finally, practical full plaintext recovery attacks on RC4 in SSL/TLS were independently proposed by AlFardan et al. and Isobe et al. in 2013. Responded to these attacks, usage of RC4 has drastically decreased in SSL/TLS. However, according to the research by Trustworthy Internet Movement, RC4 is still used by some websites for the encryption on SSL/TLS. In this paper, we shows a new plaintext recovery attack for RC4 under the assumption of HTTPS. We develop a method for exploiting single-byte and double-byte biases together to efficiently guess the target bytes, while previous attacks use either single-byte biases or double-byte biases. As a result, target plaintext bytes can be extracted with higher probability than previous best attacks given 229 ciphertexts encrypted by randomly-chosen keys. In the most efficient case, the success probability of our attack are more than twice compared to previous best attacks.

The RC4 stream cipher is widely used including WEP and WPA, which are the security protocols for IEEE 802.11 wireless standard. WPA improved a construction of the RC4 key setting known as TKIP to avoid the known WEP attacks. The first 3-byte RC4 keys generated by IV in WPA are known since IV can be obtained by observing packets. The weaknesses in TKIP using the known IV were reported by Sen Gupta et al. at FSE 2014 and by Ito and Miyaji at FSE 2015. Both showed that TKIP induces many RC4 key correlations including the keystream bytes or the unknown internal states. Ideally TKIP should be constructed in such a way that it can keep the security level of generic RC4. In the first part of this paper, we will provide newly theoretical proofs of 17 correlations remain unproven in our previous work theoretically. Our theoretical analysis can make clear how TKIP induces biases of internal states in generic RC4. In the second part of this paper, we will further provide a refined construction of the RC4 key setting. As a result, we can reduce the number of correlations in the refined construction by about 70% in comparison with that in the original setting.

WPA is the security protocol for IEEE 802.11 wireless networks standardized as a substitute for WEP in 2003, and uses RC4 stream cipher for encryption. It improved a 16-byte RC4 key generation procedure, which is known as TKIP, from that in WEP. One of the remarkable features in TKIP is that the first 3-byte RC4 key is derived from the public parameter IV, and an analysis using this feature has been reported by Sen Gupta et al. at FSE 2014. They focused on correlations between the keystream bytes and the known RC4 key bytes in WPA, which are called key correlations or linear correlations, and improved the existing plaintext recovery attack using their discovered correlations. No study, however, has focused on such correlations including the internal states in WPA. In this paper, we investigated new linear correlations including unknown internal state variables in both generic RC4 and WPA. From the result, we can successfully discover various new linear correlations, and prove some correlations theoretically.

RC4 stream cipher, designed by Rivest in 1987, is widely used in various standard protocols and commercial applications. After the disclosure of RC4 algorithm in 1994, many cryptanalytic results on RC4 have been reported. In 1996, Jenkins discovered correlations between a keystream byte and an internal state variable. This is known as the Glimpse theorem. In 2013, Maitra and Sen Gupta proved the Glimpse theorem and showed other correlations between two consecutive keystream bytes and an internal state variable. This is called the long-term Glimpse. These correlations provide only cases with positive biases, and hold generally on any round. In this paper, we refine known Glimpse correlations from two aspects. One is to find new positive or negative biases on all values in addition to a known value. The other is to provide precise biases on specific rounds. As a result, we can discover 6 cases with several new biases, and prove these cases theoretically. From the first refinement, combining our new biases with known one, the long-term Glimpse with positive biases is integrated into a whole. From the second refinement, we can successfully find that two correlations on specific rounds become an impossible condition.

RC4 is a widely-used stream cipher, adopted in many standard protocols, such as WEP, WPA and SSL/TLS, as a standard encryption algorithm. Isobe et al. proposed a plaintext recovery attack on RC4 in the broadcast setting, where the same plaintext is encrypted with different secret keys. Their attack is able to recover the first 257bytes by exploiting the biases of the initial bytes of a keystream. In this paper, we propose two types of full plaintext recovery attacks that are able to recover all the bytes, even after the 258th byte, of a plaintext, unlike Isobe et al.'s attack. To achieve this, we combine the use of multiple keystream biases appropriately. The first attack utilizes the initial byte biases and Mantin's long-term bias. This attack can recover the first 1000 terabytes of a plaintext from 234 ciphertexts with a probability of almost one. The second attack is based on two long-term biases. Since this attack does not rely on the biases of the initial bytes of the RC4 keystream, it can recover any byte of a plaintext, even if the initial bytes are disregarded. Given 235 ciphertexts encrypted by different keys, any byte of a target plaintext can be recovered with a probability close to one.

After the disclosure of the RC4 algorithm in 1994, a number of keystream biases of RC4 were reported, e.g., Mantin and Shamir showed that the second byte of the keystream is biased to 0, Sepehrdad et al. found that the l-th byte of the keystream is biased to -l, and Maitra et al. showed that 3rd to 255th bytes of the keystream are also biased to 0, where l is the keylength in byte. However, it is unknown that which bias is strongest in each byte of initial bytes. This paper comprehensively analyzes initial keystream biases of RC4. In particular, we introduce several new biases in the initial (1st to 257th) bytes of the RC4 keystream, which are substantially stronger than known biases. Combining the new biases with the known ones, a complete list of strongest single-byte biases in the first 257bytes of the RC4 keystream is constructed for the first time. Then, we show that our set of these biases are applicable to plaintext recovery attacks, key recovery attacks and distinguishing attacks.

Thanks to the achievements in wireless technology, maximum data rate of wireless LAN systems was rapidly increased recently. As a key part of the WEP and the WPA security for the wireless LAN system, throughput of RC4 must be significantly improved also. This paper proposes two high throughput RC4 architectures. The first one is a RAM-based RC4 using a single of 256-byte tri-port RAM to store the S-box. The core generates 4bits of ciphering key per clock cycle. This paper also proves that 4bits/cycle is the maximum throughput can be achieved by a RAM-based RC4 circuit. The second architecture is a Register-based M-byte RC4 that uses a set of registers to store the S-box. It is able to generate multiple bytes of ciphering key per clock cycle, and is proposed as a novel solution for designing extremely high throughput RC4 core for future WLAN systems. Base on this proposal, a 4-byte RC4 core is developed (M=4). The synthesis results in 90nm ASIC show that: As the same throughput's requirement, the proposed RAM-based and Register-based RC4 can respectively save 60% and 50% of power consumption as compare to that of the most recently works. Moreover, the proposed Register-based design is the best candidate for achieving high throughput at low frequency.

In this paper, we propose two new attacks against stream cipher RC4 which can recover the secret key in different length with practical computational amount. However, we have to point out that the proposed attacks are performed under relatively strong related key models. The same as the usual related key models, the adversary can specify the key differentials without knowing the target key information. However, in our attacks, only the relation between two keystream outputs or the two final internal states are required for the attacker. In addition, we discover a statistical bias of RC4 which is the key point to one of the attacks. Besides the inappropriate usage during the WEP environment, RC4 is still considered to be secure with the proper setting, and we believe the result of this paper will add to the understanding of RC4 and how to use it correctly and safely.

In recent years, wireless LAN systems are widely used in campuses, offices, homes and so on. It is important to discuss the security aspect of wireless LAN networks in order to protect data confidentiality and integrity. The IEEE Standards Association formulated some security protocols, for example, Wired Equivalent Privacy (WEP) and Wi-Fi Protected Access Temporal Key Integrity Protocol (WPA-TKIP). However, these protocols have vulnerability for secure communication. In 2008, we proposed an efffective key recovery attack against WEP and it is called the TeAM-OK attack. In this paper, first, we present a different interpretation and the relation between other attacks and the TeAM-OK attack against WEP. Second, we present some existing attacks against WPA-TKIP and these attacks are not executable in a realistic environment. Then we propose an attack that is executable in a realistic environment against WPA-TKIP. This attack exploits the vulnerability implementation in the QoS packet processing feature of IEEE 802.11e. The receiver receives a falsification packet constructed as part of attack regardless of the setting of IEEE 802.11e. This vulnerability removes the attacker's condition that access points support IEEE 802.11e. We confirm that almost all wireless LAN implementations have this vulnerability. Therefore, almost all WPA-TKIP implementations cannot protect a system against the falsification attack in a realistic environment.

The fact that the stream cipher RC4 can generate colliding key pairs with hamming distance one was first discovered by Matsui in FSE 2010. This kind of weakness demonstrates that two different secret keys have the same effect on the cipher's encryption and the corresponding decryption procedure. In this paper, we further investigate the property of RC4 key collisions and achieved the following results: 1. We show that RC4 can generate colliding key pairs with various hamming distances, which cannot be generated by Matsui's pattern. We also give concrete examples of colliding key pairs with hamming distances greater than one. 2. We formalize RC4 colliding key pairs into two large patterns, namely, Transitional pattern and Self-Absorbing pattern. All the currently known colliding key pairs can be categorized into either two patterns. 3. We analyze both patterns and clarified the relations among the probability of key collision, key length and hamming distances which yield the colliding key pairs. 4. We demonstrate the vulnerability of key collisions by showing collisions of RC4-Hash function proposed in INDOCRYPT 2006. Some concrete experimental results of RC4-Hash collision are also given in this paper.

Conventional class of weak keys on RC4 stream cipher is defined as a specific case that combinations of the first three bytes of secret key satisfy two relational equations. This paper expands and generalizes the classes of weak keys using generalized relational equations and special classes of the internal state (called predictive state). We derive the probability that generalized classes of weak keys leak the information of bytes of the secret key. Furthermore, we enumerate the generalized classes of weak keys and show that most of them leak more information of the secret key than Roos' one.

RC4 is the stream cipher proposed by Rivest in 1987, which is widely used in a number of commercial products because of its simplicity and substantial security. RC4 exploits shuffle-exchange paradigm, which uses a permutation S. Many attacks have been reported so far. No study, however, has focused on correlations in the Pseudo-Random Generation (PRGA) between two permutations S and S' with some differences, nevertheless such correlations are related to an inherent weakness of shuffle-exchange-type PRGA. In this paper, we investigate the correlations between S and S' with some differences in the initial round. We show that correlations between S and S' remain before "i" is in the position where the nonzero-bit difference exists in the initial round, and that the correlations remain with non negligible probability even after "i" passed by the position. This means that the same correlations between S and S' will be observed after the 255-th round. This reveals an inherent weakness of shuffle-exchange-type PRGA.

Conventional efficient key recovery attacks against Wired Equivalent Privacy (WEP) require specific initialization vectors or specific packets. Since it takes much time to collect the packets sufficiently, any active attack should be performed. An Intrusion Detection System (IDS), however, will be able to prevent the attack. Since the attack logs are stored at the servers, it is possible to prevent such an attack. This paper proposes an algorithm for recovering a 104-bit WEP key from any IP packets in a realistic environment. This attack needs about 36,500 packets with a success probability 0.5, and the complexity of our attack is equivalent to about 220 computations of the RC4 key setups. Since our attack is passive, it is difficult for both WEP users and administrators to detect our attack.

The WEP (Wired Equivalent Privacy) is a part of IEEE 802.11 standard designed for protecting over-the-air communication. While almost all of the WLAN (Wireless LAN) cards and the APs (Access Points) support WEP, a serious key recovery attack (aka FMS attack) was identified by Fluhrer et al. The FMS attack can basically be prevented by skipping IVs (Initial Values) used in the attack, but naive skip methods reveal information on the WEP key since most of them depend on the WEP key and the patterns of the skipped IV reveal it. In order to skip IVs safely, the skip patterns must be chosen carefully. In this paper, we review the attack conditions (6) and (7), whose success probability is the highest, 0.05, amongst all known conditions to guess one key-byte from one packet. Then we identify their safe skip patterns.

In a key scheduling algorithm (KSA) of stream ciphers, a secret key is expanded into a large initial state. An internal state reconstruction method is known as a general attack against stream ciphers; it recovers the initial state from a given pair of plaintext and ciphertext more efficiently than exhaustive key search. If the method succeeds, then it is desirable that the inverse of KSA is infeasible in order to avoid the leakage of the secret key information. This paper shows that it is easy to compute a secret key from an initial state of RC4. We propose a method to recover an -bit secret key from only the first bits of the initial state of RC4 using linear equations with the time complexity less than that of one execution of KSA. It can recover the secret keys of which number is 2103.6 when the size of the secret key is 128 bits. That is, the 128-bit secret key can be recovered with a high probability when the first 128 bits of the initial state are determined using the internal state reconstruction method.

The WEP (Wired Equivalent Privacy) is a part of IEEE 802.11 standard designed for protecting over the air communication. While almost all of the WLAN (Wireless LAN) cards and the APs (Access Points) support WEP, a serious key recovery attack (aka FMS attack) was identified by Fluhrer et al. The attack was then extended and implemented as WEP cracking tools. The key recovery attacks can basically be prevented by skipping certain IVs (Initial Values) called weak IVs, but the problem is that there exist huge amount of key-dependent weak IVs and the patterns of them have not been fully identified yet. The difficult part is that a naive approach to identify the key-dependent weak IVs requires the exhaustive search of IVs and WEP keys, and hence is infeasible. On the other hand, it might be feasible to skip the key-dependent weak IVs for the currently set WEP key but this reveals information on the WEP key from the skipped patterns. To skip them safely, the patterns of the key-dependent weak IVs must be identified in the first place. In this paper, we analyze the famous condition for IVs and WEP keys to be weak in the FMS attack, i.e. 0≤S[1]≤t'

Knudsen et al. proposed an efficient method based on a tree-search algorithm with recursive process for reconstructing the internal state of RC4 stream cipher. However, the method becomes infeasible for word size n > 5 because its time complexity to reconstruct the internal state is too large. This letter proposes a more efficient method than theirs. Our method can reconstruct the internal state by using the pre-known internal-state entries, which are fewer than their method.