New Techniques For Symmetric-key Cryptanalysis

The Internet has been tightly involved into people's daily life and even the country's development due to its continuous development and evolution.Consequently,how to ensure cybersecurity has attracted an increasing interest from researchers in both academia and industry.As the basis of cybersecurity,it is obvious that cryptography plays an important role and needs more attention.According to the differences in encryption,modern cryptography can be classified into two catagories in general,i.e.,symmetric-key cryptography and public-key cryptography.Symmetric-key cryptography is well-known for its high performance and has been widely used for data encryption,which covers the block cipher,stream cipher,hash function and authentication encryption.Different from public-key cryptography,the security of a symmetric-key primitive is not based on a concrete difficult mathematical problem but rather its resistance against many state-of-the-art attacks.Therefore,developing new techniques for symmetric-key cryptanalysis is crucial to understand the security of symmetric-key primitives.We are motivated by it and will present some original techniques and results in symmetric-key cryptanalysis,as stated below:1.Cryptanalysis of RIPEMD-160.Since Wang et al.made a breakthrough in the cryptanalysis of MD-SHA hash family in 2005,many MD4-like hash functions have been proven to be insecure,including RIPEMD,RIPEMD-128,MD5,SHA-0and SHA-1.However,for RIPEMD-160 which was designed in almost the same time-period when the above mentioned hash functions were designed,it still remains secure and there is no full-round collision attack.Hence,it is still used,e.g.,to generate Bitcoin addresses together with SHA-256,and is an ISO/IEC standard.Due to its dual-stream structure,even the semi-free-start(SFS)collision attack starting from the first step can only reach 36 steps and both the time and memory complexity are rather high,which was obtained by Mendel et al.at Asiacrypt2013.To improve this SFS collision attack in terms of the time and memory complexity,some new strategies for freedom degree utilization and solving equations are proposed.However,the improved attack still requires a significant amount of computational resource.To overcome this obstacle,we propose a new efficient SFS collision attack framework for reduced RIPEMD-160.Benefiting from our new framework,we could provide the first practical colliding message pairs for the first 36 and 37 steps of RIPEMD-160.Moreover,the theoretical SFS collision attack can reach up to 40 steps.In addition to the SFS collision attack,efficient collision attack frameworks are also proposed,which allows us to find the first practical colliding message pairs for 30 and 31 steps of RIPEMD-160 and to give the best theoretical collision attack for up to 34 steps.To the best of our knowledge,our(SFS)collision attacks on reduced RIPEMD-160 are the best thus far.2.Cryptanalysis of Subterranean-SAE.Subterranean 2.0 is a Round 2 candidate of the NIST Lightweight Cryptography Standardization process.In the official document of Subterranean 2.0,the designers have analyzed the security of its hash scheme.However,due to the special structure,little cryptanalysis of the authenticated encryption scheme Subterranean-SAE was made.For Subterranean-SAE,the designers expect a non-trivial effort to achieve the full-state recovery in the nonce-misuse setting.Motivated by this expectation,we propose a new strategy to utilize the conditional cube tester,i.e.,directly recovering 1 secret state bit from the cube sum of ciphertexts.Moreover,such a method can also be extended to the attacks in the nonce-respecting setting by reducing the number of blank rounds.As a result,together with some algebraic techniques,we are able to provide the first practical state-recovery attack and key-recovery attack in the nonce-misuse setting and to give a practical distinguishing attack and a theoretical key-recovery attack in the nonce-respecting setting by reducing the number of blank rounds from 8 to4.3.Cryptanalysis of Gimli.Since Keccak was selected as the SHA-3 standard,an increasing number of permutation-based primitives have been proposed.Different from block ciphers,no round key will be used in the underlying permutation for permutation-based primitives.Consequently,there exists a higher risk for a differential trail of the underlying permutation to become incompatible when considering the dependency of difference transitions over different rounds.However,in most of the MILP or SAT based models to search for differential trails,only the difference transitions are involved and are treated as independent in different rounds,which may cause that an invalid one is found for the underlying permutation.To overcome this obstacle,a new method to search for differential trails is proposed.Specifically,the dependency between the difference transitions and value transitions over rounds are taken into account in the model.With our techniques,we reveal that some existing differential trails of reduced Gimli are indeed invalid,one of which is found in the Gimli document.In addition,a compatible 6-round collision-generating differential trail is found with our new model,which allows to mount a collision attack on 6 rounds of Gimli-Hash.As a second-round candidate in NIST Lightweight Cryptography Standardization process,Gimli has attracted many researchers' interest for its simplicity,symmetry and weak diffusion.By exploiting these features and investigating some properties of the SP-box used in Gimli,we demonstrate that it is feasible to construct a novel 18-round distinguisher and an improved full-round distinguisher with time complexity 2and 252,respectively.Apart from these,our preimage attack on the hash schemes Gimli-Hash and Gimli-XOF-128 can reach up to 5 and 9 rounds,respectively.For the authenticated encryption scheme,our state-recovery attack can reach 9 rounds.To the best of our knowledge,the proposed distinguishing attack,preimage attack and state-recovery attack are all the best so far.In addition,if considering the collision attack starting from the first round,i.e.,there is a swap operation in the first round,our collision attack on 6-round Gimli-Hash is also the best thus far.