More Accurate Detection Algorithms For Integral Properties Of Symmetric Encryption Primitives

The modern cryptography studies the secure transmission and storage of the message from the sender to the recipient,whose core is the cryptographic design and analysis.Design and analysis arc two contradictory but unified aspects,the design provides the materials for the analysis,whereas the analysis is the pre-requisites of designing more secure primitives.According to whether the sender and the recipient use the same key,cryptographic primitives are divided into two categories,one is the asymmetric ciphers(aka.public-key ciphers)and the symmetric ciphers(aka.private-key ciphers).Comparing to the asymmetric ci-phers,the symmetric ones are suitable to encrypting massive data for its high efficiency.Consequently,most encrypted data in the network transmission and the computer storage are from the symmetric ciphers.A secure symmetric cryptographic algorithm needs to be able to resist all currently known analysis methods,such as differential analysis,linear analysis,integral analysis,and so on.The research in this paper is the analysis method of symmetric cipher algorithm,and the main focus is how to perform integral-like analysis on block cipher and stream cipher algorithm.The mostimportant step of integral analysis is to detect the integral distinguisher.This article studies the latest developments in the method of using zero-correlation linear analysis and division properties to detect the integral distinguisher.The main contents include:1.A new method of converting from a zero-correlation linear characteristic to an integral property is studied,and the current optimal integral distin-guisher for 5-round advanced encryption standard(Advanced Encryption Standard,AES)is given.At CRYPTO 2016,Sun ct al.conversed a 5-round linear hull with the zero correlation to a 5-round integral distinguisher for 5-round AES.This distinguisher requires 2128 chosen ciphertexts and the timc complexity is thcn 2128 5-round AES decryptions.In this thesis,wc took the same 5-round zero-correlation linear hull,but under the chosen-plaintext settings,with the relationship between the zero-correlation linear hulls and the integral distinguisher,we manage to construct a new integral distinguisher for 5-round AES.Our new distinguisher utilizes the property that only two bytes are with the non-zero masks and the two masks are equal.From this property,we know that the XOR value of the two bytes has the ALL property,so the number of times each value appears is just 1/256 of all the chosen plaintexts.We then take the property that the Sbox can keep the zero difference,we prove that the number of ciphertexts of the 5-round AES whose XOR value of two specific bytes is one specific value is strictly 288.For a randomly-chosen permutation.however,this probability is only 2-40.7.According to this gap,we can distinguish the 5-round AES from a randomly-chose permutation.Our new distinguisher consumes 296 chosen plaintexts,which is the best integral-like distinguisher on AES.2.We improve the current automatic model of division properties to detect integral characteristics,give an efficient and general SMT model that de-scribes the two-subset bit-based division properties propagation of complex linear layers.The division properties are the most efficient methods of de-tecting the integral distinguishers.To enhance the efficiency of searching for division propcrtics,the Mixed Intcgral Linear Programming(MILP)tools are introduced into the filed of division properties.With the MILP models,the integral results of lots of ciphers are improved.In order to construct the models,wc first need to build the MILP models for each ci-pher component.Currently,some operations such as XOR,AND,COPY,Sbox and addition have been modeled in property ways,whereas for the linear layer,we do not have the perfect models.Among the two methods in the literature,one decomposes the linear layer to the basic operations of XORand COPY,then we can construct the models based on the models of the smaller operations;the other takes advantage of the relationship be-tween the inverse sub-matrices and the valid division trials and construct the one-to-one mapping.Although this method is precious,it is not friendly to the automated tools.The only automated models are only suitable to the binary matrices.In this thesis,wc propose a new precious and general model for this problem,with which we can re-perform the 5-round integral distinguisher for AES,give the longest integral distinguisher for LED and obtain the best two-subset division properties of MISTY1,CLEFIA and so on.3.We propose a variant three-subset bit-based division property and use them to improve the integral analysis of SIMON,KATAN/KATANTAN and so on.The three-subset bit-based division property is more precious than the two-subset bit-based division property,and can find more bits with inte-gral property.However,in the search process of the three-subset bit-based division property,the duplicated vectors should be canceled,which violates the principle of the automated tools.To further capture the properties of the algorithms,we introduce a variant of the three-subset bit-based divi-sion property.In this model,we do not cancel the duplicated vectors and strictly prove that the results of this kind of search model are always cor-rect.With this variant model,we can give the better results for SIMON,KATAN/KATANTAN and so on.4.From the perspective of whether a certain monomial in the polynomial ap-pears or not,a monomial prediction technique is proposed,and the most accurate theoretical model for detecting integral distinguishers is given.The monomial prediction technique is used to study the algebraic degree estima-tion and cube attack related to integral analysis.Inspired by the division property,we find that whether a monomial appears in the final polyno-mial can be determined by the the number of so-called monomial trails and we give the strict proof for it.Through studying whether the key-related monomials appear or does not appear in the polynomial of ciphertext bits,we can accurately determine the integral properties of the ciphertext bits.As a result,the existence of the integral property can be accurately judged.After that,we study the relationship between the division properties and the monomial prediction,prove that the word-based division properties,two-subset bit-based division properties and three-subset bit-based division properties arc all no-falsc-alarm approximations of the monomial predic-tion.We use the monomial prediction technique to give the latest research on the degree estimation and cube attack related to the concept of integral analysis,giving the accurate algebraic degree for 834-round TRIVIUM We also give the optimal key-recovery attacks for 840-,841-,and 842-round TRIVIUM.