International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: RC4 State Information at Any Stage Reveals the Secret Key

Goutam Paul
Subhamoy Maitra
Search ePrint
Search Google
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's work (1995). Based on this analysis, an algorithm is devised to recover the $l$ bytes (i.e., $8l$ bits, typically $5 \leq l \leq 16)$ secret key from the permutation after any round of the KSA with constant probability of success. The search requires $O(2^{4l})$ many operations which is the square root of the exhaustive key search complexity $2^{8l}$. Moreover, given the state information, i.e., (a) the permutation, (b) the number of bytes generated (which is related to the index $i$) and (c) the value of the index $j$, after any number of rounds in Pseudo-Random Generation Algorithm (PRGA) of RC4, one can deterministically get back to the permutation after the KSA and thereby extract the keys efficiently with a constant probability of success. Finally, 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.
  title={RC4 State Information at Any Stage Reveals the Secret Key},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / Bias, Cryptanalysis, Key Recovery, Key Scheduling, Permutation, RC4, Stream Cipher.},
  note={ 13752 received 1 Jun 2007, last revised 27 Aug 2007},
  author={Goutam Paul and Subhamoy Maitra},