Full Plaintext Recovery Attacks on RC4 Using Multiple Biases

Toshihiro OHIGASHI  Takanori ISOBE  Yuhei WATANABE  Masakatu MORII  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E98-A   No.1   pp.81-91
Publication Date: 2015/01/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E98.A.81
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Symmetric Key Based Cryptography
RC4,  stream cipher,  keystream biases,  plaintext recovery attack,  guess-and-determine attack,  broadcast setting,  

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

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.