How to Efficiently Exploit Different Types of Biases for Plaintext Recovery of RC4

Yuhei WATANABE  Takanori ISOBE  Toshihiro OHIGASHI  Masakatu MORII  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E100-A   No.3   pp.803-810
Publication Date: 2017/03/01
Online ISSN: 1745-1337
Type of Manuscript: PAPER
Category: Cryptography and Information Security
RC4,  SSL/TLS,  plaintext recovery attack,  keystream biases,  

Full Text: PDF(937.9KB)
>>Buy this Article

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.