Tabu Search Against Permutation Based Stream Ciphers

• Autorzy: Polak I. , Boryczka M.

Identyfikatory

DOI

10.24425/119361

• Języki publikacji: EN

Abstrakty

EN

Encryption is one of the most effective methods of securing data confidentiality, whether stored on hard drives or transferred (e.g. by e-mail or phone call). In this paper a new state recovery attack with tabu search is introduced. Based on research and theoretical approximation it is shown that the internal state can be recovered after checking 2⁵² internal states for RC4 and 2¹⁸⁰ for VMPC.

Słowa kluczowe

EN

tabu search; TS; cryptanalysis; RC4; VMPC; stream cipher; state recovery attack

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: International Journal of Electronics and Telecommunications
• Rocznik: 2018
• Tom: Vol. 64, No. 2
• Strony: 137--145
• Opis fizyczny: Bibliogr. 17 poz., rys., tab., wykr.

Twórcy

autor

Polak I.

• Institute of Computer Science, University of Silesia, Poland

autor

Boryczka M.

• Institute of Computer Science, University of Silesia, Poland

Bibliografia

• [1] C. E. Shannon, “A mathematical theory of communication,” The Bell System Technical Journal, vol. 27, no. 3, pp. 379-423, July 1948.
• [2] C. Shannon, Communication Theory and Secrecy Systems. Bell Telephone Laboratories, 1949. [Online]. Available: https://books.google.pl/books?id=8IL3HAAACAAJ
• [3] “RC4 Source Code,” Cypherpunks, September 1994, http://cypherpunks.venona.com/archive/1994/09/msg00304.html.
• [4] B. Harris, “Improved Arcfour Modes for the Secure Shell (SSH) Transport Layer Protocol,” January 2006. [Online]. Available: http://tools.ietf.org/html/rfc4345
• [5] B. Zoltak, “VMPC One-Way Function and Stream Cipher,” in Fast Software Encryption, ser. Lecture Notes in Computer Science, B. Roy and W. Meier, Eds. Springer Berlin Heidelberg, 2004, vol. 3017, pp. 210-225. [Online]. Available: http://dx.doi.org/10.1007/978-3-540-25937-4n\_4
• [6] B. Ferriman and C. Obimbo, “Solving for the RC4 stream cipher state register using a genetic algorithm,”International Journal of Advanced Computer Science and Applications, vol. 5, no. 5, pp. 218-223, May 2014.
• [7] M. Vanhoef and F. Piessens, “All Your Biases Belong to Us: Breaking RC4 in WPA-TKIP and TLS,” in Proceedings of the 24th USENIX Conference on Security Symposium, ser. SEC’15. Berkeley, CA, USA: USENIX Association, 2015, pp. 97-112. [Online]. Available: http://dl.acm.org/citation.cfm?id=2831143.2831150
• [8] A. Maximov, Two Linear Distinguishing Attacks on VMPC and RC4A and Weakness of RC4 Family of Stream Ciphers. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005, pp. 342-358. [Online]. Available: https://doi.org/10.1007/11502760\_23
• [9] S. Li, Y. Hu, Y. Zhao, and Y. Wang, “Improved cryptanalysis of the VMPC stream cipher,” Journal of Computational Information Systems, vol. 8, no. 2, pp. 831-838, 2012.
• [10] S. Sarkar, “Further non-randomness in RC4, RC4A and VMPC,” Cryptography and Communications, vol. 7, no. 3, pp. 317-330, 2015. [Online]. Available: https://doi.org/10.1007/s12095-014-0119-0
• [11] Y. Tsunoo, T. Saito, H. Kubo, M. Shigeri, T. Suzaki, and T. Kawabata, “The Most Efficient Distinguishing Attack on VMPC and RC4A.”
• [12] F. Glover, “Future Paths for Integer Programming and Links to Artificial Intelligence,” Comput. Oper. Res., vol. 13, no. 5, pp. 533-549, May 1986. [Online]. Available: http://dx.doi.org/10.1016/0305-0548(86)90048-1
• [13] F. Glover and M. Laguna, Tabu Search. Norwell, MA, USA: Kluwer Academic Publishers, 1997.
• [14] S. Maitra and G. Paul, Analysis of RC4 and Proposal of Additional Layers for Better Security Margin. Berlin, Heidelberg: Springer Berlin Heidelberg, 2008, pp. 27-39. [Online]. Available: http://dx.doi.org/10.1007/978-3-540-89754-5\_3
• [15] R. L. Rivest and J. C. N. Schuldt, “Spritz-a spongy RC4-like stream cipher and hash function,” August 19, 2014, presented at Charles River Crypto Day (2014-10-24).
• [16] S. Paul and B. Preneel, A New Weakness in the RC4 Keystream Generator and an Approach to Improve the Security of the Cipher. Berlin, Heidelberg: Springer Berlin Heidelberg, 2004, pp. 245-259. [Online]. Available: https://doi.org/10.1007/978-3-540-25937-4\_16
• [17] J. Strombergson and S. Josefsson, “Test Vectors for the Stream Cipher RC4,” May 2011. [Online]. Available: http://tools.ietf.org/html/rfc6229

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).