Research On New Conditional Cube Attack And Optimized Interpolation Attack

With the development of Internet technology,life is gradually digitized,and a large number of data need to be transmitted through the Internet.The issue of information security on the network is increasingly paid attention to,and cryp-tography,as a core technical support to guarantee information security,has an increasingly important position.Modern cryptography is generally divided into two categories:symmetric cryptography and asymmetric cryptography.Sym-metric cryptography is widely used in various industries because of its advan-tages such as fast encryption and decryption speed and suitable for hardware and software implementation.Symmetric cryptography algorithm is subdivid-ed into block cipher,hash function,stream cipher,message authentication code(MAC)and authentication encryption algorithm according to the structure.Au-thentication encryption algorithm can not only guarantee the confidentiality of information but also realize the authentication of message,so it has attracted more and more attention.There's a lot of analysis of it.At the same time,with the booming development of the Internet of Things(IoT),the security problem of the Internet of Things devices is also becoming increasingly prominent.Due to the limitation of the resources of the devices,many large-state cryptographic algorithms cannot be deployed,but lightweight cryptographic algorithms can do it.Therefore,the lightweight authentication encryption algorithm has become very popular in recent years.In this paper,based on the new conditional cube attack,several lightweight authentication encryption algorithms arc analyzed.Moreover,we present the analysis of FARFALLE pseudo-random function(PRF)based on the optimized interpolation attack.In the research of lightweight au-thentication encryption algorithms KETJE JR,XOODOO-AE and XOODYAK,we propose a new model to control variable diffusion by using mixed integer linear programming(MILP)and combining with the characteristics of small state cipher algorithm.At the same time,we strictly control the diffusion of the conditional cube variable in the first round and reduce the consumption of the conditional cube variable to the degree of freedom.As a result,the complexity of the al-gorithm analysis is reduced,and the attack can be implemented on a personal computer.ELEPHANT is the final round participant of the National Institute of Standards and Technology(NIST)lightweight cryptography project.In this paper,combining the interpolation attack and the MOEBIUS Transform,we give the key recovery attack on the round reduced ELEPHANT-DELIRIUM.Besides,we adapt this method to the FARFALLE PRF structure,and give the key recovery attack on KRAVATTE and XOOFFF,which are the FARFALLE instances.·New Conditional Cube Attack on Round-Reduced Ketje Jr,Xoodoo-AE And XoodyakKETJE,designed by the KECCAK team,is one of 15 participants of the third round CAESAR competition,which is short for Competition for Authenticated Encryption:Security,Applicability,and Robustness.There are multiple versions of KETJE.The lightweight algorithm KETJE JR(v1&v2)use 200 bits state size KECCAK-p permutation.The internal state is small and the diffusion is good.Dacmcn ct al.introduce a new XOODOO permutation at FSE 2018.It can be used in KETJE structure as a new authentication encryption algorithm named XOODOO-AE.At the same time,Daemen et al.give a original instance named XOODYAK,which was submitted to the final round of NIST lightweight cryptography project.In EUROCRYPT 2017,Huang et al.introduce the conditional cube attack.By adding key bit conditions,the diffusion of the conditional cube variable is controlled so that the conditional cube variable does not multiply in the first two rounds.Then search for ordinary cubic variables that satisfy the following conditions:not multiplied in the first round,not multiplied by a conditional cubic variable in the second round.Under these conditions,if the key is right,there is no item with algebraic degree greater than two.In FSE 2020,Li et al.proposed new conditional cube attacks on KECCAK keyed modes,which allow only two variables to be multiplied in the first round,and make sure that no other variables are multiplied by it in the second round.In Huang et al.'s attack,it requires that,in the first round,all the cube variables are not multiplied with each other.However,Li et al.relaxed this constraint by introducing the so-called kernel quadratic term.By adding bit conditions,the kernel quadratic term satisfy the 6-2-2 diffusion model.This improvement reduces the restriction conditions on ordinary cubic variables,increases the search space,and can obtain more ordinary cube variables in the algorithm with low degree of freedom.However,when this method is applied to the algorithm of small state,the number of ordinary cubic variables is insufficient.In this paper,we introduce a new diffusion model for kernel quadratic term,i.e.8-2-2 model.This mode can not only control the kernel quadratic term in the second round of ? operation does not diffuse,but also has a better constraint on the diffusion of the two cube variables of the kernel quadratic term.The results indicate that it will lead to more freedom degrees to search ordinary cube variables.Under the new diffusion control model,we apply the key recovery attacks to KETJE JR v1 and v2 whose initialization process is reduced to 5 rounds.The time complexities reduce from 238.86 and 234.91 to 226.6 and 227.5 respectively.As for the artificial algorithm XOODOO-AE,we give the practical key recovery attack on 6-round initialization of it,whose time complexity is 240.5.Moreover,the time complexities of the key recovery attack on 6-round XOODYAK is 243.8.All the attacks are practically implemented.·Optimized Interpolation Attacks on Round-Reduced Elephant,Kravatte And XoofffELEPHANT is one of the participants of the NIST lightweight cryptography project.It has three permutation structures,and the ELEPHANT-DELIRIUM version use KECCAK-p as its internal permutation.It is suitable for algebraic analysis.KRAVATTE and XOOFFF are two instances of FARFALLE pseudoran-dom function but use different permutations.In addition,FARFALLE was first introduced by Bcrtoni et al.in FSE 2018.It takes as input a key and a(sequence of)string(s),and produces an arbitrary-length output.It is efficient because its permutation calls can be performed in parallel as soon as the input masks have been generated.The interpolation attack was first introduced by Jakobsen and Knudsen on block ciphers with low algebraic degree in 1997,which is related to high-order differential cryptanalysis proposed by Lai.This method takes the process of en-cryption and decryption as a equation,and the key information can be obtained by solving the the equation system.In ASIACRYPT 2015,Dinur et al.in-troduce the optimized interpolation attack,which can reduce the complexity of interpolation attack.In this paper,we analyze the structure of the KECCAK and XOODOO inverse permutations and give the properties of them.These properties can be used to get the expression of the intermediate state of the algorithm.Besides,we construct an affine space in the Acc of FARFALLE so that the optimized interpolation attack can be applied to KRAVATTE and XOOFFF.For KRAVATTE ACHOUFFE-{6,6,4,4},the time complexity of the attack is 2106-2.As for XOOFFF-{6,6,4,4},it is 290.4.Moreover,the time complexity for the optimized interpolation attack on 8-round ELEPHANT-DELIRIUM is 298.3.