Abstract
A stream cipher has an unobservable internal state that is updated in every step and a keystream output (bit or word) is generated at every state transition. State recovery attack on stream cipher attempts to recover the hidden internal state by observing the keystream. RC4 is a very widely used commercial stream cipher that has a huge internal state. No known state recovery attack on RC4 is feasible in practice and the best so far has a complexity of 2241 (Maximov et al., CRYPTO 2008). In this paper, we take a different approach to the problem. RC4 has a secret index j of size one byte. We perform a combinatorial analysis of the complexity of RC4 state recovery under the assumption that the values of j are known for several rounds. This assumption of knowledge of j is reasonable under some attack models, such as fault analysis, cache analysis, side channel attacks etc. Our objective is not to devise an unconditional full state recovery attack on RC4, but to investigate how much information of j leaks how much information of the internal state. In the process, we reveal a nice combinatorial structure of RC4 evolution and establish certain interesting results related to the complexity of state recovery.
This paper is based on the M. Tech. (CS) dissertation work of the first author under the supervision of second author at Indian Statistical Institute, Kolkata.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Knudsen, L.R., 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)
Mantin, I.: Analysis of the stream cipher RC4. Master’s Thesis, The Weizmann Institute of Science, Israel (2001)
Maximov, A., Khovratovich, D.: New State Recovery Attack on RC4. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 297–316. Springer, Heidelberg (2008)
Mister, S., Tavares, S.E.: Cryptanalysis of RC4-like Ciphers. In: Tavares, S., Meijer, H. (eds.) SAC 1998. LNCS, vol. 1556, pp. 131–143. Springer, Heidelberg (1999)
Shiraishi, Y., Ohigashi, T., Morii, M.: An Improved Internal-state Reconstruction Method of a Stream Cipher RC4. In: Hamza, M.H. (ed.) Proceedings of Communication, Network, and Information Security, Track 440-088, New York, USA, December 10-12, pp. 440–488 (2003)
Tomasevic, V., Bojanic, S., Nieto-Taladriz, O.: Finding an internal state of RC4 stream cipher. Information Sciences 177, 1715–1727 (2007)
Golic, J., Morgari, G.: Iterative Probabilistic Reconstruction of RC4 Internal States. IACR Eprint Server, eprint.iacr.org, number 2008/348 August 8 (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Das, A., Maitra, S., Paul, G., Sarkar, S. (2011). Some Combinatorial Results towards State Recovery Attack on RC4. In: Jajodia, S., Mazumdar, C. (eds) Information Systems Security. ICISS 2011. Lecture Notes in Computer Science, vol 7093. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-25560-1_14
Download citation
DOI: https://doi.org/10.1007/978-3-642-25560-1_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-25559-5
Online ISBN: 978-3-642-25560-1
eBook Packages: Computer ScienceComputer Science (R0)