This paper introduces significant improvements over the existing cryptanalysis approaches on Salsa20 and ChaCha stream ciphers. For the first time, we reduced the attack complexity on Salsa20/8 to the lowest possible margin. We introduced an attack on ChaCha7.25. It is the first attack of its type on ChaCha7.25/20. In our approach, we studied differential cryptanalysis of the Salsa20 and ChaCha stream ciphers based on a comprehensive analysis of probabilistic neutral bits (PNBs). The existing differential cryptanalysis approaches on Salsa20 and ChaCha stream ciphers first study the differential bias at specific input and output differential positions and then search for probabilistic neutral bits. However, the differential bias and the set of PNBs obtained in this method are not always the ideal combination to conduct the attack against the ciphers. The researchers have not focused on the comprehensive analysis of the probabilistic neutrality measure of all key bits concerning all possible output difference positions at all possible internal rounds of Salsa20 and ChaCha stream ciphers. Moreover, the relationship between the neutrality measure and the number of inverse quarter rounds has not been scrutinized yet. To address these study gaps, we study the differential cryptanalysis based on the comprehensive analysis of probabilistic neutral bits on the reduced-round Salsa20 and ChaCha. At first, we comprehensively analyze the neutrality measure of 256 key bits positions. Afterward, we select the output difference bit position with the best average neutrality measure and look for the corresponding input differential with the best differential bias. Considering all aspects, we present an attack on Salsa20/8 with a time complexity of 2241.62 and data complexity of 231.5, which is the best-known single bit differential attack on Salsa20/8 and then, we introduced an attack on ChaCha7.25 rounds with a time complexity of 2254.011 and data complexity of 251.81.

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.

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.

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.

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.