Abstract
In Usenix Security symposium 2015, Vanhoef and Piessens published a number of results regarding weaknesses of the RC4 stream cipher when used in the TLS protocol. The authors unearthed a number of new biases in the keystream bytes that helped to reliably recover the plaintext using a limited number of TLS sessions. Most of these biases were based on the joint distribution successive/non-successive keystream bytes. Moreover, the biases were reported after experimental observations and no theoretical explanations were proffered. In this paper, we provide detailed proofs of most of these biases, and provide certain generalizations of the results reported in the above paper. We also unearth new biases based on the joint distributions of three consecutive bytes.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
AlFardan, N.J., Bernstein, D.J., Paterson, K.G., Poettering, B., Schuldt, J.C.N.: On the security of RC4 in TLS. In: USENIX Security Symposium 2013, pp. 305–320 (2013)
Banik, S., Sarkar, S., Kacker, R.: Security analysis of the RC4+ stream cipher. In: Paul, G., Vaudenay, S. (eds.) INDOCRYPT 2013. LNCS, vol. 8250, pp. 297–307. Springer, Heidelberg (2013). doi:10.1007/978-3-319-03515-4_20
Banik, S., Jha, S.: Some security results of the RC4+ stream cipher. Secur. Commun. Netw. 8(18), 4061–4072 (2015)
Banik, S., Jha, S.: How not to combine RC4 states. In: Chakraborty, R.S., Schwabe, P., Solworth, J. (eds.) SPACE 2015. LNCS, vol. 9354, pp. 95–112. Springer, Heidelberg (2015). doi:10.1007/978-3-319-24126-5_6
Banik, S., Isobe, T.: Cryptanalysis of the full Spritz stream cipher. In: Peyrin, T. (ed.) FSE 2016. LNCS, vol. 9783, pp. 63–77. Springer, Heidelberg (2016). doi:10.1007/978-3-662-52993-5_4
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). doi:10.1007/11599548_14
Isobe, T., Ohigashi, T., Watanabe, Y., Morii, M.: Full plaintext recovery attack on broadcast RC4. In: Moriai, S. (ed.) FSE 2013. LNCS, vol. 8424, pp. 179–202. Springer, Heidelberg (2014). doi:10.1007/978-3-662-43933-3_10
Lv, J., Zhang, B., Lin, D.: Distinguishing attacks on RC4 and a new improvement of the cipher. Cryptology ePrint Archive: Report 2013/176
Maitra, S.: Four Lines of Design to Forty Papers of Analysis: The RC4 Stream Cipher. http://www.isical.ac.in/~indocrypt/indo12.pdf
Maitra, S., Paul, G.: Analysis of RC4 and proposal of additional layers for better security margin. In: Chowdhury, D.R., Rijmen, V., Das, A. (eds.) INDOCRYPT 2008. LNCS, vol. 5365, pp. 27–39. Springer, Heidelberg (2008). doi:10.1007/978-3-540-89754-5_3
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). doi:10.1007/3-540-45473-X_13
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). doi:10.1007/978-3-540-85174-5_17
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). doi:10.1007/11502760_23
Papov, A.: Prohibiting RC4 cipher suites. In: Internet Engineering Task Force (IETF). https://tools.ietf.org/html/rfc7465
Paul, G., Maitra, S., Chattopadhyay, A.: Quad-RC4: merging four RC4 states towards a 32-bit stream cipher. IACR Cryptology eprint Archive 2013:572 (2013)
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). doi:10.1007/978-3-540-25937-4_16
Rivest, R.L., Schuldt, J.C.N.: Spritz—a spongy RC4-like stream cipher and hash function. https://people.csail.mit.edu/rivest/pubs/RS14.pdf
Sarkar, S.: Further non-randomness in RC4, RC4A and VMPC. Crypt. Commun. 7(3), 317–330 (2015)
Tsunoo, Y., Saito, T., Kubo, H., Shigeri, M., Suzaki, T., Kawabata, T.: The most efficient distinguishing attack on VMPC and RC4A. In: SKEW 2005. http://www.ecrypt.eu.org/stream/papers.html
Vanhoef, M., Piessens, F.: All your biases belong to us: breaking RC4 in WPA-TKIP and TLS. In: 24th USENIX Security Symposium 2015, pp. 97–112 (2015)
Vanhoef, M., Piessens, F.: Practical verification of WPA-TKIP vulnerabilities. In: ASIACCS 2013, Proceedings of the 8th ACM SIGSAC Symposium on Information, Computer and Communications Security, pp. 427–436 (2013)
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). doi:10.1007/978-3-540-25937-4_14
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing AG
About this paper
Cite this paper
Jha, S., Banik, S., Isobe, T., Ohigashi, T. (2016). Some Proofs of Joint Distributions of Keystream Biases in RC4. In: Dunkelman, O., Sanadhya, S. (eds) Progress in Cryptology – INDOCRYPT 2016. INDOCRYPT 2016. Lecture Notes in Computer Science(), vol 10095. Springer, Cham. https://doi.org/10.1007/978-3-319-49890-4_17
Download citation
DOI: https://doi.org/10.1007/978-3-319-49890-4_17
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-49889-8
Online ISBN: 978-3-319-49890-4
eBook Packages: Computer ScienceComputer Science (R0)