Research On The Security Of Evolutionary Block Cipher

Cryptology is one of the most important techniques in information security, which provides an abundance of services including privacy, data integrity, availability and non-repudiation. The high level of security, efficiency and ease of implementation of a cryptosystem are the long-term design aims of cryptographers. Intuitively, frequent replacement of the key probably strengthens the security of a cryptosystem. More gen-erally, if the key is truly random, as large as or greater than the plaintext, never reused in whole or part, and kept secret, the cryptosystem will be the well-known "one-time pad" with the perfect secrecy property, which has been mathematically proven to be uncrackable. In the one-time pad, the encrypted message provides no information about the original message to a cryptanalyst no matter how much encrypted message and com-puting resource he possesses. Nevertheless, the practical restriction and inconvenience of the key creation and management have meant that the one-time pad is, in practice, little-used.In the last15years, intelligent algorithms such as evolutionary computing, simu-lated annealing, hill-climbing algorithm have been widely and successfully used in the design of cryptographically strong single/multi-output Boolean functions. Inspired by the fact that frequent replacement of the key contributes to a cryptosystem’s high se-curity level and the gradual mature of intelligent computing algorithms, Prof. Zhang proposed the concept of evolutionary cryptography and an evolutionary method for S-boxes in DES-like ciphers, which are more robust than the original ones against linear and differential cryptanalysis. Thereafter, Clark introduced a simulated annealing al-gorithm to generate highly nonlinear and lowly self-correlated S-boxes, and Laskari, et al studied the particle swarm optimization algorithm on the evolutionary design of the S-boxes. Prof. Feng showed how to make use of evolutionary algorithm to improve the nonlinearity of the involution S-boxes. In his doctoral dissertation, Tong systematically studied the heuristic search in the design of highly nonlinear orthormorphisms in detail.Taking the design complexity into account, researchers both domestic and abroad have been concentrating the evolutionary design on some units and components in a cryptosystem. Those units and components are filtered by a fitness function with some cryptographical criteria. significantly improved or maintained at a fairly high security level. From the viewpoint of the security. they sufficiently met the requirements of the application of cryptography at that time. As an important complement to the evolutionary cryptography, the research on the security of the evolutionary cryptosystem both examines the security strength of the system and provides a theoretical foundation for the evolving stratege of the evolutionary cryptosystcms. However, two issues in the study of the security of evolutionary cryptosystems remain unresolved:theoretical analysis of the security of an evolutionary cryptosystem and quantitative examination of the contribution on the security of the whole cryptosystem when some core components and units evolve in the system.Linear and differential cryptanalyses are two of most effect statistical attack ap-proaches on iterated block ciphers, and they have been used as basic tools and standards in evaluating the security of block ciphers. This thesis investigates the security of an evolutionary block cipher against the linear and differential cryptanalysis in depth and exploits the effect of the number of evolving times on the the data complexity, time com-plexity and the success rate. First and foremost, it briefly describes the basic framework of statistical cryptanalysis, thoroughly develops the theoretical foundation of the statis-tical cryptanalysis, especially the process of the key recovery—the log-likelihood ratio (LLR) statistic and χ2statistic, hypothesis testing and the theory of order statistics. Following the introduction on statistical cryptanalysis, the thesis exploits the security of an evolutionary block cipher against the linear cryptanalysis and multidimensional linear cryptanalysis in Chapter3. In this chapter, the thesis first examines the rela-tionship of the data complexity, time complexity, linear bias and the success rate in the (one-dimensional) linear cryptanalysis Algorithm2, and then compares the security levels of an evolutionary block cipher and a fixed block cipher against Algorithm2. Thereafter, starting from the vectorial Boolean functions, the thesis presented a unified methodology for using multiple linear approximations in distinguishing and key recov-cry attacks for Algorithms1and2, which is on basis of the logarithmic likelihood ratio (LLR) statistic. Further, the relationship of the data complexity, time complexity, the capacity of the probability distribution of linear approximations and the success rate in the proposed multidimensional linear cryptanalysis is studied, and this relationship is utilized to compare the data and time complexities in the multidimensional linear cryptanalysis against an evolutionary block cipher and a fixed block cipher.The fourth chapter of this thesis is dedicated to the exploration on the security of an evolutionary block cipher against the differential cryptanalysis and multiple differ-ential cryptanalysis. This chapter proceeds along the same line as Chapter3. First it examines the relationship of the data complexity, time complexity, the best differential probability and the success rate in differential cryptanalysis and compare the data and time complexities of the differential cryptanalysis against an evolutionary block cipher and a fixed block cipher, then it introduces a methodology based on χ2statistic for using multiple differential characteristic in distinguishing and key recovery attacks. Finally, the relationship of the data complexity, time complexity, the capacity of the probability distribution of differential characteristics and the success rate in the multiple differential cryptanalysis is studied, and the data and time complexities in the multiple differential cryptanalysis against an evolutionary block cipher and a fixed block cipher are com-pared.In the end of this thesis, an evolutionary block cipher originating from the lightweight block cipher PRESEXT is given, and the effects of the number of evolving time on the data complexity, time complexity and success rate of all the above attack approaches against this cipher are comprehensively examined and demonstrated. As indicated in the figures throughout this chapter, it can be concluded that evolving on the core S-box is an effective measure to strengthen the security of the lightweight block cipher PRESENT.