Breaking of Simplified Data Encryption Standard Using Genetic Algorithm

Table of contents

1.

cipher is a secret way of writing in which plaintext is converted into a scrambled (encrypted) version of the original message (ciphertext) by using a key. Those who know the key can easily decrypt the ciphertext back into the plaintext. Cryptanalysis is the study of breaking ciphers that is finding the key or converting the ciphertext into the plaintext without knowing the key. Many cryptographic systems have a finite key space and, hence, are vulnerable to an exhaustive key search attack. Yet, these systems remain secure from such an attack because the size of the key space is such that the time and resources for a search are not available. Optimization techniques have got a significant importance in determining efficient solutions of different complex problems. One such problem is to break S-DES. This paper considers cryptanalysis of S-DES. In the brute force attack, the attacker tries each and every possible key on the part of cipher text until desired plaintext is obtained. A brute force approach may take so much time to guess the real key which is used to generate a cipher text, so the difficulty of breaking the cipher is directly proportional to the number of keys. On the other hand optimization technique can be used for the same purpose. Genetic algorithm is an evolutionary algorithm that works well and takes less time to break cipher as compared to Brute force attack.

The remaining paper is organized as follows: Section II discusses the earlier works done in this field. Section III presents overview of S-DES and Section IV gives the overview of Genetic Algorithm. Experimental results are discussed in Section V.Conclusion are presented in section VI At last References are given.

In the last few years, so many papers have been published in the field of cryptanalysis. R.Spillman etc. showed that Knapsack cipher [4] and substitution ciphers [5] could be attacked using genetic algorithm. In the recent years Garg[1,2] presented the use of memetic algorithm and genetic algorithm to break a simplified data encryption standard algorithm. Nalini [3] used efficient heuristics to attack S-DES. In 2006 Nalini used GA, Tabu search and Simulated Annealing techniques to break S-DES. Matusi [7] showed the first experimental cryptanalysis of DES using an linear cryptanalysis technique. Clark [6] also presented important analysis on how different optimization techniques can be used in the field of cryptanalysis. Vimalathithan [9] also used GA to attack Simplified-DES. In this paper, a Genetic Algorithm with improved parameters is used to break S-DES.A population of keys is generated and their fitness is calculated by using efficient fitness function. At the end, we will find the key in less time.

In this section we will provide the overview of S-DES Algorithm. Simplified DES, developed by Professor Edward Schaefer of Santa Clara University is an educational rather than a secure encryption algorithm. The S-DES [8,10] encryption algorithm takes an 8-bit block of plaintext and a 10-bit key as input and produces an 8-bit block of ciphertext as output. The S-DES decryption algorithm takes an 8-bit block of ciphertext and the same 10-bit key used to produce that ciphertext as input and produces the original 8-bit block of plaintext. The encryption algorithm involves five functions: an initial permutation (IP); a complex function labeled f K , which involves both permutation and substitution operations and depends on a key input; a simple permutation function that switches (SW) the two halves of the data; the function f K again; and finally a permutation function that is the inverse of the initial permutation (IP -1 ).

The function f K takes as input not only the data passing through the encryption algorithm, but also an 8bit key. S-DES uses a 10-bit key from which two 8-bit subkeys are generated. In this, the key is first subjected to a permutation (P10). Then a shift operation is performed. The output of the shift operation then passes through a permutation function that produces an 8-bit output (P8) for the first subkey (K 1 ). The output of the shift operation also feeds into another shift and another instance of P8 to produce the second subkey (K 2 ). The S-boxes operate as follows:

The first and fourth input bits are treated as 2-bit numbers that specify a row of the S-box and the second and third input bits specify a column of the Sbox. The entry in that row and column in base 2 is the 2-bit output.

2. The Switch Function

The function f K only alters the leftmost 4 bits of the input. The switch function (SW) interchanges the left and right 4 bits so that the second instance of f K operates on a different 4 bits. In this second instance, the E/P, S0, S1, and P4 functions are the same. The key input is K2.

The genetic algorithm [13,20] is a search algorithm based on the natural selection and on "survival of the fittest", the main idea is that in order for a population of individuals to adapt to some environment, it should behave like a natural system. This means that survival and reproduction of an individual is promoted by the elimination of useless traits and by rewarding useful behavior. The genetic algorithm belongs to the family of evolutionary algorithms. An evolutionary algorithm maintains a population of solutions for the problem at hand. The population is then evolved by the iterative application of a set of stochastic operators. The simplest form of genetic algorithm involves three types of operators: selection, crossover and mutation. A selection operator is applied first. In this paper, we are using Ring crossover operator [11].In ring crossover two parents such as parent1 and parent2 are considered for the crossover process, and then combined in the form of ring, as shown in fig. 4 decided in any point of ring. The children are created with a random number generated in any point of ring according to the length of the combined two parental chromosomes. With reference to the cutting point, while one of the children is created in the clockwise direction, the other one is created in direction of the anticlockwise, as shown in fig. 4(c). Then swapping and reversing process is performed in the Ring Crossover operator, as shown in fig. 4(d).

