Welcome to the resource topic for 2007/208
Title:
RC4 State Information at Any Stage Reveals the Secret Key
Authors: Goutam Paul, 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.
ePrint: https://eprint.iacr.org/2007/208
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .