New State Recovery Attack on RC4

Alexander Maximov; Dmitry Khovratovich

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 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 operations, whereas the best previous attack needs of time. Moreover, we show that if the secret key is of length 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: RC4 state recovery attack key 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},
      url = {https://eprint.iacr.org/2008/017}
}