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.

After the disclosure of the RC4 algorithm in 1994, a number of keystream biases of RC4 were reported, e.g., Mantin and Shamir showed that the second byte of the keystream is biased to 0, Sepehrdad et al. found that the l-th byte of the keystream is biased to -l, and Maitra et al. showed that 3rd to 255th bytes of the keystream are also biased to 0, where l is the keylength in byte. However, it is unknown that which bias is strongest in each byte of initial bytes. This paper comprehensively analyzes initial keystream biases of RC4. In particular, we introduce several new biases in the initial (1st to 257th) bytes of the RC4 keystream, which are substantially stronger than known biases. Combining the new biases with the known ones, a complete list of strongest single-byte biases in the first 257bytes of the RC4 keystream is constructed for the first time. Then, we show that our set of these biases are applicable to plaintext recovery attacks, key recovery attacks and distinguishing attacks.