A Survey on RC4 Stream Cipher

Full Text (PDF, 562KB), PP.37-45

Views: 0 Downloads: 0

Author(s)

Poonam Jindal 1,* Brahmjit Singh 1

1. National Institute of Technology, Kurukshetra, 136119, Haryana

* Corresponding author.

DOI: https://doi.org/10.5815/ijcnis.2015.07.05

Received: 6 Oct. 2014 / Revised: 25 Feb. 2015 / Accepted: 2 Apr. 2015 / Published: 8 Jun. 2015

Index Terms

Security attacks, Symmetric key encryption, Stream cipher, RC4, Weaknesses of RC4

Abstract

RC4 is one of the most widely used stream cipher due to its simplicity, speed and efficiency. In this paper we have presented a chronological survey of RC4 stream cipher demonstrating its weaknesses followed by the various RC4 enhancements from the literature. From the recently observed cryptanalytic attempts on RC4 it is established that innovative research efforts are required to develop secure RC4 algorithm, which can remove the weaknesses of RC4, such as biased bytes, key collisions, and key recovery attacks specifically on WEP and WPA. These flaws in RC4 are offering open challenge for developers. Hence our chronological survey corroborates the fact that even though researchers are working on RC4 stream cipher since last two decades, it still offers a plethora of research issues related to statistical weaknesses in either state or keystream.

Cite This Paper

Poonam Jindal, Brahmjit Singh,"A Survey on RC4 Stream Cipher", International Journal of Computer Network and Information Security(IJCNIS), vol.7, no.7, pp.37-45, 2015. DOI:10.5815/ijcnis.2015.07.05

Reference

