How to Recover Any Byte of Plaintext on RC4

摘要

In FSE 2013, Isobe et al. proposed efficient plaintext recovery attacks on RC4 in the broadcast setting where the same plaintext is encrypted with different user keys. Their attack is able to recover first 1000 terabytes of a plaintext with probability of almost one, given 234 ciphertexts encrypted by different keys. Since their attack essentially exploits biases in the initial (1st to 257th) bytes of the keystream, it does not work any more if such initial bytes are disregarded. This paper proposes two advanced plaintext recovery attacks that can recover any byte of a plaintext without relying on initial biases, i.e., our attacks are feasible even if initial bytes of the keystream are disregarded. The first attack is the modified Isobe et al.'s attack. Using the partial knowledge of the target plaintext, e.g., only 6 bytes of the plaintext, the other bytes can be recovered with the high probability from 2~(34) ciphertexts. The second attack does not require any previous knowledge of a plaintext. In order to achieve it, we develop a guess-and-determine plaintext recovery method based on two strong long-term biases. Given 2~(35) ciphertexts, any byte of a plaintext can be recovered with probability close to one.