Full Plaintext Recovery Attack on Broadcast RC4

Abstract. This paper investigates the practical security of RC4 in broad-cast setting where the same plaintext is encrypted with different user keys. We introduce several new biases in the initial (1st to 257th) bytes of the RC4 keystream, which are substantially stronger than known bi-ases. Combining the new biases with the known ones, a cumulative list of strong biases in the first 257 bytes of the RC4 keystream is constructed. We demonstrate a plaintext recovery attack using our strong bias set of initial bytes by the means of a computer experiment. Almost all of the first 257 bytes of the plaintext can be recovered, with probability more than 0.8, using only 232 ciphertexts encrypted by randomly-chosen keys. We also propose an efficient method to extract later bytes of the plain-text, after the 258th byte. The proposed method exploits our bias set of first 257 bytes in conjunction with the digraph repetition bias proposed by Mantin in EUROCRYPT 2005, and sequentially recovers the later bytes of the plaintext after recovering the first 257 bytes. Once the pos-sible candidates for the first 257 bytes are obtained by our bias set, the later bytes can be recovered from about 234 ciphertexts with probability close to 1