Paper 2007/208

RC4 State Information at Any Stage Reveals the Secret Key

Goutam Paul and Subhamoy Maitra

Abstract

A theoretical analysis of the RC4 Key Scheduling Algorithm (KSA) is presented in this paper, where the nonlinear operation is swapping among the permutation bytes. Explicit formulae are provided for the probabilities with which the permutation bytes at any stage of the KSA are biased to the secret key. Theoretical proofs of these formulae have been left open since Roos' work (1995). Next, a generalization of the RC4 KSA is analyzed corresponding to a class of update functions of the indices involved in the swaps. This reveals an inherent weakness of shuffle-exchange kind of key scheduling. We additionally show that each byte of $S_N$ actually reveals secret key information. Looking at all the elements of the final permutation $S_N$ and its inverse $S^{-1}_N$, the value of the hidden index $j$ in each round of the KSA can be estimated from a ``pair of values" in $0, \ldots, N-1$ with a constant probability of success $\pi = \frac{N-2}{N}\cdot(\frac{N-1}{N})^{N-1} + \frac{2}{N}$ (we get $\pi \approx 0.37$, for $N = 256$), which is significantly higher than the random association. Using the values of two consecutive $j$'s, we estimate the $y$-th key byte from at most a ``quadruple of values" in $0, \ldots, N-1$ with a probability $> 0.12$. As a secret key of $l$ bytes is repeated at least $\lfloor \frac{N}{l}\rfloor$ times in RC4, these many quadruples can be accumulated to get each byte of the secret key with very high probability (e.g., 0.8 to close to 1) from a small set of values. Based on our analysis of the key scheduling, we show that the secret key of RC4 can be recovered from the state information in a time much less than the exhaustive search with good probability.

Note: Reorganized the paper for better clarity.