Full Plaintext Recovery Attacks on RC4 Using Multiple Biases

Toshihiro OHIGASHI, Takanori ISOBE, Yuhei WATANABE, Masakatu MORII

Summary :

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 2³⁴ 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 2³⁵ ciphertexts encrypted by different keys, any byte of a target plaintext can be recovered with a probability close to one.

• Publication: IEICE TRANSACTIONS on Fundamentals 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

Authors

Toshihiro OHIGASHI
  Hiroshima University
Takanori ISOBE
  Kobe University
Yuhei WATANABE
  Kobe University
Masakatu MORII
  Kobe University

Keyword

RC4,  stream cipher,  keystream biases,  plaintext recovery attack,  guess-and-determine attack,  broadcast setting