Skip to main content
SpringerLink
Log in

Analysis of RC4 and Proposal of Additional Layers for Better Security Margin

  • Conference paper
Progress in Cryptology - INDOCRYPT 2008 (INDOCRYPT 2008)

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 5365))

Included in the following conference series:

Abstract

In this paper, the RC4 Key Scheduling Algorithm (KSA) is theoretically studied to reveal non-uniformity in the expected number of times each value of the permutation is touched by the indices i, j. Based on our analysis and the results available in the literature regarding the existing weaknesses of RC4, few additional layers over the RC4 KSA and RC4 Pseudo-Random Generation Algorithm (PRGA) are proposed. Analysis of the modified cipher (we call it RC4 + ) shows that this new strategy avoids existing weaknesses of RC4.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. Akgun, M., Kavak, P., Demirci, H.: New Results on the Key Scheduling Algorithm of RC4. In: Indocrypt 2008 (2008)

    Google Scholar 

  2. 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)

    Chapter  Google Scholar 

  3. eSTREAM, the ECRYPT Stream Cipher Project (last accessed on July 18, 2008), http://www.ecrypt.eu.org/stream

  4. 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)

    Chapter  Google Scholar 

  5. Golic, J.: Linear statistical weakness of alleged RC4 keystream generator. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 226–238. Springer, Heidelberg (1997)

    Chapter  Google Scholar 

  6. Gong, G., Gupta, K.C., Hell, M., Nawaz, Y.: Towards a General RC4-Like Keystream Generator. In: Feng, D., Lin, D., Yung, M. (eds.) CISC 2005. LNCS, vol. 3822, pp. 162–174. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  7. Hong, J., Sarkar, P.: New Applications of Time Memory Data Tradeoffs. In: Roy, B. (ed.) ASIACRYPT 2005. LNCS, vol. 3788, pp. 353–372. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  8. Jenkins, R.J.: ISAAC and RC4 (1996) (last accessed on July 18, 2008), http://burtleburtle.net/bob/rand/isaac.html

  9. Klein, A.: Attacks on the RC4 stream cipher. Designs, Codes and Cryptography 48(3), 269–286 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  10. Knudsen, L.R., Meier, W., Preneel, B., Rijmen, V., Verdoolaege, S.: Analysis Methods for (Alleged) RCA. In: Ohta, K., Pei, D. (eds.) ASIACRYPT 1998. LNCS, vol. 1514, pp. 327–341. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

  11. LAN/MAN Standard Committee. Wireless LAN medium access control (MAC) and physical layer (PHY) specifications, 1999 edition. IEEE standard 802.11 (1999)

    Google Scholar 

  12. Maitra, S., Paul, G.: Analysis of RC4 and Proposal of Additional Layers for Better Security Margin (Full Version). IACR Eprint Server, eprint.iacr.org, number 2008/396, September 19 (2008)

    Google Scholar 

  13. 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)

    Chapter  Google Scholar 

  14. 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)

    Chapter  Google Scholar 

  15. Mantin, I.: A Practical Attack on the Fixed RC4 in the WEP Mode. In: Roy, B. (ed.) ASIACRYPT 2005. LNCS, vol. 3788, pp. 395–411. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  16. 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)

    Chapter  Google Scholar 

  17. Mantin, I.: Analysis of the stream cipher RC4. Master’s Thesis, The Weizmann Institute of Science, Israel (2001)

    Google Scholar 

  18. Maximov, A.: Two Linear Distinguishing Attacks on VMPC and RC4A and Weakness of RC4 Family of Stream Ciphers. In: Gilbert, H., Handschuh, H. (eds.) FSE 2005. LNCS, vol. 3557, pp. 342–358. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  19. 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)

    Chapter  Google Scholar 

  20. Mironov, I. (Not So) Random Shuffles of RC4. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 304–319. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  21. New European Schemes for Signatures, Integrity, and Encryption (last accessed on September 19, 2008), https://www.cosic.esat.kuleuven.be/nessie

  22. Paul, G., Rathi, S., Maitra, S.: On Non-negligible Bias of the First Output Byte of RC4 towards the First Three Bytes of the Secret Key. In: Proceedings of the International Workshop on Coding and Cryptography (WCC) 2007, pp. 285–294 (2007); Extended version available at Designs, Codes and Cryptography 49, 1-3 (December 2008)

    Google Scholar 

  23. Paul, G., Maitra, S.: Permutation after RC4 Key Scheduling Reveals the Secret Key. In: Adams, C., Miri, A., Wiener, M. (eds.) SAC 2007. LNCS, vol. 4876, pp. 360–377. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  24. Paul, G., Maitra, S.: RC4 State Information at Any Stage Reveals the Secret Key. IACR Eprint Server, eprint.iacr.org, number 2007/208 (June 1, 2007); This is an extended version of [23]

    Google Scholar 

  25. Paul, G., Maitra, S., Srivastava, R.: On Non-randomness of the Permutation After RC4 Key Scheduling. In: Boztaş, S., Lu, H.-F(F.) (eds.) AAECC 2007. LNCS, vol. 4851, pp. 100–109. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  26. 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)

    Chapter  Google Scholar 

  27. Paul, S., Preneel, B.: A New Weakness in the RC4 Keystream Generator and an Approach to Improve the Security of the Cipher. In: Roy, B., Meier, W. (eds.) FSE 2004. LNCS, vol. 3017, pp. 245–259. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  28. A. Roos. A class of weak keys in the RC4 stream cipher. Two posts in sci.crypt, message-id 43u1eh$1j3@hermes.is.co.za and 44ebge$llf@hermes.is.co.za (1995) (last accessed on July 18, 2008), http://groups.google.com/group/sci.crypt.research/msg/078aa9249d76eacc?dmode=source

  29. RSA Lab Report. RSA Security Response to Weaknesses in Key Scheduling Algorithm of RC4 (last accessed on July 18, 2008), http://www.rsa.com/rsalabs/node.asp?id=2009

  30. Tews, E., Weinmann, R.P., Pyshkin, A.: Breaking 104 bit WEP in less than 60 seconds. IACR Eprint Server, eprint.iacr.org, number 2007/120 (April 1, 2007) (last accessed on July 18, 2008)

    Google Scholar 

  31. Tomasevic, V., Bojanic, S., Nieto-Taladriz, O.: Finding an internal state of RC4 stream cipher. Information Sciences 177, 1715–1727 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  32. Tsunoo, Y., Saito, T., Kubo, H., Shigeri, M., Suzaki, T., Kawabata, T.: The Most Efficient Distinguishing Attack on VMPC and RC4A. In: SKEW 2005 (last accessed on July 18, 2008), http://www.ecrypt.eu.org/stream/papers.html

  33. Tsunoo, Y., Saito, T., Kubo, H., Suzaki, T.: A Distinguishing Attack on a Fast Software-Implemented RC4-Like Stream Cipher. IEEE Transactions on Information Theory 53(9), 3250–3255 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  34. Vaudenay, S., Vuagnoux, M.: Passive-Only Key Recovery Attacks on RC4. In: Adams, C., Miri, A., Wiener, M. (eds.) SAC 2007. LNCS, vol. 4876, pp. 344–359. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  35. Zoltak, B.: VMPC One-Way Function and Stream Cipher. In: Roy, B., Meier, W. (eds.) FSE 2004. LNCS, vol. 3017, pp. 210–225. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Indian Statistical Institute, Applied Statistics Unit, Kolkata, 700 108, India

    Subhamoy Maitra

  2. Department of Computer Science and Engineering, Jadavpur University, Kolkata, 700 032, India

    Goutam Paul

Authors
  1. Subhamoy Maitra
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Goutam Paul
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Dept. of Computer Science and Engineering, Indian Institute of Technology, 721 302, Kharagpur, India

    Dipanwita Roy Chowdhury

  2. K.U. Leuven, ESAT/COSIC Kasteelpark, Arenberg 10, B-3001, Leuven-Heverlee, Belgium

    Vincent Rijmen

  3. Department of Computer Science and Engineering, Indian Institute of Technology, 721 302, Kharagpur, India

    Abhijit Das

Rights and permissions

Reprints and permissions

Copyright information

© 2008 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Maitra, S., Paul, G. (2008). Analysis of RC4 and Proposal of Additional Layers for Better Security Margin. 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_3

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-89754-5_3

  • 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)

Publish with us

Policies and ethics

Search

Navigation