Basic Theories And Applications On Cryptanalytic Methods Of Block Ciphers

Block cipher is an important branch of cryptology. The brokenness of data encryptionstandard(DES)andthelaunchofadvancedencryptionstandard(AES)havegreatlypromotedboth the theories of design and analysis of block cipher. In recent years, from the ECRYPTproject of Europe to SHA-3 project of America, more and more stream ciphers and Hashfunctions were designed based on the idea of block cipher. The design theory of block ciphercomes mature gradually, which proposes more challenge of cryptanalysis. New cryptanaly-sis results can also promote the design theory. This thesis investigates several cryptanalyticmethods, including impossible differential cryptanalysis, related-key cryptanalysis, integralcryptanalysis, differential fault analysis and so on. By using these methods, we analyze Feis-tel cipher, Modified Lai-Messay cipher, SPN cipher etc. efficiently and get some new resultson cryptanalysis.In the first part, impossible differential cryptanalysis on Feistel cipher and modifiedLai-Messay cipher is studied. The main contents and fruits of this part are as follows:(1) Feistel ciphers with SP and SPS round functions are discussed, where the lineartransformation P is defined over F2n×n. The typical ciphers employing the two structuresare European standard Camellia and AES candidate E2. Known result shows that there arealways 5-round impossible differentials of a Feistel cipher with bijective round function. Byusing the method of"miss in the middle", we find some sufficient conditions for impossi-ble differentials of Feistel-SP ciphers with 6/7/8 rounds, i.e. any column of P⊕P?1 whoseHamming weight is greater than 1 corresponds to some 6-round impossible differentials forFeistel ciphers with SP round functions. The existence of some 7-round impossible differ-entials can be determined by counting the times that 1 appears at some special positions of PandP?1. Some8-roundimpossibledifferentialscanbefoundbycomputingtherankofsomesub-matrix of P. We also present two linear transformations, by employing which, Feistel-SP structure has no 8-round impossible differentials mentioned above. For Feistel cipherswith SPS round functions, by determining the rank of some sub-matrix of P, 6-round im-possible differentials can be found. These results tell us that when designing a Feistel cipherwith SP or SPS round function where the diffusion layer is selected from Fn2×n, the lin-ear transformation should be chosen carefully to make the cipher secure against impossible differential cryptanalysis.(2) For an AES candidate E2, a series of impossible differentials are discovered, whichimproves the former results by one round. We also evaluate the security of E2 against im-possible differential cryptanalysis. The results show that tweaked E2-128/192/256 reducedto 7 rounds and tweaked E2-256 reduced to 8 rounds are not immune to this cryptanalysis.(3) Impossible differential cryptanalysis on FOX, a block cipher with a modified Lai-Messay structure, is studied. Combining properties of the structure and diffusion layer, wepresent some 4-round impossible differentials, based on which we can perform attacks onFOX with reduced rounds and improve the former cryptanalysis results.In the second part, the thesis studies the security of block cipher under the related-keymodel. The main contents and fruits of this part are as follows:(1) We target an SPN cipher Crypton firstly. By analyzing the key schedule of Cryptonand diffusion layer, some 6-round related-key impossible differential distinguishers are con-structed, based on which we perform a 9-round attack on Crypton with 256 bits key for thefirst time. The attack can recover all the bytes of the 9th round key.(2) We aim to re-evaluate the security of HAS-160 in encryption mode—a block cipherwith 512 bits key size and 160 bits plaintext size. Previous attack was based on a 71-roundrelated-key distinguisher with a probability of 2?304. By investigating some delicate proper-tiesofHAS-160andusingabit-fixingtechnique,wepresenta72-roundrelated-keyrectangledistinguisher with a probability of 2?290. Two key recovery attacks on the encryption modeof the full 80-round HAS-160 are performed, which improve the former results.The third part discusses the construction of integral distinguisher, which is used forperforming integral attack. Firstly, by using Z'aba's idea of bit-pattern based integral, weconstruct a new 3-round distinguisher of Rijndael with 256 bit block length. Comparingwith the Square distinguisher which needs 256 chosen plaintexts, this new one only needs32 chosen plaintexts. Secondly, if we treat the ciphertext as the boolean function respectto plaintext bits, the integral distinguisher can be constructed or proved using the theory ofalgebraic degree. Take Rijndael and Present as examples, we unify byte-oriented integralmethod and bit-oriented integral method in a new way. Finally, we bounded the algebraicdegree of 6-round SMS4 structure, which turns out to be a bad degree.In the last part, we proposed differential fault attack on European standard algorithmSHACAL-2, which employs an unbalanced Feistel structure. By observing the iterate struc- ture, using word-oriented fault model, as well as combining the technique of differentialcryptanalysis, the subkey of SHACAL-2 can be recovered. PC simulation shows that, 8faulty ciphertexts can recover a 32-bit subkey on average, and 128 faulty ciphertexts areneeded to recover all the 512 bit keys if consider the key schedule. The attack indicates thatfaults on hardware greatly threat the security of SHACAL-2.