REVIEW OF THE APPLICATIONS OF METAHEURISTIC APPROACH IN CRYPTANALYSIS
DOI:
https://doi.org/10.35546/kntu2078-4481.2023.2.20Keywords:
cryptanalysis, cryptography, cipher, combinatorial optimization, algorithm, metaheuristicsAbstract
Cryptographic protection of information is an important component of information security. The development of new methods of cryptanalysis helps to understand the limits of stability of existing cryptosystems. Modern cryptanalysis relies on various mathematical disciplines, in particular, on the theory and methods of optimization. Taking into account the generally accepted requirements for the stability of ciphers, the decryption problem can be considered as a combinatorial optimization problem. Methods and algorithms of combinatorial optimization today play an important role in research related to a range of problems directly affecting information security. The task of cryptographic protection of information is solved by creating new and improving existing encryption algorithms. On the other hand, the rapidly growing capabilities of computer technology open up practical prerequisites for the implementation of cryptanalysis technologies that were not available before. In particular, up-to-date cryptanalysis technologies include the use of optimization randomized algorithms for intelligent exploration of the search space in order to obtain an acceptable result. It is theoretically justified that such algorithms, under certain conditions, allow obtaining a solution when the probability of success is very small. The main tool for analyzing the effectiveness of optimization randomized algorithms is a computational experiment. Analysis of the possibility, features and limits of the use of metaheuristic algorithms by cryptanalysts indicates the prospect of using the metaheuristic approach as a universal method of cryptanalysis. The paper substantiates the need for the development of new methods of cryptanalysis using metaheuristics, contains a retrospective review of publications in the last period in this area. The number of publications indicates the relevance of the research direction.
References
Гуляницький Л. Ф., Мулеса О.Ю. Прикладні методи комбінаторної оптимізації. Київ: ВПЦ «Київський університет». 2016. 142 с.
Andrew Clark, Ed Dawson, Optimisation Heuristics for the Automated Cryptanalysis of Classical Ciphers. Journal of Combinatorial Mathematics and Combinatorial Computing. Vol. 28. 1998. pp. 63–86.
M. D. Russell, J. A. Clark and S. Stepney. Making the most of two heuristics: breaking transposition ciphers with ants. The 2003 Congress on Evolutionary Computation, 2003. CEC ‘03., Canberra, ACT, Australia Vol. 4. 2003. pp. 2653–2658. https://doi.org/10.1109/CEC.2003.1299423
Dimovski A., Gligoroski D. Attacks on the Transposition Ciphers Using Optimization Heuristics. International Scientific Conference on Information, Communication Energy Systems,Technologies. ICEST 2003.
Toemeh R., Arumugam S. Breaking Transposition Cipher with Genetic Algorithm. Elektronika Ir Elektrotechnika. 79(7). 2007. pp. 75–78. https://eejournal.ktu.lt/index.php/elt/article/view/10844
Uddin M. F., Youssef A. M. An artificial life technique for the cryptanalysis of simple substitution ciphers. Canadian Conference on Electrical and Computer Engineering. IEEE. 2006. pp. 1582–1585. http://dx.doi.org/10.1109%2FCCECE.2006.277769
Song J., Zhang H., Meng Q., Zhangyi W. Cryptanalysis of Four-Round DES Based on Genetic Algorithm. Wirel. Commun. Netw. Mob. Comput. IEEE, 2007, 10. pp. 2326–2329. https://doi.org/10.1109/WICOM.2007.580
Garg P. A. Comparison between Memetic algorithm and Genetic algorithm for the cryptanalysis of Simplified Data Encryption Standard algorithm. Int. J. Netw. Secur. Its Appl. (IJNSA). 1. 2009. pp. 34–42. https://doi.org/10.48550/arXiv.1004.0574
Hu W. Cryptanalysis of TEA using quantum-inspired genetic algorithms. J. Softw. Eng. Appl. 3. 2010. pp. 50–57. http://dx.doi.org/10.4236/jsea.2010.31006
Abd-Elmonim W.G., Ghali N.I., Hassanien A.E., Abraham. A. Known-Plaintext Attack of DES16 Using Particle Swarm Optimization. In Proceedings of the Third IEEE World Congress on Nature and Biologically Inspired Computing. Salamanca. Spain. 2011. pp. 12–16. https://doi.org/10.1109/NaBIC.2011.6089410
Mekhaznia T., Menai M. Cryptanalysis of classical ciphers with ant algorithms. International Journal of Metaheuristics. 3(3). 2014. pp. 175–198. https://doi.org/10.1504/IJMHEUR.2014.065159
Boryczka U., Dworak K. Genetic Transformation Techniques in Cryptanalysis. In: Nguyen, N.T., Attachoo, B., Trawiński, B., Somboonviwat, K. (eds) Intelligent Information and Database Systems. ACIIDS 2014. Lecture Notes in Computer Science. vol. 8398. 2014. Springer, Cham. https://doi.org/10.1007/978-3-319-05458-2_16
Dadhich A., Gupta A., Yadav S. Swarm Intelligence based linear cryptanalysis of four-round Data Encryption Standard algorithm. International Conference on Issues and Challenges in Intelligent Computing Techniques (ICICT), 2014, pp. 378–383. http://dx.doi.org/10.1109%2FICICICT.2014.6781312
Sadeghzadeh M, Taherbaghal M. A new method for decoding an encrypted text by genetic algorithms and its comparison with tabu search and simulated annealing. Management Science Letters. 4(2). 2014. pp. 213–220. https://doi.org/10.5267/j.msl.2013.12.037
Teytaud F., Fonlupt, C. A. Critical Reassessment of Evolutionary Algorithms on the cryptanalysis of the simplified data encryption standard algorithm. 2014. ArXiv, abs/1407.1993. https://doi.org/10.5121/IJCIS.2014.4201
Ashok K. Bhateja, Aditi Bhateja, Santanu Chaudhury, P.K. Saxena. Cryptanalysis of Vigenere cipher using Cuckoo Search. Applied Soft Computing, Vol. 26. 2015. pp. 315–324. https://doi.org/10.1016/j.asoc.2014.10.004
Tahar, M. BAT algorithm for Cryptanalysis of Feistel cryptosystems. 3(2). 2015. pp. 82–85. https://doi.org/10.18201/ijisae.82426
Dworak K., Boryczka U. Differential Cryptanalysis of FEAL4 Using Evolutionary Algorithm. In: Nguyen, N., Iliadis, L., Manolopoulos, Y., Trawiński, B. (eds) Computational Collective Intelligence. ICCCI 2016. Lecture Notes in Computer Science. 2016. vol. 9876. Springer. Cham. https://doi.org/10.1007/978-3-319-45246-3_10
Dworak, K., Nalepa, J., Boryczka, U., Kawulok, M. Cryptanalysis of SDES Using Genetic and Memetic Algorithms. In: Król, D., Madeyski, L., Nguyen, N. (eds) Recent Developments in Intelligent Information and Database Systems. Studies in Computational Intelligence. vol 642. 2016. Springer. Cham. https://doi.org/10.1007/978-3-319-31277-4_1
Dworak, K., Boryczka, U. Genetic Algorithm as Optimization Tool for Differential Cryptanalysis of DES6. In: Nguyen, N., Papadopoulos, G., Jędrzejowicz, P., Trawiński, B., Vossen, G. (eds) Computational Collective Intelligence. ICCCI 2017. Lecture Notes in Computer Science. vol. 10449. Springer. Cham. 2017. https://doi.org/10.1007/978-3-319-67077-5_11
Amic S., Soyjaudah K.S., Mohabeer H., Ramsawock. G. Cryptanalysis of DES16 using binary firefly algorithm. In Proceedings of the 2016 IEEE International Conference on Emerging Technologies and Innovative Business Practices for the Transformation of Societies. IEEE: Balaclava. Mauritius. 2016. pp. 94–99. https://doi.org/10.1109/EmergiTech.2016.7737318
Amic S., Soyjaudah K.S., Ramsawock G. Binary cat swarm optimization for cryptanalysis. In Proceedings of the 2017 IEEE International Conference on Advanced Networks and Telecommunications Systems (ANTS). Bhubaneswar. India. 2017. pp. 1–6. https://doi.org/10.1109/ANTS.2017.8384120
Candra A., Budiman M.A., Rachmawati D. On Factoring The RSA Modulus Using Tabu Search. Journal of Computing and Applied Informatics, vol. 1(1). 2017. pp. 30–37. https://doi.org/10.32734/JOCAI.V1.I1-65
Grari H., Azouaqui A., Zine-Dine K., Bakhouya M., Gaber J. Cryptanalysis of Knapsack Cipher Using Ant Colony Optimization. Smart Application and Data Analysis for Smart Cities. 2018. http://dx.doi.org/10.2139/ssrn.3185322
Grari H., Azouaoui A., Zine-Dine K. A Novel Ant Colony Optimization Based Cryptanalysis of Substitution Cipher. In: Abraham, A., Haqiq, A., Ella Hassanien, A., Snasel, V., Alimi, A. (eds) Proceedings of the Third International Afro-European Conference for Industrial Advancement AECIA 2016. Advances in Intelligent Systems and Computing. vol. 565. 2016. pp. 180–187. https://doi.org/10.1007/978-3-319-60834-1_19
Grari H., Azouaoui A., Zine-Dine K. Ant colony optimization for cryptanalysis of simplified-DES. In Advanced Intelligent Systems for Sustainable Development (AI2SD’2018) Vol. 2: Advanced Intelligent Systems Applied to Energy. 2019. pp. 111–121. https://doi.org/10.1007/978-3-030-12065-8_11
Grari H., Azouaoui A., Zine-Dine K. A cryptanalytic attack of simplified-AES using ant colony optimization. International Journal of Electrical & Computer Engineering. 9(5). 2019. pp. 4287–4295. https://doi.org/10.11591/ijece.v9i5.pp4287-4295
Jain A., Chaudhari N. S. An improved genetic algorithm and a new discrete cuckoo algorithm for solving the classical substitution cipher. International Journal of Applied Metaheuristic Computing (IJAMC). 10(2). 2019. pp. 109–130. DOI: 10.4018/IJAMC.2019040105
Amic S., Soyjaudah K.S., Ramsawock G. Dolphin swarm algorithm for cryptanalysis. In Information Systems Design and Intelligent Applications; Satapathy, S., Bhateja, V., Somanah, R., Yang, X.S., Senkerik, R., Eds.; Advances in Intelligent Systems and Computing. Vol. 863. 2019. pp. 149–163. https://doi.org/10.1007/978-981-13-3338-5_15
D. Rachmawati, H. Tamara, S. Sembiring, M. Budiman. RSA public key solving technique by using genetic algorithm. Journal of Theoretical and Applied Information Technology, Vol. 98. 15. 2020. pp. 2990–2999.
Sabonchi A. K. S., Akay B. Cryptanalysis of polyalphabetic cipher using differential evolution algorithm. Tehnički vjesnik. 27(4). 2020. pp. 1101–1107. https://doi.org/10.17559/TV-20190314095054
Akay B. A binomial crossover based artificial bee colony algorithm for cryptanalysis of polyalphabetic cipher. Tehnički vjesnik. 27(6). 2020. pp. 1825–1835. https://doi.org/10.17559/TV-20190422225110
Sabonchi A. K. S., Akay B. A survey on the Metaheuristics for Cryptanalysis of Substitution and Transposition Ciphers. Computer Systems Science And Engineering, vol. 39. 1. 2021. pp. 87–106. http://doi.org/10.32604/csse.2021.05365
Grari H., Lamzabi S., Azouaoui A., Zine-Dine K. Cryptanalysis of Merkle-Hellman cipher using ant colony optimization. Int J Artif Intell. 2021. pp. 490–500. DOI: 10.11591/ijai.v10.i2
Dworak K., Boryczka U. Breaking Data Encryption Standard with a Reduced Number of Rounds Using Metaheuristics Differential Cryptanalysis. Entropy. vol. 23. 12. 2021. pp. 1697–1718. https://doi.org/10.3390/e23121697
