Theoretical Understanding of Some Conditional and Joint Biases in RC4 Stream Cipher

In this paper we present proofs for the new biases in RC4 which were experimentally found and listed out (without theoretical justifications and proofs) in a paper by Vanhoef et al. in USENIX 2015. Their purpose was to exploit the vulnerabilities of RC4 in TLS using the set of new biases found by them. We also show (and prove) new results on couple of very strong biases residing in the joint distribution of three consecutive output bytes of the RC4 stream cipher. These biases provides completely new distinguisher for RC4 taking roughly O (2(24)) samples to distinguish streams of RC4 from a uniformly random stream. We also provide a list of newresults with proofs relating to some conditional biases in the keystreams of the RC4 stream cipher.