Figure 4 : Ring Crossover Procedure [11] The primary goals of this work are to produce a performance comparison between traditional Brute force search algorithm and genetic algorithm with improved parameters based method, and to determine the use of typical GA-based methods in the field of cryptanalysis.

The procedure to carry out the cryptanalysis using GA in order to break the key is as follows 1. Input: ciphertext, and the language statistics. 2. Randomly generate an initial pool of solutions (keys).

C K = (i Ã) |K (i) u -D(i) u | + (i, j Ã) | K (i, j) b -D (i, j) b | + (i,j,k Ã)|K(i,j,k) t -D(i,j,k) t | (!)

Our objective in this paper is to compare the results obtained from Brute Force search algorithm with the Genetic Algorithms with improved parameters. The experiments were conducted on Core chromosome, the more times it is likely to be selected to reproduce. Crossover : Crossover selects genes from is parent chromosomes and creates a new offspring. The simplest way to do this is to choose randomly some crossover point and everything before this point is copied from the first parent and then, everything after a crossover point copied from the second parent. Mutation : After a crossover, mutation is performed. This is to prevent falling all solutions in population into a local optimum of solved problem. Mutation changes randomly the new offspring. In binary GA we can switch a few randomly chosen bits from 1 to 0 or from 0 to 1. From the above table, it is found that both GA works better than Brute force algorithm in terms of time taken as well as obtaining number of key bits. In this paper, we have used a Genetic algorithm with Ring crossover and other operators for the cryptanalysis of Simplified Data Encryption Standard. We found that Genetic Algorithm is far better than Brute Force search algorithm for cryptanalysis of S-DES. Although S-DES is a simple encryption algorithm, GA with Ring Crossover method can be adopted to handle other complex block ciphers like DES and AES.

Figure 1. Figure 1 :
1Figure 1: Simplified Data Encryption Algorithm a) Initial and Final Permutations The input to the algorithm is an 8-bit block of plaintext, which we first permute using the IP function IP= [2 6 3 1 4 8 5 7].This retains all 8-bits of the plaintext but mixes them up. At the end of the algorithm, the inverse permutation is applied; the inverse permutation is done by applying, IP -1 = [4 1 3 5 7 2 8 6] where we have IP -1 (IP(X)) =X. b) The Function f K The function f k , which is the complex component of S-DES, consists of a combination of permutation and substitution functions. The functions are given as follows. Let L, R be the left 4-bits and right 4-bits of the input, then, f K (L, R) = (L XOR f(R, key), R) Where XOR is the exclusive-OR operation and key is a sub -key. Computation of f(R, key) is done as follows.
Figure 2. Figure 2 :
2Figure 2 : Working of S-box
Figure 3. Global
Journal of Computer Science and Technology Volume XII Issue V Version I 2012 March c) Selection : This selection operator selects chromosomes in the population for reproduction. The better the
Figure 4. Figure 3 :
3Figure 3 : Flow chart of Genetic Algorithm [19]
Figure 5. 3 .
3Calculate the fitness value of each of the solutions in the pool using equation (1). 4. Create a new population by repeating following steps until the new population is complete a. Select parent (keys) from a current population according to their fitness value (the better fitness, the bigger chance to be selected). Here Tournament selection is used. b. With a crossover probability cross over the parents to form new offspring (childrens). In our genetic algorithm we are using Ring Crossover Operator c. For each of the children, perform a mutation operation with some mutation probability to generate new children. d. Place new children in the new population 5. Use new generated population for a further run of the algorithm 6. If the end condition is satisfied, stop, and return the best solution in current population a) Cost Function Equation (1) is a general fitness function used to determine the suitability of a assumed key (k). Here, A denotes the language alphabet (i.e., for English, [A... Z, _ ], where _ represents the space symbol), K and D denote known language statistics and decrypted message statistics, respectively, and the u, b, and t denote the unigram, digram and trigram statistics respectively; , and are the weights assigning different weights to each of the three statistics where + + = 1. In view of the computational complexity of trigram, only unigram and digram statistics are used.
Figure 6. 2
2Duo system. There are a variety of cost functions used by other researchers in the past. The most common cost function uses gram statistics. Some use a large amount of grams © 2012 Global Journals Inc. (US) Global Journal of Computer Science and Technology Volume XII Issue V Version I 57 2012 March (b). Later, a random cutting point is
Figure 7. Figure 5 :
5Figure 5 : comparison of Genetic algorithm and Brute Force Search algorithm
Figure 8. Figure 6 :
6Figure 6 : The running time comparison of Genetic Algorithm and Brute Force Search Algorithm
Figure 9.
1. G Poonam, Memetic Algorithm Attack on Simplified Data Encryption Standard algorithm, proceeding of International Conference on Data Management, February 2008, pg 1097-1108 Computer Science and Technology Volume XII Issue V Version I
Figure 10. Comparison Between GA and Brute Force Search Algorithm
GA Parameters
The following are the GA parameters used
during the experimentation:
Population Size: 100
Selection : Tournament Selection operator
Crossover Ring Crossover
Crossover: .85
Mutation: .02
No. of Generation: 50
Genetic
Algorithm
Brute Force
Search
Algorithm
Figure 11. Table 1 :
1
Force Search Algorithm.
S. Amount No. of No. of Time Time
No of bits bits Taken Taken
Cipher matched matche by GA by
Text using d using (M) Brute
GA Brute Force
Force search
search (M)
1. 200 5 5 4.7 24.3
2. 400 4 3 2.1 24.7
3. 600 7 6 1.9 23.6
4. 800 8 7 3.1 24.1
5. 1000 9 7 2.6 25.1
6. 1200 9 8 2.1 25.5
1
56

