Proving empirical key-correlations in RC4

•We justify significant empirical biases related to RC4 reported in SAC 2010.•We prove that P(Z4=−4+K[0]−K[4])=1.04N.•Our experimental data also corroborate this claim.

In view of the recent attacks on practical network protocols like WEP, WPA and TLS, there has been a renewed interest in the non-random behavior of RC4, the stream cipher that constitutes the core of all these protocols. While most of the non-random events in the cipher, more commonly known as ‘biases’, are initially reported as experimental observations, it is equally important to present theoretical proofs of such biases to justify the attacks based on these. In this paper, we provide theoretical proofs of all significant empirical correlations between the initial bytes of the RC4 keystream and its secret key, as experimentally observed by Sepehrdad, Vaudenay and Vuagnoux in SAC 2010.