A New Weakness in the RC4 Keystream Generator and an Approach to Improve the Security of the Cipher

     Souradyuti Paul and Bart Preneel

Publication Info: FSE 2004,  Lecture Notes in Computer Science 3017, Bimal Roy, Willi Meier (Eds.), Springer-Verlag, 2004, pp. 245 - 259.

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 2^25 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.

Full paper:   post-script  and  pdf.

Presentation:  Power point.

Post-publication Note: None.

Contact:  Find the email here.  

Copyright Notice: This article is solely meant for non-commercial  (mainly academic) use as it is copyrighted by the respective publisher(s). Your comments/remarks/suggestions on the paper (of any kind from typographical error to technical ambiguity)  are kindly solicited and will be gratefully acknowledged.