Cryptanalysis Of Authenticated Ciphers

In the information age,the high popularity of the Internet makes sensiive data such as politics,economy,finance and personal privacy face the threat of disclosure.The security of network data is closely related to everyones vital interest.Data confidentiality and authenticity are two very urgent and severe problems when guaranteeing network security,and they are core goals of infor-mation security.Authenticated encryption(AE)scheme is the key technology to achieve such security goals.In January 201:3.the NIST funded CAESAR(Competition for Authenticated Encryption:Security.Applicability,and Robustness)competition was launched to identify suitable for widely adopted AE schemes as better alternatives to cur-rent options such as AES-GCM.The competition announced 7 finalists in March 2018.with six of finalists selected into the fmal portfolio in February 2019.Dur-ing AE schemes collecting and screening of CAESAR competition,analyzing the security of the submissions is of great importance to enable the committee to judge them adequately.We adopt several cryptographic techniques to analyze the security of candidates to CAESAR competition.including MORUS.ASCON and PRIMATEs,which accelerates the competition to some extent.MORUS is an authenticated cipher as one of the finalists of CAESAR compe-tition.In the submission document,the designers initially evaluated the security of MORUS,especially on the differential cryptanalysis and the internal state col-lision of state update function.Then,Zhang et al.observed that the lower bound of steps that output keystream and internal state of MORUS-640-128 needing to full diffusion is 4 and 6 steps,respectively.Based on the property,they pro-posed a differential-distinguishing attack on 4.5-stepMORUS-640 under nonce-respecting model and performed a divide-and-conquer attack to recover the key of 3-step initialization of MORUS-640 under nonce-reuse setting.Dwivedi et al.applied differential and rotational cryptanalysis to retrieve the key of MORUS-1280-256 with 18-round and 8-round initialization,respectively.And ciphertext predictions were conducted on 7-round initialization of MORUS-1280-128 and on 10-round initialization of MORUS-1280-256.These analyses did not guarantee the uniqueness of nonces.Our security assessment of MORUS is done using the Mixed Integer Linear Programming(MILP)tool under nonce-respecting model,covering key-recovery attacks and distinguishing attacks for reduced-round ver-sion.We use the new concept of cube attacks based on the division property proposed by Todo et al.to recover the key of at most 5.5/6.5-step initializa-tion of MORUS-640/1280.This process takes the MILP model of bitwise AND operation with a constant introduced by Sun et al.into consideration,which makes division trails and subsequent integral distinguishers more accurate.And we also obtain 6/6.5-step integral distinguisher for MORUS-640/1280 and 4.5-step differential distinguisher of MORUS-1280.Compared to previous work,our cryptanalysis is the best result in terms of the number of attacked steps and required complexity.ASCON is an authenticated encryption scheme submitted to CAESAR com-petition and becomes one of the final portfolio.In CT-RSA 2015,the designers performed several detailed cryptanalysis on ASCON,including zero-sum distin-guisher.differential cryptanalysis and linear cryptanalysis on the permutation,cube-like attacks and differential-linear attacks on the initialization.The design-ers used the property of the permutation with low algebraic degree to create a zero-sum distinguisher for 12-round ASCON permutation with the complexity of 2130.which is able to distinguish the full 12-round permutation from a ran-dom one.Under nonce-respecting model,their work first applied cube-like attack to retrieve the key for 5/6-round initialization with time 235/266,then adopted differential-linear attack to recover the ke for 4/5-round initialization with time 218/236.Under nonce-misuse scenario,they gave forgery attacks on 3/4-round fi-nalization with 233/2101 messages based on differential analysis.We conduct fur-ther security analysis on ASCON,mainly evaluating the security loss when nonce is misused,our work consists of key-recovery attacks and forgery attacks.The key-recovery attack targets the round-reduced version of ASCON with 7-round initialization and 5-round phase of plaintext processing.With two methods of cube-like and cube tester,the key is olbtained with almost the same time 297,which works on round-reduced initialization comprising more than half number of original 12 rounds in the first time.The forgery attack focuses on 4/5/6-round finalization with 29/217/233 messages,which is more practical compared to the previous ones.The authenticated encryption family PRIMATEs pa.sses through the screening of t.he second round of CAESAR competition.It consists of three modes of operation:APE,HANUMAN,GIBBON and two security levels:80,120.The designers analyzed PRIMATEs in the submission document,including security declaration on the three modes of operation:APE,HANUMAN and GIBBON,differential trails,linear trails,collision producing trails and impossible differential cryptanalysis on the PRIMATE permutation.Moreover,Minaud introduced zero-sum distinguishers for 12-round PRIMATE permutation with the complexity 2130 in order to be distinguishable from random ones,and performed cube attack to recover the key of 8-round finalization of APE-80/120 with 233 2-block chosen messages and time complexity 261/271 under nonce-misuse setting.Morawiecki et al.applied cube attack to retrieve the key of 6-round initialization of HANUMAN-120 with time 265 and this attack did not need to repeat any nonces.Our security assessment of APE and HANUMAN in PRIMATEs family is mainly concerned with the resistance of repeating nonces.Based on the algebraic model of PRIMATE permutation,we find a series of integral distinguishers targeting PRIMATE permutation and its inverse.According to the findings,we improve zero-sum distinguishers of 12-round PRIMATE-80/120 permutation introduced by Minaud,reduce the required complexity significantly to 2100/2105.For 8-round finalization of APE-80/120,we use integral attack to recover the key.This attack adopts the new found 6-round integral distinguisher of PRIMATE permutation and applies FFT technique to optimize the key-recovery attack performed by Minaud,which reduces the data and time complexity to 230 and 23.929/20.26,respectively.For 5/6-round finalization of APE and HANUMAN,we present forgery attacks for the first time.We use integral distinguishers to build forgery.5-round forgery needs 215 chosen messages and 6-round forgery needs 230 chosen messages.From the complexity,forgeries are very practical.As one of the most widely adopted authentication ciphers,Galois/Counter Mode(GCM)has excellent software performance and hardware support.How-ever,the fault tolerance of GCM is low.and GCM cannot guarantee its security when nonce is misused in encryption or unverified plaintext is released(RUP)in decryption.Thus,based on GCM,some variants have been designed to achieve more robust security,such as GCM-SIV with nonce-misuse resistance,and GCM-RUP supporting RUP setting.At CRYPTO'17,Ashur et al.designed a generic construction by appending an extra tweakable block cipher(TBC)to an existing AE scheme,to achieve security even when releasing unverified plaintext.They proposed a concrete instantiation following this construction,GCM-RUP.The designers proved that GCM-RUP is secure up to the birthday bound in the nonce-respecting model,but do not make claims when nonce are misused.We show that this proof is tight with a birthday-bound universal forgery attack against GCM-RUP in nonce-respecting model.While there are simple distinguishing attacks with birthday complexity on GCM-RUP.our attack is much stronger:we have a partial key recovery leading to universal forgeries.We present a novel leakage technique of internal states using inner collisions,which will lead to the exposure of the output difference of GHASHK2.Then a polynomial equation for GHASHK2 with K2 as a root is constructed,which can be solved to recover K2· The recovery of K2 can be used to give an universal forgery for GCM-RUP with complexity 2n/2.For reference,the best known universal forgery attack against GCM requires 22n/3 operations,and many schemes do not have any known universal forgery attacks faster than 2n.This suggests that GCM-RUP offers a different security trade-off than GCM:stronger protection in RUP setting,but more fragile when the data complexity reaches the birthday bound.In order to avoid this attack,we suggest a minor modification of GCM-RUP that seems to offer better robustness at the birthday bound.