Group particle swarm optimization for cryptanalysis of classical ciphers T. Mekhaznia1 , M.B. Menai2 , and A. Zidani3 1 1 D´epartement d’Informatique, Universit´e de T´ebessa, 12000 T´ebessa, Alg´erie [email protected] 2 Department of Computer Science, CCIS, King Saud University, P.O. Box 51178, Riyadh 11543, Saudi Arabia [email protected] 3 D´epartement d’Informatique, Universit´e de Batna, Alg´erie [email protected] Introduction Cryptanalysis consists in studying cryptosystems, including ciphers and ciphertexts to break them without necessary knowing the key or the algorithm. This leads, for example, to transform a ciphertext into a plaintext without knowing the decryption key. Classical encryption methods are mainly based on replacing characters in the plaintext by other characters, including substitution and transposition techniques. They are used in most modern symmetric algorithms, such as the Advanced Encryption Standard (AES)[1] and International Data Encryption Algorithm (IDEA)[2]. Classical ciphers represent building blocks for more complex ciphers. They still represent a promising research direction in modern cryptanalysis, due to their simplicity compared to block ciphers. More formally, given an alphabet A = {a0 , a1 , · · · , an−1 } and another alphabet B = {b0 , b1 , · · · , bn−1 } obtained from A with a bijective function k : A → B, which substitutes each character of A by another character of the same set to obtain B. The function k is the encryption key. It can be a simple substitution function, or more complex methods of encrypting alphabetic text, such as Feistel networks [3], Vigen`ere [3], Hill cipher [4], and aﬃne cipher [5]. These encryption algorithms represent a test base for new cryptanalysis methods. The cost function of a decryption key is given by the analysis and comparison of both texts based on tables of character frequency and unigram, bigram, or other models. Automated cryptanalysis of classical ciphers has been tackled using several methods, such as brute force attack, diﬀerential cryptanalysis, and heuristic-based methods. In this paper, we present a variant of the group particle swarm optimization (GPSO) as a meta-heuristic attack of classical ciphers. We show its eﬀectiveness by reporting results of some preliminary experiments, including comparison results obtained with a variant of ant system (Max-Min Ant System) and a genetic algorithm (GA). 2 Cryptanalysis of classical ciphers using GPSO Particle swarm optimization (PSO) [6] is a well-known meta-heuristic that was used successfully to approximate solutions to various real-world optimization problems. PSO is a population-based meta-heuristic inspired by the social foraging behavior, such as ﬂocking behavior of birds and schooling behavior of ﬁsh. PSO consists basically in making particles ﬂy above the ﬁtness landscape. The movement of a particle is inﬂuenced by its attraction to the best solution found by its neighbors and its personal best solution found so far. Group particle swarm optimization (GPSO) [7] is a variant of PSO that consists in maintaining a group of active swarms at any time. The swarms are initially distributed regularly in the search space without ideally overlapping. Each swarm moves independently of the other swarms and has its own global best. The search space is represented by a strongly connected graph of n nodes of ASCII characters. At each move from node xti to node xt+1 , the particle i performs a decryption key kxt ,xt+1 obtained i by swapping the characters xt and xt+1 . The performance of node xt+1 corresponds to the cost of i text obtained using the decryption key kxt ,xt+1 according to a cost function. The next node xt+1 i is selected by the particle i according to the performance f (xi ), performance of its neighbors f (p), 2 Mekhaznia, Menai and Zidani and overall performance of the group f (g). The overall performance of GPSO algorithm depends on the number of swarms and their distribution through the search space. 3 Preliminary results Some experiments have been conducted to test the performance of the proposed GPSO algorithm on a set of sample texts of 120 characters. Encryption methods used are: Polyalph. Substitution, Transposition, Vigen`ere, Polybe/Delastelle, Feistel network, and Aﬃne. Table 1 shows the results obtained in terms of key length, cost function, and average number of much characters. GPSO ﬁnds the maximum number of much characters when Vigen`ere encryption algorithm is used. Table 1. Results of GPSO Encryption algorithm key length Cost function Avg(much characters) Max(much characters)=27 Polyalph. Substitution Transposition Vigen`ere Polybe/Delastelle Feistel network (2 rounds) Aﬃne 4 0.833 8 0.912 6 1 5x5 0.280 XOR mod 26 0.789 0.912 23.04 23.58 27 21.36 19.36 22.10 Table 2 shows results obtained with a Max-Min Ant System and a GA. Overall results (Tables 1,2) show clearly that GPSO outperforms both Max-Min Ant System and GA. Table 2. Results of Max-Min Ant System and GA Encryption algorithm key length Avg(much characters) Max(much characters)=27 Max-Min Ant System GA Polyalph. Substitution Vigen`ere Polybe/Delastelle Feistel network (2 rounds) 4 6 5x5 XOR mod 26 19.22 16.30 10.80 9.38 16.31 12.88 9.04 8.24 References 1. ”Advanced Encryption Standard Development Eﬀort,” http://www.nist.gov/aes. 2. Lai, X., Massey, J.L.: A Proposal for a new block encryption standard, Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology (EUROCRYPT’90), Springer-Verlag (1991), 389-404. 3. Menezes, A., Van Oorschot, P., Vanstone, S.: Handbook of applied cryptography (Discrete Mathematics and its Applications), Series Editor Kenneth H. Rosen, CRC Press, (1997). 4. Gupta, I., Singh, J., Chaudhary, R.: Cryptanalysis of an extension of the Hill cipher, Cryptologia 31(3), (2007), 246–253. 5. Biryukov, A., De Canni`eere, C., Braeken, A., Preneel, B.:A toolbox for cryptanalysis: linear and aﬃne equivalence algorithms, Proceedings of the 22nd international conference on Theory and applications of cryptographic techniques (EUROCRYPT’03), Warsaw, Poland, Springer-Verlag, (2003), 33–50. 6. Kennedy, J., Eberhart, R.:Particle Swarm Optimization, Proceedings of IEEE International Conference on Neural Networks IV, (1995), 1942-1948. 7. Nalini, N.: Experiments on cryptanalysing block ciphers via evolutionary computation paradigms, Proceedings of the International Conference on Evolutionary Computing, Cavtat, Croatia, (2006), 20–27.