[1]Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone. Hand- book of Applied Cryptography. CRC Press, August 2011 edition, 1996. Fifth Printing.
[2]Douglas R. Stinson. Cryptography: Theory and Practice. CRC Press, third November 2005) edition, 1995.
[3]Alex Biryukov, Adi Shamir, and David Wagner. Real time cryptanalysis of A5/1 on a PC. In Bruce Schneier, editor, FSE, volume 1978 of Lecture Notes in Computer Science, pages 1–18. Springer, 2000.
[4]Bluetooth T M. Bluetooth specification, v4.0, June 2010. E0 encryption algorithm described in volume 2, pages 1072–1081. Available online at http://www.bluetooth.org.
[5]Marc Briceno, Ian Goldberg, and David Wagner. A pedagogical implementation of the GSM A5/1 and A5/2 “voice privacy” encryption algorithms. Available online at http://www.scard.org/gsm/a51.html, 1998.
[6]3rd Generation Partnership Project. Specification of the 3GPP confidentiality and integrity algorithms UEA2 & UIA2. ETSI/SAGE Specification Document 2: SNOW 3G Specification, v1.1, September 6, 2006.
[7]ECRYPT Stream Cipher Project eSTREAM. The current eSTREAM portfolio. Available online at http://www.ecrypt.eu.org/stream/ index.html.
[8]ECRYPT Stream Cipher Project eSTREAM. Software performance results from the eSTREAM project. Available online at http://www. ecrypt.eu.org/stream/perf/#results.
[9]Ronald L. Rivest. RSA security response to weaknesses in key scheduling algorithm of RC4. Technical note, RSA Data Security, Inc., 2001.
[10]Andrew Roos. A class of weak keys in the RC4 stream cipher. Two posts in sci.crypt, message-id 43u1eh$1j3@hermes.is.co.za 1995.
[11]Goutam Paul, Siddheshwar Rathi, and Subhamoy Maitra. On non-negligible bias of the first output byte of RC4 towards the first three bytes of the secret key. Des. Codes Cryptography, 49(1-3):123–134, 2008. Initial version in proceedings of WCC 2007.
[12]David A. Wagner. My RC4 weak keys. Post in sci.crypt, messageid 447o1l$cbj@cnn.Princeton.EDU, 1995. Available online at http://www.cs.berkeley.edu/~daw/my-posts/my-rc4-weak-keys.
[13]Alexander L. Grosul and Dan S. Wallach. A related-key cryptanalysis of RC4. Technical Report TR-00-358, Department of Computer Science, Rice University, 2000.
[14]Eli Biham and Orr Dunkelman. Differential cryptanalysis in stream ciphers. IACR Cryptology ePrint Archive, 2007:218, 2007.
[15]Mitsuru Matsui. Key collisions of the RC4 stream cipher. In Orr Dunkelman, editor, FSE, volume 5665 of Lecture Notes in Computer Science, pages 38–50. Springer, 2009.
[16]Jiageng Chen and Atsuko Miyaji. How to find short RC4 colliding key pairs. In Xuejia Lai, Jianying Zhou, and Hui Li, editors, ISC, volume 7001 of Lecture Notes in Computer Science, pages 32–46. Springer, 2011.
[17]Subhamoy Maitra, Goutam Paul, Santanu Sarkar, Michael Lehmann, and Willi Meier. New results on generalization of Roostype biases and related keystreams of RC4. In Amr Youssef, Abderrahmane Nitaj, and Aboul Ella
Hassanien, editors, AFRICACRYPT, volume 7918 of Lecture Notes in Computer Science, pages 222–239. Springer, 2013.
[18]Goutam Paul and Subhamoy Maitra. Permutation after RC4 key scheduling reveals the secret key. In Carlisle M. Adams, Ali Miri, and BIBLIOGRAPHY Michael J. Wiener, editors, Selected Areas in Cryptography, volume 4876 of Lecture Notes in Computer Science, pages 360–377. Springer, 2007.
[19]Eli Biham and Yaniv Carmeli. Efficient reconstruction of RC4 keys from internal states. In Kaisa Nyberg, editor, FSE, volume 5086 of Lecture Notes in Computer Science, pages 270–288. Springer, 2008.
[20]Mete Akgün, Pinar Kavak, and Hüseyin Demirci. New results on the key scheduling algorithm of RC4. In Dipanwita Roy Chowdhury, Vincent Rijmen, and Abhijit Das, editors, INDOCRYPT, volume 5365 of Lecture Notes in Computer Science, pages 40–52. Springer, 2008.
[21]Shahram Khazaei and Willi Meier. On reconstruction of RC4 keys from internal states. In Jacques Calmet, Willi Geiselmann, and J?rn Müller-Quade, editors, MMICS, volume 5393 of Lecture Notes in Computer Science, pages 179–189. Springer, 2008.
[22]Riddhipratim Basu, Subhamoy Maitra, Goutam Paul, and Tanmoy Talukdar. On some sequences of the secret pseudo-random index j in RC4 key scheduling. In Maria Bras-Amorós and Tom H?holdt, editors, AAECC, volume 5527 of Lecture Notes in Computer Science, pages 137–148. Springer, 2009.
[23]Scott R. Fluhrer, Itsik Mantin, and Adi Shamir. Weaknesses in the key scheduling algorithm of RC4. In Serge Vaudenay and Amr M. Youssef, editors, Selected Areas in Cryptography, volume 2259 of Lecture Notes in Computer Science, pages 1–24. Springer, 2001.
[24]Korek. Need security pointers. Published online at http://www.netstumbler.org/showthread.php?postid=89036#pos%t89036, 2004.
[25]Korek. Next generation of WEP attacks? Published online at http://www.netstumbler.org/showpost.php?p=93942&postcount=%35, 2004.
[26]Itsik Mantin. A practical attack on the fixed RC4 in the WEP mode. In Bimal K. Roy, editor, ASIACRYPT, volume 3788 of Lecture Notes in Computer Science, pages 395–411. Springer, 2005.
[27]Andreas Klein. Attacks on the RC4 stream cipher. Des. Codes Cryptography, 48(3):269–286, 2008. Published online in 2006, and accepted in WCC 2007 workshop.
[28]Erik Tews, Ralf-Philipp Weinmann, and Andrei Pyshkin. Breaking 104 bit WEP in less than 60 seconds. In Sehun Kim, Moti Yung, and Hyung- Woo Lee, editors, WISA, volume 4867 of Lecture Notes in Computer Science, pages 188–202. Springer, 2007.
[29]Serge Vaudenay and Martin Vuagnoux. Passive-only key recovery attacks on RC4. In Carlisle M. Adams, Ali Miri, and Michael J. Wiener, editors, Selected Areas in Cryptography, volume 4876 of Lecture Notes in Computer Science, pages 344– 359. Springer, 2007.
[30]Erik Tews and Martin Beck. Practical attacks against WEP and WPA. In David A. Basin, Srdjan Capkun, and Wenke Lee, editors, WISEC, pages 79–86. ACM, 2009.
[31]Pouyan Sepehrdad. Statistical and Algebraic Cryptanalysis of Lightweight and Ultra-Lightweight Symmetric Primitives. PhD thesis No. 5415, école Polytechnique Fédérale de Lausanne (EPFL), 2012. Available online at http://lasecwww.epfl.ch/~sepehrdad/Pouyan_Sepehrdad_PhD_Thesis.pdf.
[32]Pouyan Sepehrdad, Serge Vaudenay, and Martin Vuagnoux. Discovery and exploitation of new biases in RC4. In Alex Biryukov, Guang Gong, and Douglas R. Stinson, editors, Selected Areas in Cryptography, volume 6544 of Lecture Notes in Computer Science, pages 74–91. Springer, 2010.
[33]Pouyan Sepehrdad, Serge Vaudenay, and Martin Vuagnoux. Statistical attack on RC4 - distinguishing WPA. In Kenneth G. Paterson, editor, EUROCRYPT, volume 6632 of Lecture Notes in Computer Science, pages 343–363. Springer, 2011.
[34]Pouyan Sepehrdad, Petr Susil, Serge Vaudenay, and Martin Vuagnoux. Smashing WEP in a passive attack. In Fast Software Encryption (FSE), 2013.
[35]Lars R. Knudsen, Willi Meier, Bart Preneel, Vincent Rijmen, and Sven Verdoolaege. Analysis methods for (alleged) RC4. In Kazuo Ohta and Dingyi Pei, editors, ASIACRYPT, volume 1514 of Lecture Notes in Computer Science, pages 327–341. Springer, 1998.
[36]Serge Mister and Stafford E. Tavares. Cryptanalysis of RC4-like ciphers. In Stafford E. Tavares and Henk Meijer, editors, Selected Areas in Cryptography, volume 1556 of Lecture Notes in Computer Science, pages 131–143. Springer, 1998.
[37]Jovan Dj. Golic. Iterative probabilistic cryptanalysis of RC4 keystream generator. In Ed Dawson, Andrew Clark, and Colin Boyd, editors, ACISP, volume 1841 of Lecture Notes in Computer Science, pages 220– 233. Springer, 2000.
[38]Yoshiaki Shiraishi, Toshihiro Ohigashi, and Masakatu Morii. An improved internal-state reconstruction method of a stream cipher RC4. In M.H. Hamza, editor, Communication, Network, and Information Security, Track 440–088, New York, USA, December 2003.
[39]Violeta Tomasevic, Slobodan Bojanic, and Octavio Nieto-Taladriz. Finding an internal state of RC4 stream cipher. Inf. Sci., 177(7):1715–1727, 2007.
[40]Alexander Maximov and Dmitry Khovratovich. New state recovery attack on RC4. In DavidWagner, editor, CRYPTO, volume 5157 of Lecture Notes in Computer Science, pages 297–316. Springer, 2008.
[41]Jovan Dj. Golic and Guglielmo Morgari. Iterative probabilistic reconstruction of RC4 internal states. IACR Cryptology ePrint Archive, 2008:348, 2008.
[42]Sourav Sen Gupta, Subhamoy Maitra, Goutam Paul, and Santanu Sarkar. Proof of empirical RC4 biases and new key correlations. In Ali Miri and Serge Vaudenay, editors, Selected Areas in Cryptography, volume 7118 of Lecture Notes in Computer Science, pages 151–168. Springer, 2011.
[43]Sourav Sen Gupta, Subhamoy Maitra, Goutam Paul, and Santanu Sarkar. "(Non-) Random Sequences from (Non-) Random Permutations—Analysis of RC4 Stream Cipher." Journal of Cryptology 27, no. 1 (2014): 67-108.
[44]Takanori Isobe, Toshihiro Ohigashi, Yuhei Watanabe, and Masakatu Morii. "Full plaintext recovery attack on broadcast RC4." In Proc. the 20th International Workshop on Fast Software Encryption (FSE 2013), 2013.
[45]Santanu Sarkar, Sourav Sen Gupta, Goutam Paul, and Subhamoy Maitra. Proving TLS-attack related open biases of RC4. IACR Cryptology ePrint Archive, 2013:502, 2013.
[46]Robert J. Jenkins Jr. ISAAC and RC4. Published on the Internet at http://burtleburtle.net/bob/rand/isaac.html, 1996.
[47]Itsik Mantin and Adi Shamir. A practical attack on broadcast RC4. In Mitsuru Matsui, editor, FSE, volume 2355 of Lecture Notes in Computer Science, pages 152–164. Springer, 2001.
[48]Itsik Mantin. Analysis of the stream cipher RC4. Master’s thesis, The Weizmann Institute of Science, Israel, 2001. Available online at http: //www.wisdom.weizmann.ac.il/~itsik/RC4/RC4.html.
[49]Goutam Paul, Subhamoy Maitra, and Rohit Srivastava. On non-randomness of the permutation after RC4 key scheduling. In Serdar Boztas and Hsiao feng Lu, editors, AAECC, volume 4851 of Lecture Notes in Computer Science, pages 100–109. Springer, 2007.
[50]Santanu Sarkar. Further non-randomness in RC4, RC4A and VMPC. In International Workshop on Coding and Cryptography (WCC), 2013.
[51]Subhamoy Maitra, Goutam Paul, and Sourav Sen Gupta. Attack on broadcast RC4 revisited. In Antoine Joux, editor, FSE, volume 6733 of Lecture Notes in Computer Science, pages 199–217. Springer, 2011.
[52]Nadhem AlFardan, Dan Bernstein, Kenneth G. Paterson, Bertram Poettering, and Jacob C.N. Schuldt. On the security of RC4 in TLS. In USENIX Security Symposium, 2013. Presented at FSE 2013 as an invited talk [14] by Dan Bernstein. Full version of the research paper and relevant results are available online at http://www.isg.rhul.ac.uk/tls/.
[53]Jovan Dj. Golic. Linear statistical weakness of alleged RC4 keystream generator. In Walter Fumy, editor, EUROCRYPT, volume 1233 of Lecture Notes in Computer Science, pages 226–238. Springer, 1997.
[54]Scott R. Fluhrer and David A. McGrew. Statistical analysis of the alleged RC4 keystream generator. In Bruce Schneier, editor, FSE, volume 1978 of Lecture Notes in Computer Science, pages 19–30. Springer, 2000.
[55]Itsik Mantin. Predicting and distinguishing attacks on RC4 keystream generator. In Ronald Cramer, editor, EUROCRYPT, volume 3494 of Lecture Notes in Computer Science, pages 491–506. Springer, 2005.
[56]Riddhipratim Basu, Shirshendu Ganguly, Subhamoy Maitra, and Goutam Paul. A complete characterization of the evolution of RC4 pseudo random generation algorithm. J. Mathematical Cryptology, 2(3):257–289, 2008.
[57]Adam Stubblefield, John Ioannidis, and Aviel D. Rubin. Using the Fluhrer, Mantin, and Shamir attack to break WEP. In NDSS. The Internet Society, 2002.
[58]Gong, Guang, Kishan Chand Gupta, Martin Hell, and Yassir Nawaz. "Towards a general RC4-like keystream generator." In Information Security and Cryptology, pp. 162-174. Springer Berlin Heidelberg, 2005.
[59]Orumiehchiha, Mohammad Ali, Josef Pieprzyk, Elham Shakour, and Ron Steinfeld. "Cryptanalysis of RC4 (n, m) Stream Cipher." In Proceedings of the 6th International Conference on Security of Information and Networks, pp. 165-172. ACM, 2013.
[60]Maitra, S., & Paul, G. Analysis of RC4 and proposal of additional layers for better security margin. In Progress in CryptologyINDOCRYPT 2008 (pp. 27-39). Springer Berlin Heidelberg.
[61]Banik, Subhadeep, Santanu Sarkar, and Raghu Kacker. "Security Analysis of the RC4+ Stream Cipher." In Progress in Cryptology–INDOCRYPT 2013, pp. 297-307. Springer International Publishing, 2013.
[62]Xie, J., & Pan, X. An improved RC4 stream cipher. In Computer Application and System Modeling (ICCASM), 2010 International Conference on (Vol. 7, pp. V7-156). IEEE.
[63]Hammood, M. M., Yoshigoe, K., & Sagheer, A. M. (2013). RC4-2S: RC4 Stream Cipher with Two State Tables. In Information Technology Convergence (pp. 13-20). Springer Netherlands.
[64]Paul, G., Maitra, S., & Chattopadhyay, A. Quad-RC4: Merging Four RC4 States towards a 32-bit Stream Cipher. IACR Cryptology ePrint Archive, 2013, 572.
[65]Kherad, F. J., Naji, H. R., Malakooti, M. V., & Haghighat, P. A new symmetric cryptography algorithm to secure e-commerce transactions. In Financial Theory and Engineering (ICFTE), 2010 International Conference on (pp. 234-237). IEEE.
[66]Weerasinghe, T. D. B. An Effective RC4 Stream Cipher. IACR Cryptology ePrint Archive, 2014, 171
[67]Lv, J., Zhang, B., & Lin, D. Distinguishing Attacks on RC4 and A New Improvement of the Cipher. IACR Cryptology ePrint Archive, 2013, 176.
[68]Khine, L. L. A New Variant of RC4 Stream Cipher. World Academy of Science, Engineering and Technology, 50.