Appendix A

  1. Evolutionary optimization of constrained problems. A , Michalewiez , N Attia . InProc.3rd annu. Conf. on Evolutionary Programming, 1994. p. .
  2. Optimisation Heuristics for the Automated Cryptanalysis of Classical Ciphers. ClarkA , Dawson Ed . Journal of Combinatorial Mathematics and Combinatorial Computing 1998. 28 p. .
  3. Studying chaos via 1-Dmaps-atutorial. C W Wu , N F Rulkov . IEEE Trans. on Circuits and Systems I: Fundamental Theory and Applications 1993. 40 (10) p. .
  4. Genetic algorithms in search. Optimization and Machine Learning, D E Goldberg . Reading. M.A. addison -Wesley (ed.) 1989.
  5. A Simplified Data Encryption Standard Algorithm. E Schaefer . Cryptologia 1996. 20 (1) p. .
  6. Genetic algorithm Attack on Simplified Data Encryption Standard Algorithm. Garg Poonam . International journal Research in Computing Science 2006. p. .
  7. , J Alfred , Menezes , Menezes . Alfred J. Handbook of Applied Cryptography 1997. CRC.
  8. Multi-objective Optimization using Evolutionary Algorithms, Kalyanmoy Deb . 2001. John Wiley and Sons.
  9. Handbook of Genetic Algorithm, L Davis . 1991. New York: Van Nostrand Reinhold.
  10. Linear cryptanalysis method for DES cipher. M Matsui . Lect. Notes Comput. Sci 1994. 765 p. .
  11. Cryptanalysis of SDES Using Genetic Algorithm. M R L Vimalathithan , Valarmathi . International Journal of Recent Trends in Engineering November 2009. 2 (4) p. .
  12. Cryptanalysis of S-DES via Optimization heuristics. Nalini . International Journal of Computer Sciences and network security Jan 2006. 6 (1B) .
  13. A Course on number theory and cryptography, N Koblitz . 1994. Springer-Verlag New York,Inc.
  14. Cryptanalysis of Knapsack Ciphers Using Genetic Algorithms. R Spillman . Cryptologia XVII 1993. (4) p. .
  15. Use of A Genetic Algorithm in the Cryptanalysis of simple substitution Ciphers. R Spillman , M Janssen , B Nelson , M Kepner . Cryptologia XVII 1993. (1) p. .
  16. Breaking Transposition Cipher with Genetic Algorithhm Electronics and Electrical Engineering, R Toemeh , S Arumugam . 2007.
  17. Cryptography and Network Security Principles and Practices, Third Edition, William Stallings . 2003. Pearson Education Inc.
  18. A Novel Crossover Operator for Genetic Algorithms: Ring Crossover, Y?lmaz Kaya , Murat Uyar , Ramazan Tekdn .
  19. Genetic algorithms+ Data structures = Evolution programs, Z Michalewicz . 1996. New York: springer. (3rd ed)
Notes
1
© 2012 Global Journals Inc. (US) Global Journal of Computer Science and Technology Volume XII Issue V Version I
56.
© 2012 Global Journals Inc. (US)
Date: 2012-05-15