Cryptanalysis of Geffe Generator Using Genetic Algorithm

The use of basic crypto-primitives or building blocks has a vital role in the design of secure crypto algorithms. Such crypto primitives must be analyzed prior to be incorporated in crypto algorithm. In cryptanalysis of any crypto algorithm, a cryptanalyst generally deals with intercepted crypts without much auxiliary information available to recover plaintext or key information. As brute force attack utilizes all possible trials exhaustively, it has high computing time complexity due to huge search space and hence is practically infeasible to mount on secure crypto algorithms. The Geffe generator is a non-linear binary key sequence generator. It consists of three linear feedback shift registers and a nonlinear combiner. In this paper, we attempt Geffe generator to find initial states of all three shift registers used. The initial states are the secret key bits that maintain the security of Geffe generator. To find secret key bits, one has to search huge key space exhaustively. We consider divide-and-conquer attack and genetic algorithm to reduce exhaustive searches significantly. Simulation results show that correct initial states of all shift registers can be obtained efficiently.