International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

New State Recovery Attack on RC4

Authors:
Alexander Maximov
Dmitry Khovratovich
Download:
URL: http://eprint.iacr.org/2008/017
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2008-17694,
  title={New State Recovery Attack on RC4},
  booktitle={IACR Eprint archive},
  keywords={RC4, state recovery attack, key recovery attack.},
  url={http://eprint.iacr.org/2008/017},
  note={ Alexander.Maximov@ericsson.com 13929 received 10 Jan 2008, last revised 20 Feb 2008},
  author={Alexander Maximov and Dmitry Khovratovich},
  year=2008
}