Studies On Cryptanalytic Methods Of Block Ciphers And Their Applications

Block cipher is one of the most important branches in symmetric cryptology, and more and moreattentions are paid to that how to construct a secure block cipher. Although the AES and NESSIEprojects have selected their standards which have been studied in a wide range, people don't satisfywith the known results, they make efforts to evaluate these ciphers in different manners, for example,how to evaluate the security of block-cipher-based stream ciphers and hash functions.Impossible differentials are studied in this thesis, and we take CLEFIA and SNAKE as examplesto show how to find the impossible differentials in a cipher by using the meet-in-the-middle method.New 9-round impossible differentials of CLEFIA are found by analyzing the linear transformationcarefully, and by using the newly found impossible differentials, we can attack 12-round CLEFIAwith data complexity and time complexity being 2¹¹¹ and 2⁹⁰, respectively; 13-round CLEFIA withdata complexity and time complexity being 2¹¹² and 2158, respectively; 14-round CLEFIA with datacomplexity and time complexity being 2^112.3 and 2^248.5, respectively. By the same method, 9-roundimpossible differentials of SNAKE are found, by which we can attack 10/11/12-round SNAKE withdata complexities being 2⁴⁵, 2^45.5 and 2^46.5, respectively, and the time complexities are neglectable.These results imply that, when design a cipher, the linear transformations should be designed care-fully.Two block ciphers, Pigeon and Parrot, are proposed to show the basic theories of SQUAREattack. If the round function of a Feistel cipher is bijective, there exists a 4-round SQUARE distin-guisher by which we can recover the round key of the fifth round. However, it is invalid for Pigeon.Any guessed key, no matter it is the right one or not, can pass the balance-test. The main reason is thatthe algebraic degree of the round function is too low, which shows that the algebraic degree of roundfunction is a proper measurement for the existence of the SQUARE distinguisher. To date, most of theSQUARE distinguishers are found by experience, however, by using the algebraic method mentionedabove, we can find the SQUARE distinguisher in an algebraic way. To show the effectiveness of thealgebraic method, another block cipher, namely, Parrot, is designed. By experience, if there is onlya single active word in the input, every word of the output of the second round is balanced, and theproperty of the output of the third round can not be determined. However, when using the algebraicmethod, we found that, if there is only a single active word in the input, every word of the output ofthe second to the twelfth round is balanced, which is beyond the ability of experience. The relationsbetween SQUARE attack and other cryptanalytic methods are studied. We show that if a cipher is attackable by SQUARE attack, it is also attackable by the interpolation attack.The foundation of interpolation attack and integral attack are studied in an algebraic view, anda new kind of integral is proposed, namely, higher degree integral:Our result shows that, to compute the coefficients of a polynomial, we can use not only the Lagrangeinterpolation formula, but also the higher degree integrals in the hole space, by which we found therelation between interpolation attack and integral attack. Based on the new conception, the securityof ciphers with low algebraic degree is studied. By computing the coefficient of the second-leadingcoefficient, we improved the interpolation attack on PURE, and our result shows that PURE withno more than 22 rounds is breakable on a personal computer: 10-round PURE is breakable in a fewseconds and 22-round PURE in less than 150 hours. To the best of our knowledge, these results arethe best ones that can lead to real-world attacks against PURE.By using elementary number theory, we proved that when mod 4andα+ k≡C≡1 mod 2, f(x) =αx +β(x >>> b) +γ(x >> b) + C mod 2n is a sin-gle cycle invertible function, which can be used in the design of stream ciphers. To make the cyclelonger, we generalized the sample theorem in the stop-and-go sequence. Permutation polynomialover finite field is also studied, and a new kind of permutation is proposed: if s = 1, for anyδ∈F_2ⁿ,f(x) = (x^2k + x +δ)s + x³âˆˆF_2ⁿ[x] is a permutation polynomial; if s = 2^2n-1 + 1 andδ= 1,f(x) = (x^2k + x +δ)s + x³âˆˆF_2ⁿ[x] is a permutation polynomial, too. Properties of binomials arediscussed, it is pointed that, if b(x) = xu(xd - a)∈Fq[x](d|q - 1) is a permutation polynomial,there must existβ∈F-q such that , or equivalently, . At last,some relations between fixed-points of components and the security of a cipher are discussed. Wedefined a new value to measure the number of fixed-points, and among the permutations, a completepermutation has the least number of fixed-points. Furthermore, we show that if an n×n involutionalS box has no fixed-points, its algebraic degree can not exceed 2ⁿ - 3 while the best one is 2ⁿ - 2; foran n×n involutional linear transformation, the number of fixed-points is at least 2^2/n .