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 shuffleexchange 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, N1$ with a constant probability of success $\pi = \frac{N2}{N}\cdot(\frac{N1}{N})^{N1} + \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, N1$ 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.
Metadata
 Available format(s)
 Category
 Secretkey cryptography
 Publication info
 Published elsewhere. SAC 2007
 Keywords
 BiasCryptanalysisKey RecoveryKey SchedulingPermutationRC4Stream Cipher.
 Contact author(s)
 subho @ isical ac in
 History
 20090109: last of 6 revisions
 20070605: received
 See all versions
 Short URL
 https://ia.cr/2007/208
 License

CC BY
BibTeX
@misc{cryptoeprint:2007/208, author = {Goutam Paul and Subhamoy Maitra}, title = {RC4 State Information at Any Stage Reveals the Secret Key}, howpublished = {Cryptology ePrint Archive, Paper 2007/208}, year = {2007}, note = {\url{https://eprint.iacr.org/2007/208}}, url = {https://eprint.iacr.org/2007/208} }