## CryptoDB

### Paper: Iterative Probabilistic Reconstruction of RC4 Internal States

Authors: Jovan Golic Guglielmo Morgari URL: http://eprint.iacr.org/2008/348 Search ePrint Search Google It is shown that an improved version of a previously proposed iterative probabilistic algorithm, based on forward and backward probability recursions along a short keystream segment, is capable of reconstructing the RC4 internal states from a relatively small number of known initial permutation entries. Given a modulus $N$, it is argued that about $N/3$ and $N/10$ known entries are sufficient for success, for consecutive and specially generated entries, respectively. The complexities of the corresponding guess-and-determine attacks are analyzed and, e.g., for $N=256$, the data and time complexities are (conservatively) estimated to be around $D \approx 2^{41}$, $C \approx 2^{689}$ and $D \approx 2^{211}$, $C \approx 2^{262}$, for the two types of guessed entries considered, respectively.
##### BibTeX
@misc{eprint-2008-18025,
title={Iterative Probabilistic Reconstruction of RC4 Internal States},
booktitle={IACR Eprint archive},
keywords={secret-key cryptography/stream ciphers, RC4, iterative probabilistic cryptanalysis, guess-and-determine attacks},
url={http://eprint.iacr.org/2008/348},
note={ jovan.golic@telecomitalia.it 14099 received 8 Aug 2008, last revised 8 Aug 2008},
author={Jovan Golic and Guglielmo Morgari},
year=2008
}