A Study Of Problems In Higher Order Differential Cryptanalysis

Higher order differential attack generalizes differential analysis and is a special case of integral attack.Because of simple attack process and strong attack capability,it is widely used in the field of block cipher cryptanalysis.In 1994,X.Lai first proposed the notion of higher order differential in cryptanalysis,which elaborated some basic properties of higher order derivative of boolean function,and extended the idea of differential attack to the higher order differential attack,so as to effectively utilize cryptographic properties of multiple differential pairs.In 1997,R.Knudsen and T.Jakobsen first used the higher order differential idea on specific cryptographic algorithm analysis and used 2⁹plaintexts and 2⁴²time complexity to recover the last key of 6 rounds KN cipher.Since then,higher order differential attack is widely used in block cipher analysis.Square attack,Saturation attack and Multiset attacks are successively proposed.In 2002,R.Knudsen summed up the core idea of these attacks,proposed the integral attack,and further developed the higher order differential thought.In 2007,scholar M.Vielhaber analyzed the stream cipher Trivium and proposed the AIDA attack.Then,in Crypt2008,I.Dinur and A.Shamir use Cube attack to make further cryptanalysis on Trivium.In 2015,the Japanese scholar Y.Todo formalized the integral feature,proposed the concept of division property,can be more effective to find the optimal integral distinguisher.In essence,the above cryptanalysis methods are based on the idea of higher order differential.The higher order differential attack is summed on any subspace,while integral attack,AIDA attack and integral attack are obtained in a certain subspace.Through the restriction of subspace selection,we can find the better attacking equation group and accelerate online attack phase.In the course of the development of the higher order difference thought,there are still many problems worthy of further study.We first start with the cryptographic properties of Boolean functions,and then combine the specific cryptographic algorithms to study problems in higher order differential attacks.The following results are obtained:1.We study higher order derivatives of Boolean functions and get some interesting prop-erties:the set of i-DP?i-differential point?is a closed to the XOR operation on F₂ⁿ;when the Boolean function f has an i-DP,The original i-DP still exists after taking a derivative on the boolean function at a non-2-DP point.In addition,an n-variable nonlinear Boolean function of degree d has at most 2^n-d-1 2-DPs.By constructing the related higher order differential dis-tinguishers and computing the adversarial advantage of the respective distinguishers,we know that an n-bit block cipher whose n component functions have common terns of degree n-1 and an n-bit cipher with low degree d are not IND-CPA security.It also provides some meaningful design criteria for the design of round function.In order to resist the higher order differential attack,a block cipher should have as many component functions with maximum degree n-1as possible,and as few component functions with common terms of degree n-1 as possible.2.We revisit the previous higher order differential attack on the CAST-128 structure,ac-cording to low degree of round function to obtain the equations of the round key,round keys can be obtained by solving the corresponding equations.In this attack,in addition to the monomial on the key,there is a large number of redundant polynomials,which costs some time.Based on this,we have applied the basic interpolation attack and optimized interpolation attack.In the basic interpolation attack,the corresponding polynomial coefficients are obtained by solving the attack equations.Obviously,it does not get any information about the key.By using the method of variable transformation,the polynomials of high degree about plaintext are trans-formed into the polynomial of low degree about the key,which reduces time complexity from2^37.7bit operations to 2^31.4without significantly increasing the data complexity.Similarly,we can get the attack on 16-round CAST-128-like structure,which requires 2³¹chosen plaintexts,2^44.2bit operations to recover the last round keys.3.We do a further research on low-degree Feistel block cipher.The theorem of related literatureis has some restrictions,and the cipher PURE meets these conditions,so as to obtain a better attack.With the continuous development of modern cryptography,cryptographers in the design of cryptgrophy will make more thorough consideration,it is difficult to meet such restrictions:the algebraic sdegree of the round function is odd,the second term of the high coefficient is 0.We combine the CAST-128 structure and several variants to do the related cryptanalysis.Largrange interpolation is used to obtain coefficient of second highest term,and then the interpolation-integral attack is used to attack these toy ciphers.Comparing the attack result,we get that the degree of round function is not as higher as better,considering a variety of factors and giving an appropriate integer,while the degree is preferably even.