Paper 2008/348
Iterative Probabilistic Reconstruction of RC4 Internal States
Jovan Golic and Guglielmo Morgari
Abstract
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.
Metadata
- Available format(s)
- PS
- Category
- Secret-key cryptography
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- stream ciphersRC4iterative probabilistic cryptanalysisguess-and-determine attacks
- Contact author(s)
- jovan golic @ telecomitalia it
- History
- 2008-08-11: received
- Short URL
- https://ia.cr/2008/348
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2008/348,
author = {Jovan Golic and Guglielmo Morgari},
title = {Iterative Probabilistic Reconstruction of RC4 Internal States},
howpublished = {Cryptology ePrint Archive, Paper 2008/348},
year = {2008},
note = {\url{https://eprint.iacr.org/2008/348}},
url = {https://eprint.iacr.org/2008/348}
}
