New Conditional Cube Attacks On Sponge(-Like)Cryptographic Algorithms

The rapid development of information technology,especially the Internet,has made the relationship between individuals closer,and information security has become increasingly prominent.Cryptography is one cornerstone of information security.The cryptographic algorithms can be divided into symmetric primi-tives and asymmetric primitives.Symmetric primitives include block ciphers,stream ciphers,hash functions,MAC(message authentication code),authenti-cated encryption schemes,and the like.For SPONGE constructions,the size of the internal state is fixed,while the length of the input is variable.Recent-ly.SPONGE constructions are widely used to design hash functions.MAC and authenticated encryption schemes.The cube attack was first proposed by Din-ur and Shamir at EUROCRYPT 2009.The symmetric encryption algorithm is considered as a polynomial system,and the maxterm is the product of several public variables.The attacker can recover the value of the key bit by utiliz-ing the maxterm.Then Huang et al.proposed the conditional cube attack for the first time at EUROCRYPT 2017.By assigning bit conditions,the diffusion of a conditional cube variable is reduced.This paper presents new conditional cube attacks for several SPONGE(-like)cryptographic algorithms.In the study of authenticated encryption ASCON.one winner of CAESAR competition,the generalized conditional cube attack was established.A partial common factor is proposed for the algebraic expression,and the bit conditions are constructed ac-cording to each common factor,and then the according cube attack is obtained.We perform key-recovery attacks on 5/6/7-round initialization of ASCON.and the time complexities are 224,240,2103.92,respectively.7-round theoretical at-tack and 6-round practical attack are the best results of cryptanalysis so far.In the research of KECCAK,we use the MILP(Mixed-integer Linear Programming)method to enrich the automated cryptanalysis tool of KECCAK:propose a new mode of controlling the diffusion of conditional cube variable,exactly move the control from the first round to the second round.Those expand the rounds of attacks,also greatly reduces the cryptanalysis difficulty of KECCAK.The series of cryptanalysis results include key-recovery attacks on reduced versions of cryp-tographic primitives such as KMAC256(NIST standard),KECCAK-MAC-384/-512,and KETJE(one of the third round survivors in CAESAR competition).? Conditional Cube Attack on Round-Reduced Ascon:from Key Subspace to the Whole Key SpaceASCON submitted by Dobraunig et al.is one winner of CAESAR competition.The cube-like method is first used by Dinur et al.to analyze KECCAK keyed modes,and the cube variables do not multiply with each other in the first round.In CT-RSA 2015.Dobraunig et al.applied this method to 5/6-round ASCON,whose structure is similar to KECCAK keyed modes.However,for ASCON the non-linear layer is more complex and the state is much smaller,which makes it hard for the attackers to select enough cube variables that do not multiply with each other in the first round.This seems to be the reason why the best previous key-recovery attack is on 6-round ASCON,while for KECCAK keyed modes(KECCAK-MAC and KEYAK)the attacked round is no less than 7-round.In this paper,we generalize the conditional cube attack proposed by Huang et al,and find new cubes depending on some key bit conditions for 5/6-round reduced ASCON,and translate the previous theoretic 6-round attack with 266 time complexity to a practical one with 240 time complexity.Moreover,we propose the first 7-round key-recovery attack on ASCON.By introducing the cube-like key-subset technique,we divide the full key space into many subsets according to different key conditions.For each key subset,we launch the cube tester to determine if the key falls into it.Finally,we recover the full key space by testing all the key subsets.The total time complexity is about 2103.9.In addition,for a weak-key subset,whose size is 2117,the attack is more efficient and costs only 277 time complexity.?Improved Conditional Cube Attacks on Keccak Keyed Modes with MILP MethodKECCAK is a family of SPONGE functions.It.has 7 permutations with differ-ent sizes of internal states.NIST published the new standard of hash functions SHA-3 which is based on KECCAK.The conditional cube attack is an efficient key-recovery attack on KECCAK keyed modes proposed by Huang et al.at EU-ROCRYPT 2017.By assigning bit conditions,the diffusion of a conditional cube variable is reduced.Then,using a greedy algorithm(Algorithm 4 in Huang et al.'s paper),Huang et al.find some ordinary cube variables,that do not multiply together in the first round and do not multiply with the conditional cube variable in the second round.Then the key-recovery attack is launched.The key part of the conditional cube attack is to find enough ordinary cube variables.Note that,the greedy algorithm given by Hua.ng et al.adds ordinary cube variable without considering its bad effect,i.e.the new ordinary cube variable may result in that many other variables could not be selected as ordinary cube variable(they multiply with the new ordinary cube variable in the first round).In this paper,we bring out a new MIILP model to solve the above problem.We show how to model the reduced diffusion of cube variables and model the way that the ordinary cube variables do not multiply together in the first round as well as do not multiply with the conditional cube variable in the second round.Based on these modeling strategies,a series of linear inequalities are given to restrict the way to add an ordinary cube variable.Then,by choosing the objective function of the maximal number of ordinary cube variables,we convert Huang et al's greedy algorithm into an MILP problem and the maximal ordinary cube variables are found.Using this new MILP tool,we improve Huang et al.'s key-recovery attacks on reduced-round KECCAK-MAC-384 and KECCAK-MAC-512 by 1 round,get the first 7-round and 6-round key-recovery attacks,respectively.For KETJE MAJOR with 1600-bit state size,and we conclude that when the nonce is no less than 704 bits,a 7-round key-recovery attack could be achieved.In addition,for KETJE MINOR with 800-bit state size and we use conditional cube variable with 6-6-6 pattern to launch 7-round key-recovery attacks.At A SIACRYPT 2018.Song et al.proposed an improved model of the MILP method.The new model reduced the time complexity of key-recovery attacks on 6-round KECCAK-MAC-512.However,for some KECCAK based versions with very few degrees of freedom,one could not find enough ordinary cube variables,which weakens or even inval-idates the conditional cube attack.In this paper,a new conditional cube attack on KECCAK is proposed.We remove the limitation that any cube variables could not multiply with each other in the first round.As a result,some quadratic terms may appear in the first round.We make use of some new bit conditions to pre-vent the quadratic terms from multiplying with other cube variables in the second round,so that there will be no cubic terms in the second round.Furthermore,we introduce the kernel quadratic term and construct 6-2-2 pattern to reduce the diffusion of quadratic terms significantly,where ? operation even in the second round becomes an identity transformation for the kernel quadratic term.There-fore,more degrees of freedom are available for ordinary cube variables and fewer bit conditions are used to remove the cubic terms in the second round,which plays a key role in the conditional cube attack on versions with very few degrees of freedom.We also use MILP method in the search of cube variables and give the key-recovery attacks on round-reduced KECCAK keyed modes.As a result,we reduce the time complexity of key-recovery attacks on 7-round KECCAK-MAC-512,7-round KETJE SR v2 from 2111,299 to 272,277,respective-ly.Additionally,we have reduced the time complexity of attacks on 9-round KMAC256,7-round KETJE SR vl.Focusing on the conditional cube attack,we have improved the attack on both round-reduced KECCAK-MAC-512 and KEETJE SR v2 by one round.Besides,practical attacks on 6-round KETJE SR v1 and v2 are given.