Using Evolving Algorithms to Cryptanalysis Nonlinear Cryptosystems

In this paper, new method have been investigated using evolving algorithms (EA's) to cryptanalysis one of the nonlinear stream cipher cryptosystems which depends on the Linear Feedback Shift Register (LFSR) unit by using cipher text-only attack. Genetic Algorithm (GA) and Ant Colony Optimization (ACO) which are used for attacking one of the nonlinear cryptosystems called "shrinking generator" using different lengths of cipher text and different lengths of combined LFSRs. GA and ACO proved their good performance in finding the initial values of the combined LFSRs. This work can be considered as a warning for a stream cipher designer to avoid the weak points, which may be found in the stream cipher, and may be explored by the cryptanalysts. This work can find the optimal solution for text with minimum lengths of 20 characters and 100 iteration were very enough to find the real initial values of key stream.


Introduction:
The basic terminology is that cryptography term refers to the science of configure the ciphers; Cryptanalysis term is the science of extraction the clear text without knowing the key. It is a method of conversion ciphertext inside a plaintext without access to the key (1); while cryptology refers to the study of both. The Cryptographic algorithms are ordinarily divided into two parts, Secret algorithms and Public-key algorithms. Secret algorithms need to that communicating parties to share the same secret key. Symmetric key cipher can be sparely collected to Stream cipher and Block cipher. Stream ciphers encipher one byte or one bit at a time (2). For practical reasons, the bit-stream generator should be applied as an algorithmic procedure, so that the cryptographic bit stream can be produced by both users. The bit-stream generator is a keycontrolled algorithm and must generate a bit stream that is cryptographically strong. Now, the two users require only sharing the generating key, and each can generate the key stream. 1  Pseudo-noise sequence created by the linear feedback shift registers (LFSRs) which utilized in cryptography field with some nonlinear combining functions have been suggested as running key generators in the stream cipher, test-pattern generation, signature analysis, uses in digital broadcasting and communications. T. Siegenthaler has stated that the number of attempts to attack these ciphers can be minimizing by using correlation ways (3). Genetic Algorithm (GA) depends on the soft computing ideas of normal operators (4). GA is a good candidate for the perfect cases to optimize and search problems (4). The algorithm has passed implementation on Maximum-Clique problem, Vertex-Cover problem, Regression testing, N-puzzle problem (5) and Traveling Salesman Problem (TSP) (6).
Ant Colony Optimization (ACO) (9) is a well-known meta-heuristic that was successfully utilized to generate approximate solutions for a large variety of optimization problems.
ACO are used to attack Data Encryption Standard (DES) by Khan and et al (6). Also, Grari and et al (9)  In the paper of (6), he used a block cipher while in suggested work, a stream cipher have been used and in the paper (9) use a classical cipher (simple substitution cipher) but suggested work use a modern ciphers (stream ciphers), finally in the paper (12) use a block cipher for four rounds of DES while the suggested work use a stream cipher.
In this paper, ACO and GA as an EA's in new methods have been investigated as automated cryptanalysis system to attack one of the NLSCC called "shrinking generator" using different lengths of ciphertext and different lengths of combined LFSRs using the hardest type of attacking which is called "cipher text-only attack" depending on statistical properties of plaintext as a fitness function.
The rest of this paper is presented as follows: in addition to introduction, introduced Cryptosystems of Stream Cipher have been presented, then the EA which is represented by GA and ACO. Then the fully automated cryptanalysis system using evolutionary computation algorithm (GA and ACO) are presented, then the results and finally, conclusions and recommendations are presented.

The problem and aim of this paper:
The problem of this paper is to attack one of the nonlinear stream cipher generators using one of the evolving algorithms using ciphertext only attack.
In this paper and for the first try, the shrinking generator have been attacked as one of the stream cipher generators, using one of the new important evolving algorithms which is Ant Colony Optimization (ACO) method.
The objective of this attack to find the true initial values of the combined LFSRs of shrinking generator. This attack is applied for the first time, but of course may be there are other evolving algorithms that are used to attack (SG) or/and the ACO is used to attack other stream cipher generators.

Cryptosystems of Stream Ciphers
Stream ciphers form a significant category of symmetric-key enciphering schemes. They enciphered characters of individuals usually in binary digits of a clear-text message one at a time, using conversion of enciphering which it changes with time. One of the most important characteristics of stream cipher, with no error propagation characteristic, hence the transmission errors are highly probable (13). The attacks methods on stream ciphers can be categorized as; cipher textsonly attack, chosen clear text-attack, known cleartext attack and chosen ciphertext -attack. Also there are other kinds of attacking methods implemented upon stream cipher, several of these attacks are: Linear Consistency Attack, Determine and Guess attacks, Algebraic attacks and Inversion Attacks (14). In this paper ,the focus is on the cipher text only attack. This type known as difficult type of attacks for the cryptanalysis field no others data output about or the algorithm of cipher, but may contain information about the allocation of the clear text, like the language of the enciphered a message (15).
Many cryptosystems of stream cipher have been found. In this paper the interest has been in Shrinking Generator (SG) is a form of pseudorandom number generator intended to be used in a stream cipher.

Shrinking Generator (SG)
The SG utilizes a different form of clock control than the previous generators (such as gaffe and bruer generators). Take two LFSRs: R1 and R2. Clock both of them. If the output of R1 is 1, then the output of the generator is R2. If the output of R1 is 0, discard the two bits, clock both LFSRs, and try again. This idea is simple, reasonably efficient, and looks secure. Even so, it's new (16). The following steps are repeated until key-stream of desired length is produced. The main steps of Shrinking Generator algorithm (SG) which are as follows in algorithm 1 Evolving Algorithms (EA) Evolutionary algorithms which model natural evolution processes have been successfully used for optimization. In this paper the focus has been on GA and ACO and utilize it in cryptanalysis field.

Ant Colony Optimization (ACO)
The basic idea of ACO was taken by the determine foods behavior of ant colonies that determine the shortest bath between ant's nest and a resource food by exchanging the data by pheromone deposited on the trips. This pheromone data is utilized to determine the directing of the search path and let ants collaborate with each other in order to determine high quality of good solutions in a large search space (17). The main Pseudo-code and formula of ACO are as follows in algorithm 2: GA's are optimization search algorithms which depend upon the idea of natural selection and natural genetics (18).
An abstract algorithm 3 of the GA is as the following:

GA-ACOCS Using EA
In this section a new cryptanalysis system for stream cipher have been suggested, that depends on GA and ACO algorithms. This cryptanalysis system is called Genetic Algorithm-Ant Colony Optimization Cryptanalysis System (GA-ACOCS).
The comparison was between GA and ACO when these methods are suggested in this work.
Before applying the GA-ACOCS, the encryption system using SG must be discussed. Let's have plaintext with Length L bits to obtain Cipher text (C). The Encryption System using SG (ESSG) steps are as follows in algorithm 4:

Algorithm 4 INPUT: Plaintext (P) characters with length M bytes (ASCII Codes).
Convert the plaintext to L=8*M bits.
For any cryptanalysis system using EA, the following main stages must be available: Step(1) (Initialization step): in the Initial generation, the attacking process starts with random generation process for values in range coding of {0, 1} as the key-stream size for n individuals. The sequence of the generated values indicates the desired keys (individual). Each individual indicates to the candidate key which will be utilized for decrypting the ciphertext and then computing to the fitness function value to save the optimal fitness (the right key).
Step(2) (Fitness Function Calculation): This stage will apply each iteration which includes calculate the fitting value. The fitting value is represented by taking the best-fits of the statistical properties of plaintext depending on the used language. In English language in any plain message, the "0" percentage is about 60% of whole text. So the best fitness must be ≥ 0.60; this rate was as a measure factor in this work, which has been changed depending on various clear-text size. In this paper the fitness function algorithm for ACO and GA in GA-ACOCS can be stated as follows in algorithm 5:

Algorithm 5 Function Fit=F-Fitness (L,P)
Step ( pheromone update stage, while in GA it has been represented in three basic operators; selection, crossover and mutation. In this paper, three samples of plaintext (T1, T2 and T3) have been suggested with sizes 100, 50 and 20 characters, respectively. These three samples give different fitness values for each sample. Table 1 shows the optimal fitness values for each sample. These value are calculated as mentioned above in algorithm 5. Many kinds of SG cryptosystem have been tried, but only two kinds (SG1 and SG2)have been focused with LFSR lengths 5 and 7 for SG1 and 7 and 9 for SG2. Table 2 presents the main parameters of GA-ACOCS.

ACO in GA-ACOCS
ACO has been successfully implemented on various problems (applications) in the field of search and optimization. It is a recursive protocol that contains ant size of tours. These tours are created randomly which correspond to the initial generation. The population has been evolved by applying three basic processes: initialization, fitness calculation, pheromones updating and evaporation process. Table 3 states the ACO parameters were used in GA-ACOCS.

GA in GA-ACOCS
For the Initial Generation, in the GA-ACOCS system starts with randomly generated values in range {0, 1} that are considered as the key size for n chromosomes according to the lengths of LFSRs and sorting these numbers in ascending order. The sequence of these values indicates the correct key (individuals).
While in the Selection operator, chose chromosome in the population for crossover process which is considered to be from GA operators. Roulette-wheel selection is the method which will be utilized in the good solutions selection more often than the other solutions.
In the Crossover Process, two individuals have been selected to crossover process completion to generate a new population. In this work, a singlepoint crossover method has been used.
For Mutation operator, flip mutation method has been used, which changed 1 to 0 and 0 to 1.
In the Fitness Function, the algorithm mentioned in step (2) of section 4 have been used. In the GA variables which represent the mostly used method to cryptanalysis stream cipher cryptosystems by GA which are shown in Table 4. The basic algorithm of cryptanalysis system stated in GA-ACO Cryptanalysis System in algorithm 6

Results of GA-ACOCS Using EA (GA and ACO)
Before discussion of the results of cryptanalysis of SG1 and SG2 using GA-ACOCS in Tables 5 and 6