Fitness Landscape Analysis of Block Ciphers for Cryptanalysis using Metaheuristics

Fitness Landscape Analysis of Block Ciphers for Cryptanalysis using Metaheuristics
  IJETT-book-cover           
  
© 2022 by IJETT Journal
Volume-70 Issue-6
Year of Publication : 2022
Authors : Seeven Amic, K. M. Sunjiv Soyjaudah, Gianeshwar Ramsawock
DOI : 10.14445/22315381/IJETT-V70I6P227

How to Cite?

Seeven Amic, K. M. Sunjiv Soyjaudah, Gianeshwar Ramsawock, "Fitness Landscape Analysis of Block Ciphers for Cryptanalysis using Metaheuristics ," International Journal of Engineering Trends and Technology, vol. 70, no. 6, pp. 257-271, 2022. Crossref, https://doi.org/10.14445/22315381/IJETT-V70I6P227

Abstract
Fitness Landscape Analysis is a well-known method that has been used to evaluate or predict the performance of evolutionary or metaheuristic algorithms for tackling combinatorial optimization problems. Researchers often attempt to solve combinatorial optimization problems using metaheuristic algorithms without having proper knowledge of the underlying nature and behaviour of the problem. A similar scenario is observed in cryptanalysis using metaheuristic methods with limited or unconvincing results. There is no evidence of successful cryptanalysis of modern block ciphers such as DES or AES using metaheuristics except for toy, weakened or classical ciphers. This work aims at establishing whether metaheuristics, in general, is an efficient and promising approach to solving the problem of cryptanalysis of block ciphers. FLA has been used for this purpose. Experimental investigations reveal that the failure of cryptanalysis might be due to the high level of the ruggedness of the fitness landscape of the cryptographic keys. Furthermore, it is shown that the terrain of the fitness of cryptographic keys tends to become more rugged as the key space becomes larger, which, at this stage, tends to indicate that metaheuristic algorithms may not be very appropriate to perform rigorous cryptanalysis.

Keywords
Block Cipher, Cryptanalysis, Fitness Landscape Analysis, Local Optima Network, Metaheuristics

