Research On Cryptanalytic Methods Of Grain-like Stream Ciphers

Grain family of stream ciphers are well-known NFSR-based stream ciphers,including Grain v1,Grain-128 and Grain-128a.Among them Grain v1 is one of the eSTREAM finalists and Grain-128a is standardized by ISO/IEC for encryption and authentication for radio frequency identification(RFID).Grain family of stream ciphers adopt similar design structure,all consisting of a cascade connection of two shift registers of the same degree and a nonlinear output function.Ever since the eSTREAM project,the cryptanalysis of Grain family has attracted extensive attention in the academe.However,due to the lack of powerful tools,the process of the cryptanalysis of Grain v1 and Grain-128a develops slowly.At the same time,the structure of the cascade connection of two registers in Grain v1 has been widely used in the design of lightweight stream ciphers.For instance,lightweight stream ciphers Sprout,Fruit,LIZARD,Plantlet and lightweight Quark family of Hash functions all adopt the cascade connection of two registers as primitives.Although lightweight ciphers are greatly needed in industry,the design of a lightweight cipher which is highly secure is still a challenge.Therefore,the cryptanalysis of Grain family of stream ciphers and other stream ciphers adopting the model of cascade connection of two registers(together referred to as Grain-like stream ciphers)becomes increasingly pressing.This dissertation investigates the typical cryptanalysis methods on Grain-like stream ciphers.With respect to the function design,model structure,initialization process and key schedule,this paper further studies conditional differential attacks,distinguishing attacks,internal state recovery attacks and differential fault attacks on Grain-like stream ciphers systematically.In specific,the main results are:1.Inspired by the idea of cube attack and based on careful observation on the differential propagation of initialization process,this dissertation proposes new differential engine,difference-choosing scheme,condition-imposing scheme,and also bias-increasing strategy for conditional differential attacks on Grain v1.It is shown that the improved conditional differential attacks could retrieve 15 distinct secret key expressions for 110-round Grain v1.Thus far,this result is the best known for the reduced variants of Grain v1 as far as the number of attacking round is concerned.2.Athough the conditional differential attacks could mount the best distinguishing attacks against Grain-128a,no secret key information could be obtained.To obtain secret key information,this dissertation further explores the influence of the function model on the differential propagation.Considering the different expressions of differential propagations,this paper proposes the definition of effective differences aiming at recovering secret key bits.Based on these results,this dissertation derives the key recovery attacks against Grain-128a based conditional differential cryptanalysis for the first time,which could retrieve 18 secret key expressions for 169-round Grain-128a.Thus far,this is the best key recovery attack against reduced Grain-128a as far as the number of the attacking rounds is concerned.3.This dissertation further explores the distinguishing attacks on Grain v1 based on conditional differential cryptanalysis.In specific,this dissertation proposes a novel method to select the appropriate input difference and also a new condition-imposing strategy,both targeting an obvious distinguishing probability of the output difference distribution.It is shown that based on these results,the new attack could distinguish the distribution of the output difference of the 111-round Grain v1 from a random one.Thus far,this is the best single-key attack on Grain v1 in terms of the number of attacking rounds.4.Based on further investigation of the influence imposed by secret key bits on the differential propagation in the initialization process of Grain-128a,this dissertation further derives an distinguishing attack on Grain-128a in a weak-key setting.It is shown that the new attack could distinguish the output difference of 195-round Grain-128a from a random one.Thus far,this is the best distinguishing attack on Grain-128a in terms of the attacking rounds.5.BSW-sampling is an efficient way to generate and enumerate special cipher states.If a stream cipher has low sampling resistance,then the time-memory-data tradeoff(TMDTO)attacks against this cipher will be greatly improved.By carefully observing the state-transform function of Grain v1,this dissertation proposes an improved BSW-sampling technique which can dynamically control the internal state bits.It is shown that using this technique the sampling resistance of Grain v1 can be further reduced to 2-29 which is the best result so far.These results lead to efficient internal state recovery attacks on Grain v1 based on TMDTO with wider choices of parameters.Compared with the previous works,the proposed attacks have better complexity figures.6.This dissertation proposes a new BSW-sampling technique which converts the process of constructing special internal states into the problem of solving system of equations.The technique breaks the limitation of the traditional BSW-sampling that only one internal state bit could be recovered at one clock and thus is expected to obtain lower sampling resistance than the traditional one.Utilizing this technique,the sampling resistance of Grain-128a is further reduced to 2-50,which is the best result so far.These results lead to efficient internal state recovery attacks on Grain-128a based on TMDTO with wider choices of parameters.Compared with the previous works,the proposed attacks have better complexity figures.7.LIZARD is a lightweight stream cipher proposed by M.Hamann et al.at FSE 2017.This paper gives the security evaluation of LIZARD in regard to differential fault analysis for the first time.In specific,this dissertation proposes a new method to determine fault location for LIZARD,whose success probability reaches 1,while the success probabilities of the existing methods when applied for LIZARD hardly exceed 0.6.Then nonlinear equations deduced from the faulty keystreams and fault-free keystreams are solved using SAT solvers.Experimental data shows that by inserting faults for 30 times and using 6 groups of 100-bit faulty and fault-free keystreams,SAT solver will return solution in less than 20 minutes.Finally the comparison shows that LIZARD is more resistible than Grain v1 in regard to differential fault analysis.