Ryoma Ito
abstract
A stream cipher is often used as a cryptographic scheme for processing communication data at a high speed. Therefore, it is important to evaluate the security of stream ciphers in keeping with the background that high-speed data processing is required with the development of the advanced information and communications society. This dissertation presents a study on statistical cryptanalysis of stream ciphers, and focuses particularly on RC4. First of all, we investigate certain events with statistical weakness known as a bias or a correlation involving the secret key, the internal state, or the pseudorandom number sequence called the keystream of RC4. We then apply new events with statistical weakness to the existing attacks, for example, a plaintext recovery attack, a key recovery attack, and a state recovery attack, and attempt to improve them. Finally, we propose a countermeasure to avoid the occurrence of the events with statistical weakness, especially in WPA-TKIP, which uses RC4 stream cipher for encryption/decryption. Our purpose in this dissertation is to contribute to security evaluations of stream ciphers through cryptanalysis of RC4 in the future. Our contributions can be summarized as follows. We first focus on Glimpse Correlations between the keystream and the internal state. The existing Glimpse Correlations provide only cases with positive biases, and hold generally on any round. We then refine the existing Glimpse Correlations from two approaches. One is to investigate certain events with positive or negative biases on all values in addition to a known value in the existing Glimpse Correlations. The other is to investigate certain events with different biases on specific rounds from the new and existing Glimpse Correlations. As a result of our investigation, we provide six events with several new biases, and prove these events theoretically. We then investigate correlations between the unknown internal state and the public RC4 key in WPA-TKIP, which are referred to as key correlations of the internal state variables. One of the remarkable features of WPA-TKIP is that the first three bytes of the RC4 key are set from the public parameters, and our investigation uses this feature. As a result of our investigation, we provide 22 events with key correlations of the internal state variables, and prove these events theoretically. Our theoretical proofs make clear how TKIP induces biases in the internal state of generic RC4. We then discuss a countermeasure toward secure RC4 key setting in WPA-TKIP in such a way that it can retain the security level of generic RC4. As a result of our discussion, we demonstrate that the number of key correlations induced by our refined RC4 key setting can be reduced by approximately 70% in comparison with that in the original setting in WPA-TKIP. We further investigate correlations between two bytes of the RC4 key and the keystream in each round, where the RC4 key pairs are iterated every specific rounds. Such correlations are referred to as the iterated RC4 key correlations. As a result of our investigation, we prove new events with the iterated RC4 key correlations theoretically. Furthermore, we apply new events with the iterated RC4 key correlations to the existing plaintext recovery attacks on WPA-TKIP. As a result of our experiments, we achieve to recover the first 257 bytes of a plaintext on WPA-TKIP from approximately 2^{30} ciphertexts with a success probability of approximately 90.8%, whose probability is approximately 6.0% higher than a success probability of the existing best attack. Finally, we conclude this dissertation by summarizing our results and future works, and provide a direction to construct secure stream ciphers generally based on our statistical cryptanalysis of RC4 stream cipher.
