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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.