On The Structure And Security Of Block Ciphers

Block cipher is one of the central research directions in modern cryptography.Due to its fast speed of encryption and decryption,easy software/hardware implementations and standardization,block cipher has been widely applied in various fields where the security of information need to be protected,such as providing confidentiality for data,building other symmetric key cryptographic primitives,like message authentication codes,stream ciphers,hash functions and pseudorandom number generators.There have been a variety of block cipher algorithms in recent years,and some of them will be put into practical use.Therefore,it is more important to analyze their security.The design and cryptanalysis methods for block cipher are constantly improved with extensive research and the development of computer technology.The designers of a new block cipher usually investigate the ability of the cipher against the differential cryptanalysis and linear cryptanalysis during their design process,both of which were introduced to analyze DES.Most block ciphers are iterated ciphers,while the Markov cipher theory serves as an important basis for studying the ability of such ciphers to resist the cryptanalysis mentioned above.The impossible differential cryptanalysis,which has been applied to many block ciphers and obtained good results,is an extension of differential cryptanalysis.This thesis focuses on the research of impossible differential cryptanalysis and the Markov cipher theory.In the first aspect,as the existence of impossible differentials is the kernel of impossible differential cryptanalysis,we searched(or built)impossible differentials for ARIA block cipher and the MARS-like structure.In the second aspect,we evaluated two estimation methods for the second largest eigenvalue and discussed the applicability of the Markov cipher theory in the scene of using actual key schedule algorithms.Our major contributions are summarized as follows:1.We used the UID method to a block cipher with SPN structure for the first time.With some improvements on the general UID searching algorithm,we searched all possible pairs of plaintext difference and ciphertext difference and got 89 136 four-round impossible differentials in total,including all previous results.Furthermore,we proved that,with regard to ARIA,impossible differentials for more than four rounds cannot be found by the UID method.2.The MARS-like structure is a generalized Feistel structure based on the cryptographic core of MARS,in the round transformation of which one sub-block will affect all the others.For a specific kind of MARS-like structure that the outputs of the round function to be XORed to other sub-blocks are the same,we used the UID identity to describe the difference between the plaintexts,ciphertexts and intermediate states,and built impossible differentials.We showed that when the number of subblocks n is even,there always exist3n-1 rounds impossible differentials,while the structure has impossible differentials for any rounds when n is odd.The number is larger than previous results 2n-1 and 2n,moreover they did not distinguish the parity of the number of sub-blocks.3.The second largest eigenvalue of the probability transition matrix of a Markov cipher determines the convergence rate of the matrix and the number of iterations to resist differential cryptanalysis.For the computation complexity of the probability transition matrix and the computing algorithm for eigenvalues,it is not easy to compute the second largest eigenvalue of the probability transition matrix of an iterated cipher.We evaluated two inequalities for computing the upper bound of the second largest eigenvalue and compared them,using the probability transition matrix of IDEA(8),and looked into the corresponding number of iterations estimated with the upper bounds.The upper bounds computed by using the initial probability transition matrix were not of practical concern,while that computed by the matrix after several rounds of iteration were close to the actual value,and there were still some gaps.Considering that matrix multiplication is inevitable to compute transition matrices for more rounds,which will be progressively difficult,it is not feasible to use such estimation methods in iterated ciphers with larger block length.4.Block ciphers usually produce round keys from the main key by some key schedule algorithms,thus in most cases the assumption of the Markov cipher theory that the round keys are independent is not satisfied.By using the equivalence between Feistel structure and the iterated Even–Mansour scheme,we analyzed the key schedules in the Knudsen–Mathiassen experiment,and explained that the one in which the probability of differentials dose not decrease with iteration cannot be a “counterexample” of the theory.Because that key schedule dose not have effect,and the whole encryption procedure did not use any key actually.On the other hand,through further understanding of the dependency and distribution of the round keys in the other key schedules,we concluded that,even if the assumption of the round keys is not satisfied to some extent,the probability of differentials will still decrease with iteration,so Markov cipher theory still works.