Abstract
A new bias is detected in the key scheduling algorithm of RC4 and a novel framework that advantageously combines this new bias with the existing ones is proposed. Using the new bias, a different algorithm is proposed to retrieve the RC4 key given the state table. The new method not only improves the success probability but also provides a more efficient way of calculation in comparison with the previous methods for any key size. The efficiency of the algorithm is demonstrated experimentally. If the key length is 40 bits, the secret key is retrieved with a 99% success rate in 0.007 seconds. The success probability for retrieving the 128 bit RC4 key is also increased significantly. 128-bit key can be retrieved with 3% success rate in 185 seconds and 7.45% success rate in 1572 seconds on a 2.67GHz Intel CPU.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Anonymous, RC4 Source Code, CypherPunks mailing list, September 9 (1994), http://cypherpunks.venona.com/date/1994/09/msg00304.html
Biham, E., Carmeli, Y.: Efficient Reconstruction of RC4 Keys from Internal States. In: Nyberg, K. (ed.) FSE 2008. LNCS, vol. 5086, pp. 270–288. Springer, Heidelberg (2008)
Finney, H.: An RC4 Cycle That Can‘t Happen, sci.crypt posting (September 1994)
Fluhrer, S.R., 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.R., McGrew, D.A.: Statistical Analysis of the Alleged RC4 Keystream Generator. In: Schneier, B. (ed.) FSE 2000. LNCS, vol. 1978, pp. 19–30. Springer, Heidelberg (2001)
Golic, J.D.: 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.L., Wallach, D.S.: A Related-Key Cryptanalysis of RC4, Technical Report-00-358, Department of Computer Science, Rice University (October 2000)
Khazaei, S., Meier, W.: On Reconstruction of RC4 Keys from Internal States
Klein, A.: Attacks on the RC4 Stream Cipher, February 27 (2006), http://cage.ugent.be/klein/RC4
Knudsen, L.R., Meier, W., Prenel, 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)
Maitra, S., Paul, G.: New Form of Permutation Bias and Secret Key Leakage in Keystream Bytes of RC4. In: Nyberg, K. (ed.) FSE 2008. LNCS, vol. 5086, pp. 253–269. Springer, Heidelberg (2008)
Maitra, S., Paul, G.: New Form of Permutation Bias and Secret Key Leakage in Key Stream Bytes of RC4, http://eprint.iacr.org/2007/261.pdf
Maitra, S.: Personal Communication
Mantin, I.: Analysis of the Stream Cipher RC4, M. Sc. Thesis, The Weizmann Institute of Science, Israel (2001), http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Mantin1.zip
Mantin, I.: Predicting and Distinguishing Attacks on RC4 Keystream Generator. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 491–506. Springer, Heidelberg (2005)
Mantin, I., Shamir, A.: A Practical Attack on Broadcast RC4. In: Matsui, M. (ed.) FSE 2001. LNCS, vol. 2355, pp. 152–164. Springer, Heidelberg (2002)
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)
Mironov, I.: (Not So) Random Shuffles of RC4. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 304–319. Springer, Heidelberg (2002)
Paul, G., Maitra, S.: RC4 State Information at Any Stage Reveals the Secret Key. In: Proceedings of SAC 2007 (2007), http://eprint.iacr.org/2007/208.pdf
Pudovkina, M.: The Number of Initial States of the RC4 Cipher with the Same Cycle Structure, Cryptology ePrint Archive, 2002-171, IACR 2002 (2002)
Roos, A.: A Class of Weak Keys in the RC4 Stream Cipher, Two posts in sci.crypt (1995), http://marcel.wanda.ch/Archive/WeakKeys
Tews, E., Weinmann, R.P., Pyshkin, A.: Breaking 104 Bit WEP in Less than 60 Seconds (2007), http://eprint.iacr.org/2007/120.pdf
Vaudenay, S., Vuagnoux, M.: Passive-Only Key Recovery Attacks on RC4. In: Adams, C., Miri, A., Wiener, M. (eds.) SAC 2007. LNCS, vol. 4876. Springer, Heidelberg (2007)
Wagner, D.: Weak Keys in RC4, sci.crypt posting (September 1995)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Akgün, M., Kavak, P., Demirci, H. (2008). New Results on the Key Scheduling Algorithm of RC4. In: Chowdhury, D.R., Rijmen, V., Das, A. (eds) Progress in Cryptology - INDOCRYPT 2008. INDOCRYPT 2008. Lecture Notes in Computer Science, vol 5365. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-89754-5_4
Download citation
DOI: https://doi.org/10.1007/978-3-540-89754-5_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-89753-8
Online ISBN: 978-3-540-89754-5
eBook Packages: Computer ScienceComputer Science (R0)