Tabu search against permutation based stream ciphers

Iwona Polak


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^52 internal states for RC4 and 2^180 for VMPC.

Full Text:



C. E. Shannon, “A mathematical theory of communication,” The Bell

System Technical Journal, vol. 27, no. 3, pp. 379–423, July 1948.

C. Shannon, Communication Theory and Secrecy Systems.

Bell Telephone Laboratories, 1949. [Online]. Available:

“RC4 Source Code,” Cypherpunks, September 1994,

B. Harris, “Improved Arcfour Modes for the Secure Shell (SSH)

Transport Layer Protocol,” January 2006. [Online]. Available:

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:

-4 14

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

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:

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: 23

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.

S. Sarkar, “Further non-randomness in RC4, RC4A and VMPC,”

Cryptography and Communications, vol. 7, no. 3, pp. 317–330, 2015.

[Online]. Available:

Y. Tsunoo, T. Saito, H. Kubo, M. Shigeri, T. Suzaki, and T. Kawabata,

“The Most Efficient Distinguishing Attack on VMPC and RC4A.”

F. Glover, “Future Paths for Integer Programming and Links to

Artificial Intelligence,” Comput. Oper. Res., vol. 13, no. 5, pp. 533–

, May 1986. [Online]. Available:


F. Glover and M. Laguna, Tabu Search. Norwell, MA, USA: Kluwer

Academic Publishers, 1997.

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: 3

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

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: 16

J. Strombergson and S. Josefsson, “Test Vectors for the Stream Cipher

RC4,” May 2011. [Online]. Available:


  • There are currently no refbacks.

International Journal of Electronics and Telecommunications
is a periodical of Electronics and Telecommunications Committee
of Polish Academy of Sciences

eISSN: 2300-1933