You are looking at a specific version 20090109:071827 of this paper. See the latest version.

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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. SAC 2007
Keywords
BiasCryptanalysisKey RecoveryKey SchedulingPermutationRC4Stream Cipher.
Contact author(s)
subho @ isical ac in
History
2009-01-09: last of 6 revisions
2007-06-05: received
See all versions
Short URL
https://ia.cr/2007/208
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.