Techniques For Cryptanalysis Based On Higher Order Differentials

Higher order differential cryptanalysis is a higher order generalization of differ-ential cryptanalysis and a special case of integral cryptanalysis. Differential cryptanal-ysis considers the distribution of a pair of differential between plaintext and ciphertextin iterated cipher, while higher order differential cryptanalysis and integral cryptanal-ysis uses the cryptographic properties of pairs of differentials. The difference betweenhigher order differential cryptanalysis and integral cryptanalysis is that the former usespairs of chosen plaintexts from a linear subspace with a fixed XOR difference and thelatter has not strict requirement on the set of chosen plaintexts, the former is universal,while the latter depend on the structure of the iterated cipher.Higher order differential was firstly introduced into cryptography by Lai in1994.He introduced the basic properties of higher order differential of discrete function andgeneralized the original differential cryptanalysis to higher order differential crypt-analysis. The first practical higher order differential attack on specific cryptographicalgorithm was proposed by Jakobsen and Knuden in1997. Since then, higher orderdifferential cryptanalysis is applied in cryptanalysis of many cryptographic algorithmsas a very effective method. After constant practice and conclusion, Knudsen extend-ed the idea of higher order differential cryptanalysis to integral cryptanalysis in2001.Vielhaber proposed AIDA from the cryptanalysis of stream cipher Trivium in2007, Inthe following2008, Shamir introduced Cube attack in a report of Crypto2008. Theseinventions once again attracted the attention of the cryptographic group to higher or-der differential cryptanalysis. AIDA and Cube attack is similar, the former is admittedby Shamir to be a pioneer of the latter while the latter is believed by Vielhaber thatits improvement is not enough to rename this attack. Moreover, Bernstein thinks thatthe latter is the re-discovery of the higher order differential attack. These findings and disputes show that there are many problems worthy of further study in higher orderdifferential. Starting from theoretical and practical, we deeply study the techniquesof cryptanalysis based on the higher order differentials and mainly get the followingresults.1、We show that the previous higher order differential related attacks, higher or-der differential attack(HODA), algebraic IV differential attack(AIDA), Cube Attack,Cube Tester and bitwise higher order differential attack(BHODA), are all theoretical-ly based on the properties of higher order derivatives of Boolean functions, whichcan deepen the understanding of the attacks. Then we propose a general higher or-der differential cryptanalysis framework based on higher order derivatives of Booleanfunctions including the above attacks. Note that higher order differential cryptanaly-sis is based on the property of higher order derivatives of Boolean functions that thedegree of a Boolean function can be reduced by at least1by taking a derivative onthe function at any point. A quicker reduction on the degree of the derivatives meansa lower data complexity. We define fast point as the point at which the degree canbe reduced by at least2. Inspiring from the cryptanalysis framework, we focus onthe sufficient and necessary conditions of some special derivative points to be fastpoints and compute their probability, these results are valuable references for higherorder differential cryptanalysis. We also introduce a practical higher order differentialcryptanalysis technique and an algorithm based on it, additionally.2、We give a relatively complete and regular summarization of the propertiesabout fast points for Boolean functions. We show that the fast points of a n-variableBoolean function form a linear subspace and its dimension plus the algebraic degreeof the function is at most n. We also show that non-zero fast point exists in everyn-variable Boolean function of degree n1, every symmetric Boolean function ofdegree d where n≡d (mod2) and every quadratic Boolean function of odd numbervariables. Moreover we show the property of fast points for n-variable Boolean func-tions of degree n2and also discuss them in the others Boolean functions. Theseproperties are supplementary to the basic ones of the higher order derivatives of theBoolean function.3、We show that having maximum degree is not the sufficient condition to resist higher order differential distinguishing attack. We prove that a n-bit block cipherwith optimized degree n1can be distinguished with significant advantage and datacomplexity2n1if either more than half of the component functions have degree lessthan n1or more than half of the component functions have common monomials ofdegree n1. With the above discussion, we propose a new design principle that theprobability distribution of the degrees of the output component functions should beindistinguishable from the one of a uniformly distributed random permutation. Morepractical considering, a block cipher should better have as many component functionswith maximum degree n1as possible, and as few component functions with commonmonomials of degree n1as possible. The results can be generalized to symmetriccryptographic primitives which can be seen as a collection of cryptographic Booleanfunctions. Although the new design principle seems usefulness, it is the first one basedon the degree.4、Keccak is a family of cryptographic sponge functions and is one of the fivehash functions selected for the third (and final) round of the SHA-3competition. Itscore component is a permutation named Keccak-f, which is composed of several iter-ations of five transformations. We study the properties of the inverse of the nonlineartransformation in Keccak-f, and observe that the algebraic degree of the product of anytwo output coordinates of this inverse is2less than its size. This enables us constructa zero-sum partition for the Keccak-f permutation with full24rounds of size21575,which is lower than the previous best result21590.