The RC4 stream cipher is the most widely used software based stream cipher. It is based on a secret internal state of N=256 bytes and two pointers. This paper proposes an efficient algorithm to compute a special set of RC4 states named non-fortuitous predictive states. These special states increase the probability to guess part of the internal state in a known plaintext attack and present a cryptanalytic weakness of RC4. The problem of designing a practical algorithm to compute them has been open since it was posed by Mantin and Shamir in 2001. We also formally prove a slightly corrected version of the conjecture by Mantin and Shamir of 2001 that only a known elements along with the two pointers at any RC4 round cannot predict more than a outputs in the next N rounds.
This work was partially supported by the Concerted Research Action GOA-MEFISTO-666 of the Flemish government.
This is a preview of subscription content, log in via an institution to check access.
PreviewUnable to display preview. Download preview PDF.
Similar content being viewed by others ReferencesMantin, I., Shamir, A.: A Practical Attack on Broadcast RC4. In: Matsui, M. (ed.) FSE 2001. LNCS, vol. 2355, pp. 152–164. Springer, Heidelberg (2002)
Fluhrer, S., McGrew, D.: Statiscal Analysis of the Alleged RC4 Keystream Generator. In: Schneier, B. (ed.) FSE 2000. LNCS, vol. 1978, pp. 19–30. Springer, Heidelberg (2001)
Finney, H.: An RC4 cycle that can’t happen. Post in sci.crypt (September 1994)
Mironov, I.: Not (So) Random Shuffle of RC4. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 304–319. Springer, Heidelberg (2002)
Jenkins, R.: Isaac and RC4, Published on the Internet at http://burtleburtle.net/bob/rand/isaac.html
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)
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)
Grosul, A., Wallach, D.: A related key cryptanalysis of RC4. Department of Computer Science, Rice University, Technical Report TR-00-358 (June 2000)
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)
Roos, A.: Class of weak keys in the RC4 stream cipher. Post in sci.crypt (September 1995)
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)
Stubblefield, A., Ionnidis, J., Rubin, A.: Using the Fluhrer, Mantin and Shamir attack to break WEP. In: NDSS 2002 (2002)
Dept. ESAT/COSIC, Katholieke Universiteit Leuven, Kasteelpark Arenberg 10, B–3001, Leuven-Heverlee, Belgium
Souradyuti Paul & Bart Preneel
Dept. of Electrical and Information Technology, Lund University, P.O. Box 118, 221 00, Lund, Sweden
Thomas Johansson
Indian Statistical Institute, 203 B T Road, 700 108, Kolkata, India
Subhamoy Maitra
© 2003 Springer-Verlag Berlin Heidelberg
About this paper Cite this paperPaul, S., Preneel, B. (2003). Analysis of Non-fortuitous Predictive States of the RC4 Keystream Generator. In: Johansson, T., Maitra, S. (eds) Progress in Cryptology - INDOCRYPT 2003. INDOCRYPT 2003. Lecture Notes in Computer Science, vol 2904. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24582-7_4
Download citationDOI: https://doi.org/10.1007/978-3-540-24582-7_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20609-5
Online ISBN: 978-3-540-24582-7
eBook Packages: Springer Book Archive
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4