Reference
[1] R. Toemeh and S. Arumugam, Applying Genetic Algorithms for Searching Key-Space of Polyalphabetic Substitution Ciphers, Int. Arab J. Inf. Technol., 5(1) (2008) 87–91.
[2] A. Bhateja, S. Kumar, and A. K. Bhateja, Cryptanalysis of Vigenere Cipher Using Particle Swarm Optimization with Markov Chain Random Walk, Int. J. Comput. Sci. Eng., 5(5) (2013) 422–429.
[3] S. S. Omran, A. S. Al-Khalid, and D. M. Al-Saady, A Cryptanalytic Attack on Vigenere Cipher Using Genetic Algorithm, 2011 Ieee Conf. Open Syst., 1 (2011) 59–64.
[4] P. Saveetha, Cryptography and the Optimization Heuristics Techniques, 4(10) (2014) 408–413.
[5] J. Song, H. Zhang, Q. Meng, and Z. Wang, Cryptanalysis of Four-Round Des Based on Genetic Algorithm, Int. Conf. Wirel. Commun. Netw. Mob. Comput. Wicom , (2007) 2326–2329.
[6] T. Mekhaznia, Nature Inspired Heuristics for Attack of Simplified Des Algorithm, Sin 2013 - Proc. 6th Int. Conf. Secur. Inf. Networks, (2013) 311–315.
[7] W. Shahzad, A. B. Siddiqui, and F. A. Khan, Cryptanalysis of Four-Rounded Des using Binary Particle Swarm Optimization, Simulation, (2009) 1757–1758.
[8] D. H. Wolpert and W. G. Macready, No Free Lunch Theorems for Optimization, Ieee Trans. Evol. Comput., 1(1) (1997) 67–82.
[9] S. M. Almufti, Historical Survey on Metaheuristics Algorithms, Int. J. Sci. World, 7(1) (2019) 1.
[10] S. Wright, the Roles of Mutation, Inbreeding, Crossbreeding and Selection in Evolution, In the Sixth International Congress of Genetics, 1 (1932) 356–366.
[11] S. Kauffman and S. Levin, Towards a General Theory of Adaptive Walks on Rugged Landscapes Section of Ecology and Systematics , and Ecosystems Research Center , New York, 128(1) (1987) 11–45.
[12] F. Glover, Future Paths for Integer Programming and Links to Artificial Intelligence, 13(5) (1986) 533–549.
[13] C. Blum and A. Roli, Metaheuristics In Combinatorial Optimization: Overview and Conceptual Comparison, Acm Comput. Surv., 35(3) (2003)189–213.
[14] P. F. Stadler and S. F. Institute, Towards a Theory of Landscapes, Complex Syst. Bin. Networks, (2008) 78–163.
[15] K. M. Malan, A Survey of Advances in Landscape Analysis for Optimisation, Algorithms, 14(2) (2021) 40.
[16] E. Pitzer and M. Affenzeller, A Comprehensive Survey on Fitness Landscape Analysis, Stud. Comput. Intell., 378 (2012) 161– 191.
[17] K. M. Malan and A. P. Engelbrecht, A Survey of Techniques for Characterising Fitness Landscapes and Some Possible Ways Forward, Inf. Sci. (Ny)., 241 (2013) 148–163.
[18] T. Jones and S. Forrest, Fitness Distance Correlation As A Measure of Problem Difficulty for Genetic Algorithms, In Proc.\ of 6th Int.\ Conf.\ on Genetic Algorithms, (1995) 184–192.
[19] E. Weinberger, Correlated and Uncorrelated Fitness Landscapes and How to Tell the Difference, Biol. Cybern., 63(5) (1990) 325–336.
[20] V. K. Vassilev, T. C. Fogarty, and J. F. Miller, Information Characteristics and the Structure of Landscapes, Evol. Comput., 8(1) (2000) 31–60.
[21] Ramanathan.L and Ulaganathan.K, Nature-Inspired Metaheuristic Optimization Technique-Migrating Bird‟S Optimization in Industrial Scheduling Problem Ssrg International Journal of Industrial Engineering,1(2) (2014) 12-17.Crossref, Https://Doi.Org/10.14445/23499362/Ijie-V1i3p101
[22] J. Horn and D. E. Goldberg, Genetic Algorithm Difficulty and the Modality of Fitness Landscapes, Second Edi., Morgan Kaufmann Publishers, Inc.,3 (1995).
[23] L. Altenberg, the Schema Theorem and Price’s Theorem, (1995) 23–49.
[24] G. Ochoa, S. Verel, F. Daolio, and M. Tomassini, Local Optima Networks: A New Model of Combinatorial Fitness Landscapes, (2014) 233–262.
[25] J. P. K. Doye, Network Topology of a Potential Energy Landscape: A Static Scale-Free Network, Phys. Rev. Lett., 88 (23) (2002) 4.
[26] S. Vérel, F. Daolio, G. Ochoa, and M. Tomassini, Local Optima Networks with Escape Edges, Lect. Notes Comput. Sci. (Including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), 7401 (2012) 49–60.
[27] A. Barrat, M. Barthélemy, R. Pastor-Satorras, and A. Vespignani, the Architecture of Complex Weighted Networks, Proc. Natl. Acad. Sci. U. S. A., 101(11) (2004) 3747–3752.
[28] M. E. J. Newman, Assortative Mixing in Networks, Phys. Rev. Lett., 89(20) (2002) 1-5.
[29] P. T. Breuer, An 8- and 12-Bit Block Aes Cipher. Academia.Edu, (2013) 1–33.
[30] Edward F. Schaefer, A Simplified Data Encryption Standard Algorithm, Cryptologia, 20(1) (1996) 77–84.
[31] R. C. Phan, Mini Advanced Encryption Standard (Mini-Aes), Publ. Cryptologia, 26(4) (2002).
[32] S. Verel, F. Daolio, G. Ochoa, and M. Tomassini, Local Optima Networks with Escape Edges, In International Conference on Artificial Evolution (Ea-2011), (2011) 10–23.
[33] J. E. Fieldsend, Computationally Efficient Local Optima Network Construction, Gecco 2018 Companion - Proc. 2018 Genet. Evol. Comput. Conf. Companion, (2018) 1481–1488.
[34] M. Barthélemy, A. Barrat, R. Pastor-Satorras, and A. Vespignani, Characterization and Modeling of Weighted Networks, Phys. A Stat. Mech. Its Appl., 346(1-2) Spec. Iss (2005) 34–43.
[35] S. Verel, F. Daolio, G. Ochoa, and M. Tomassini, Sampling Local Optima Networks of Large Combinatorial Search Spaces: the Qap Case, Lect. Notes Comput. Sci. (Including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), 11102 (2018) 257– 268.
[36] S. L. Thomson, G. Ochoa, S. Verel, and N. Veerapen, Inferring Future Landscapes: Sampling the Local Optima Level, Evol. Comput., 28(4) (2019) 621–641.
[37] S. L. Thomson, G. Ochoa, and S. Verel, Clarifying the Difference in Local Optima Network Sampling Algorithms, Lect. Notes Comput. Sci. (Including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), 11452 (2019) 163–178.
[38] G. W. Greenwood and X. Hu, are Landscapes for Constrained Optimization Problems Statistically Isotropic?, Phys. Scr., 57(3) (1998) 321–323