Comprehensive Analysis of Initial Keystream Biases of RC4 |
|
Takanori Isobe, Toshihiro Ohigashi, Yuhei Watanabe, Masakatu Morii |
|
|
 Takanori Isobe |
 Toshihiro Ohigashi |
 Yuhei Watanabe |
 Masakatu Morii |
After the disclosure of the RC4 algorithm in 1994, a number of cryptanalytic results have been published, e.g., state-recovery attacks, weak keys and key-stream prediction attacks. Among them, statistics biases of keystreams have received much attentions from the cryptography community, e.g., Mantin and Shamir showed that the second byte of the keystream is strongly biased to 0 in 2001, Sepehrdad et al. found that the ℓ-th byte of the keystream is biased to -ℓ in 2010, and Maitra et al. showed that 3rd to 255th bytes of the keystream are also biased to 0 in 2011, where ℓ is the keylength in the unit of bytes. In spite of considerable cryptanalytic efforts over twenty years, practical attacks have not been shown. This is the reason why RC4 is still widely used despite several weaknesses having been pointed out.
In this paper, the authors comprehensively analyzed initial keystream biases of RC4, and developed practically applicable attacks on RC4 in actual environments. In particular, they introduced several new biases which are substantially stronger than known biases in the initial (1st to 257th) bytes of the RC4 keystream. Combining the new biases with the known ones, a complete list of strongest single-byte biases in the first 257 bytes of the RC4 keystream was constructed for the first time. Then, they showed that the set of these biases is applicable to plaintext recovery attacks, key recovery attacks and distinguishing attacks. In particular, their plaintext attacks are practically feasible in actual settings such as a broadcast setting and the multisession setting in SSL/TLS.
In summary, this paper provides the first practical attacks on RC4 in actual environments and reveals the crucial weakness of RC4. Also, the results contributed to the CRYPTREC project aimed at evaluating the security of e-Government recommended ciphers. Thus, this paper is worthy of being a candidate for the best paper award from industrial and academic points of view.
