Abstract
RC4, a stream cipher designed by Rivest for RSA Data Security Inc., has found several commercial applications, but little public analysis has been done to date. In this paper, alleged RC4 (hereafter called RC4) is described and existing analysis outlined. The properties of RC4, and in particular its cycle structure, are discussed. Several variants of a basic “tracking” attack are described, and we provide experimental results on their success for scaled-down versions of RC4. This analysis shows that, although the full-size RC4 remains secure against known attacks, keystreams are distinguishable from randomly generated bit streams, and the RC4 key can be recovered if a significant fraction of the full cycle of keystream bits is generated (while recognizing that for a full-size system, the cycle length is too large for this to be practical). The tracking attacks discussed provide a significant improvement over the exhaustive search of the full RC4 keyspace. For example, the state of a 5 bit RC4-like cipher can be obtained from a portion of the keystream using 242 steps, while the nominal keyspace of the system is 2160. More work is necessary to improve these attacks in the case where a reduced keyspace is used.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
T. Dierks and C. Allen. The TLS protocol version 1.0. Internet Draft, ftp://ftp.ietf.org/internet-drafts/draft-ietf-tls-protocol-05.txt, November 1997.
H. Finney. An RC4 cycle that can’t happen. Posting to sci.crypt, Sept. 1994.
J. D. Golić. Linear statistical weakness of alleged RC4 keystream generator. In Walter Fumy, editor, LNCS 1233, Advances in Cryptology-EUROCRYPT’ 97, pages 226–238, Germany, 1997. Springer.
R. J. Jenkins Jr. Re: RC4? Posting to sci.crypt, Sept 1994.
R. J. Jenkins Jr. ISAAC and RC4. Internet document at http://ourworld. compuserve.com/homepages/bob_jenkins/isaac.htm, 1996.
S. Mister. Cryptanalysis of RC4-like stream ciphers. Master’s thesis, Queen’s University, Kingston, Ontario, 1998.
S. Mister and S. E. Tavares. Some results on the cryptanalysis of RC4. In Proceedings of the 19th Biennial Symposium on Communications, pages 393–397, Kingston, Ontario, June 1–3, 1998.
L. O’Connor. Private communication, August 1998.
R. L. Rivest. The RC4 encryption algorithm. RSA Data Security Inc., March 1992.
A. Roos. A class of weak keys in the RC4 stream cipher. Posting to sci.crypt, Sept. 1995.
B. Schneier. Applied Cryptography. John Wiley & Sons, Inc., Toronto, Canada, 2nd edition, 1996.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mister, S., Tavares, S.E. (1999). Cryptanalysis of RC4-like Ciphers. In: Tavares, S., Meijer, H. (eds) Selected Areas in Cryptography. SAC 1998. Lecture Notes in Computer Science, vol 1556. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48892-8_11
Download citation
DOI: https://doi.org/10.1007/3-540-48892-8_11
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65894-8
Online ISBN: 978-3-540-48892-7
eBook Packages: Springer Book Archive