Paper 2008/017
New State Recovery Attack on RC4
Alexander Maximov and Dmitry Khovratovich
Abstract
The stream cipher RC4 was designed by R.~Rivest in 1987, and it has a very simple and elegant structure. It is probably the most deployed cipher on the Earth. ~~~~In this paper we analyse the class RC4-$N$ of RC4-like stream ciphers, where $N$ is the modulus of operations, as well as the length of internal arrays. Our new attack is a state recovery attack which accepts the keystream of a certain length, and recovers the internal state. For the original RC4-256, our attack has total complexity of around $2^{241}$ operations, whereas the best previous attack needs $2^{779}$ of time. Moreover, we show that if the secret key is of length $N$ bits or longer, the new attack works faster than an exhaustive search. The algorithm of the attack was implemented and verified on small cases.
Metadata
- Available format(s)
-
PDF
PS
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- RC4state recovery attackkey recovery attack.
- Contact author(s)
- Alexander Maximov @ ericsson com
- History
- 2008-02-20: revised
- 2008-01-14: received
- See all versions
- Short URL
- https://ia.cr/2008/017
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2008/017,
author = {Alexander Maximov and Dmitry Khovratovich},
title = {New State Recovery Attack on RC4},
howpublished = {Cryptology ePrint Archive, Paper 2008/017},
year = {2008},
note = {\url{https://eprint.iacr.org/2008/017}},
url = {https://eprint.iacr.org/2008/017}
}
