Abstract
The paper presents a new statistical bias in the distribution of the first two output bytes of the RC4 keystream generator. The number of outputs required to reliably distinguish RC4 outputs from random strings using this bias is only 225 bytes. Most importantly, the bias does not disappear even if the initial 256 bytes are dropped. This paper also proposes a new pseudorandom bit generator, named RC4A, which is based on RC4’s exchange shuffle model. It is shown that the new cipher offers increased resistance against most attacks that apply to RC4. RC4A uses fewer operations per output byte and offers the prospect of implementations that can exploit its inherent parallelism to improve its performance further.
This work was partially supported by the Concerted Research Action GOA-MEFISTO-666 of the Flemish government.
Chapter PDF
Similar content being viewed by others
References
Finney, H.: An RC4 cycle that can’t happen. Post in sci. crypt (September 1994)
Fluhrer, S., Mantin, I., Shamir, A.: Weaknesses in the Key Scheduling Algorithm of RC4. In: Vaudenay, S., Youssef, A.M. (eds.) SAC 2001. LNCS, vol. 2259, pp. 1–24. Springer, Heidelberg (2001)
Fluhrer, S., McGrew, D.: Statistical Analysis of the Alleged RC4 Keystream Generator. In: Schneier, B. (ed.) FSE 2000. LNCS, vol. 1978, pp. 19–30. Springer, Heidelberg (2000)
Golić, J.: Linear Statistical Weakness of Alleged RC4 Keystream Generator. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 226–238. Springer, Heidelberg (1997)
Grosul, A., Wallach, D.: A related key cryptanalysis of RC4. Department of Computer Science, Rice University, Technical Report TR-00-358 (June 2000)
Jenkins, R.: Isaac and RC4. Published on the Internet, at http://burtleburtle.net/bob/rand/isaac.html
Knudsen, L., Meier, W., Preneel, B., Rijmen, V., Verdoolaege, S.: Analysis Methods for (Alleged) RC4. In: Ohta, K., Pei, D. (eds.) ASIACRYPT 1998. LNCS, vol. 1514, pp. 327–341. Springer, Heidelberg (1998)
Knuth, D.E.: The Art of Computer Programming. Seminumerical Algorithms, vol. 2. Addison-Wesley Publishing Company, Reading (1981)
Mantin, I., Shamir, A.: A Practical Attack on Broadcast RC4. In: Matsui, M. (ed.) FSE 2001. LNCS, vol. 2355, pp. 152–164. Springer, Heidelberg (2001)
Mironov, I.: Not (So) Random Shuffle of RC4. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 304–319. Springer, Heidelberg (2002)
Mister, S., Tavares, S.: Cryptanalysis of RC4-like Ciphers. In: Tavares, S., Meijer, H. (eds.) SAC 1998. LNCS, vol. 1556, pp. 131–143. Springer, Heidelberg (1999)
Paul, S., Preneel, B.: Analysis of Non-fortuitous Predictive States of the RC4 Keystream Generator. In: Johansson, T., Maitra, S. (eds.) INDOCRYPT 2003. LNCS, vol. 2904, pp. 52–67. Springer, Heidelberg (2003)
Preneel, B., et al.: NESSIE Security Report. Version 2.0, IST-1999-12324, February 19 (2003), http://www.cryptonessie.org
Pudovkina, M.: Statistical Weaknesses in the Alleged RC4 keystream generator. Cryptology ePrint Archive 2002–171, IACR (2002)
Roos, A.: Class of weak keys in the RC4 stream cipher. Post in sci. crypt (September 1995)
Stubblefield, A., Ioannidis, J., Rubin, A.: Using the Fluhrer, Mantin and Shamir attack to break WEP. In: Proceedings of the 2002 Network and Distributed Systems Security Symposium, pp. 17–22 (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Paul, S., Preneel, B. (2004). A New Weakness in the RC4 Keystream Generator and an Approach to Improve the Security of the Cipher. In: Roy, B., Meier, W. (eds) Fast Software Encryption. FSE 2004. Lecture Notes in Computer Science, vol 3017. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-25937-4_16
Download citation
DOI: https://doi.org/10.1007/978-3-540-25937-4_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22171-5
Online ISBN: 978-3-540-25937-4
eBook Packages: Springer Book Archive
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.