Combined and General Methodologies of Key Space Partition for the Cryptanalysis of Block Ciphers

This paper proposes two new methods of key space partitioning for the cryptanalysis of block ciphers. The first one is called combined methodology of key space partition (CoMeKSPar), which allows us to simultaneously set some of the first and last consecutive bits of the key. In this way, the search is performed using the remaining middle bits. CoMeKSPar is a combination of two methods already proposed in the scientific literature, the Borges, Borges, Monier (BBM) and the Tito, Borges, Borges (TBB). The second method is called the general algorithm of key space reduction (GAKSRed), which makes it possible to perform a genetic algorithm search in the space formed by the unknown bits of the key, regardless of their distribution in the binary block. Furthermore, a method of attacking block ciphers is presented for the case where some key bits are known; the basic idea is to deduce some of the remaining bits of the block. An advantage of these methods is that they allow parallel computing, which allows simultaneous searches in different sub-blocks of key bits, thereby increasing the probability of success. The experiments are performed with the KLEIN (Small) lightweight block cipher using the genetic algorithm.