(Conditional) Cube Cryptanalysis Of Several Keccak-based Authenticated Encryption Ciphers

With the rapid development of the Internet technology,the information se-curity becomes more and more important.The Ministry of Education has set the "Cyber Security" as the primary discipline.Cryptography is the basement of information security,which plays an important role in Cyber Security.Symmet-ric key algorithm is an important part of cryptography,which consists of block ciphers,hash functions,Message Authentication Code and Authenticated En-cryption(AE)algorithms.KECCAK is the winner of the hash function standard SHA-3,which is organized by the U.S.National Institute of Standards and Tech-nology(NIST)and plays an important role in cryptography.The Authenticated Encryption(AE)algorithms could achieve message confidentiality and integrity simultaneously,and attract a lot of attentions of the worldwide cryptanalyst-s.The CAESAR competition aims to find secure AE algorithms standard.In this paper,we explore the security of KECCAK keyed modes and Authenticated Encryption cipher KEYAK?KETJE with(conditional)cube attack.The first at-tack is a conditional cube attack on RIVER KEYAK,the lightweight schemes of KEYAK,which is one of the 15 candidates of 3rd round CAESAR competition.We find a new set of conditional cube variable which has a much weaker diffusion and achieve 8-round key-recovery attacks on RIVER KEYAK for the first time.We also achieve 6/7-round key-recovery attacks and give the experimental verifica-tion.Those are the first attacks on round-reduced RIVER KEYAK.In the second part,we introduce a new MILP model and make the cube attacks better on the Keccak keyed modes,especially better on the KECCAK-MAC-512,which has a relatively smaller degrees of freedom(the capacity is relatively larger).Then we apply our MILP module on KECCAK-MAC,KEYAK and KETJE.More impres-sively,using this new tool,we give the very first 7-round key-recovery attack on Keccak-M AC-512.These two studies are both published on Designs,Codes and Cryptography(DCC).· Conditional Cube Attack on Round-Reduced River KeyakAE cipher KEYAK is designed by KECCAK team and submitted to CAESAR competition,which is based on the KECCAK-p permutation.It is one of the 15 candidates of 3rd round CAESAR competition and has five instances:RIVER KEYAK,LAKE KEYAK,SEA KEYAK,OCEAN KEYAK and LUNAR KEYAK.The RIVER KEYAK is the only lightweight,800-bit-state instance and the others all have 1600-bit state.Its key size is variable,with a minimum of 128 bits;its tag sizes is 128 bits long if not truncated and the capacity is set to 256 bits long when its security strength is 128 bits according to their security claims.Cube attack is a chosen IV key-recovery attack,which was introduced by Dinur and Shamir.Since then,cube attack was applied to many different cryptographic primitives.In Eurocrypt 2015,Dinur et al.presented a key-recovery cube-like at-tack on round-reduced Keccak-MAC and Lake Keyak using a divide-and-conquer method.Then Huang et al.proposed a new conditional cube attack on Keccak-MAC and Lake Keyak in Eurocrypt 2017.By inducing some bit conditions,they carefully select a new set of cube variables so that they do not multiply with each other in the first round as well as meet the condition that there is one variable does not multiply with other variables in the second round and then the degree over the cube variables is further reduced.In this paper,we give the first key-recovery attack on lightweight RIVER KEYAK corresponding to its integrity and authentication.Firstly,we find a new set of conditional cube variable which has a much weaker diffusion.Then we find some new sets of 16/32 cube variables for River Keyak,which meet the condition that they do not multiply with each other after the first round as well as meet the condition that one cube variable does not multiply with the others after the second round.This makes it possible to achieve 6/7-round key-recovery attacks onRIVER KEYAK.Secondly,we launch the 6/7-round conditional cube attack on RIVER KEYAK successfully with the time complexity 233 and 249,respectively.Our 6/7-round attacks are practical and we give the experimental verification.Finally,by applying linear structure technique,we find 64 cube variables(includ-ing the conditional cube variable)and extend the key-recovery attack on RIVER KEYAK to 8 rounds with the time complexity 281.Those are the first attacks on round-reduced RIVER KEYAK.· MILP-aided Cube-attack-like Cryptanalysis on Keccak Keyed ModesThe U.S.National Institute of Standards and Technology(NIST)announced a public contest in 2007 aiming at the selection of a new standard for a crypto-graphic hash function(SHA-3).After 5 years of intensive scrutiny,in 2012 NIST selected KECCAK as the winner of the SHA-3 competition.As one of the most important cryptographic standards,KECCAK attracts lots of attention from the world wide researchers and engineers,many cryptanalysis results and evaluation tools have been proposed.KECCAK use the sponge function,the(default)sponge function works on a 1600-bit state.For each n ? ?224,256,384,512},the sponge function KECCAK-n corresponds to parameters r(bitrate)and c = 2n(capac-ity)with r + c = 1600.The state will be initialize to be 0s and the message will be split into r-bit blocks.There are two phases in the KECCAK sponge function.In the absorbing phase,the r-bit message is XORed with first r-bit of the KECCAK state,then the KECCAK internal permutation is iterated for 24 rounds.After all the blocks are absorbed,in the squeezing phase,KECCAK-n will return the first r bits as the output of the function with internal permutation iteratively until the n-bit digest is produced.The KECCAK-MAC is the keyed modes of KECCAK.A secret key is concatenated with a message as the input of KECCAK-MAC.In EUROCRYPT 2015,Dinur et al.introduced a new cube-attack-like cryptanalysis technique and gave the 7-round key-recovery attack on KECCAK-MAC-256;In EUROCRYPT 2017,Huang et al.gave a 6-round key-recovery attack on KECCAK-MAC-384 while the attack on KECCAK-MAC-512 is only 5-round;In ASIACRYPT 2017,Li et al.improved Huang et al.'s attacks and extended the attacks one more round on KECCAK-MAC-384/512 respective-ly.While the key-recovery attack on KECCAK-MAC-512 is still limited compared with other parameters.Recently,cryptographic communities found many classical cryptanalysis meth-ods could be converted to mathematical optimization problems which aim to achieve the minimal or maximal value of an objective function under certain con-straints.Mixed-integer Linear Programming(MILP)is the most widely studied technique to solve these optimization problems,it uses the linear inequalities and linear equalities as the constraint conditions,and the objective function is optimized under the constraints with openly available software like Gurobi.In this paper,we introduce a new MILP model and make the cube attacks better on the Keccak keyed modes especially on KECCAKk-MAC-512.Using this new MILP tool,we give the very first 7-round key-recovery attack on Keccak-MAC-512,at the same time we apply our new tool on KECCAK-MAC,KEYAKk and KETJE,many results are the best results till now.When comparing with Huang et al.' s conditional cube attack,the MILP-aided cube-attack-like cryptanalysis have larger effective range and get the best results on the KECCAK keyed variants with relatively smaller degrees of freedom.