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.
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.
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 |
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 |
Evolutionary optimization of constrained problems. InProc.3rd annu. Conf. on Evolutionary Programming, 1994. p. .
Optimisation Heuristics for the Automated Cryptanalysis of Classical Ciphers. Journal of Combinatorial Mathematics and Combinatorial Computing 1998. 28 p. .
Studying chaos via 1-Dmaps-atutorial. IEEE Trans. on Circuits and Systems I: Fundamental Theory and Applications 1993. 40 (10) p. .
A Simplified Data Encryption Standard Algorithm. Cryptologia 1996. 20 (1) p. .
Genetic algorithm Attack on Simplified Data Encryption Standard Algorithm. International journal Research in Computing Science 2006. p. .
Linear cryptanalysis method for DES cipher. Lect. Notes Comput. Sci 1994. 765 p. .
Cryptanalysis of SDES Using Genetic Algorithm. International Journal of Recent Trends in Engineering November 2009. 2 (4) p. .
Cryptanalysis of S-DES via Optimization heuristics. International Journal of Computer Sciences and network security Jan 2006. 6 (1B) .
Cryptanalysis of Knapsack Ciphers Using Genetic Algorithms. Cryptologia XVII 1993. (4) p. .
Use of A Genetic Algorithm in the Cryptanalysis of simple substitution Ciphers. Cryptologia XVII 1993. (1) p. .