Research On Linear Programming Based Differential Cryptanalysis Of Stream Cipher

With the development of the Internet of Things(Io T),the corresponding security prob-lems draw the attention of the public and arouse the researches of the security encryption al-gorithms.Due to the stream cipher's advantages in limited hardware environments and fast software encryption,nowadays it is becoming one of the most popular cipher schemes.Be-cause the stream ciphers based on linear shift register are discovered to be insecure,a lot of projects are launched worldwide(e.g.NESSIE,CRTPYREC,e STREAM,CAESAR)to col-lect new designs for a stream cipher.Among the collected designs,there are schemes based on the non-linear shift register,sponge function,and linear shift register with non-linear modules.To evaluate these novel structures better,more up-to-date cryptanalyses are developed,which include the improvements for the former cryptanalysis and brand new cryptanalysis.Based on several major cryptanalyses at present,this thesis researches the method of improving them to verify the security of the new ciphers a step further,then discusses the potential problems.The main contributions of this thesis are listed as follows:(1)We propose an optimized merging strategy for the fast near collision attack on Grain.To alleviate the huge online phase expenses,we improve the merging strategy by analyzing the effects of different merging methods on the data generated after the merging.Then the optimal strategy of merging methods for the merging steps can be solved by linear programming.Through experiments,it is found that there are reductions in the time complexity of 79.4% and27.8% in the cases of Grain v1 and reduced Grain respectively.Also,the new strategy does not affect the complexity of pre-computation,data,and memory,which indicates a high application.(2)We propose an error-collected mixed-integer linear programming model for cube-attack-like cryptanalysis on Keccak.Due to the original model has an inaccurate description of the at-tack,whose solution set deviates from the actual one,the optimality of generated results cannot be ensured.We develop an error-corrected model by refining the patterns of the private vari-ables diffusion,which has the function of automatically filtering the errors.The experiments Ketje Jr v1 show that in the cases of 5-round and 6-round key-size reduced attacks there are reductions on the time complexity of 23.7% and 93.9%,and the utilized cubes are reduced from3 to 2 in the 5-round attack.(3)We analyze the resistance of Grain to the division-property-based cube attack.Based on division property,we conduct experiments to count the cube variables and the upper bound of the degree of superpoly in each iteration,then the algebraic degree growth rate of the maxterm and the upper degree of the superpoly can be curved.We give the strategy of parameters selecting and the trend analysis on the superpoly degree growth in the high-round attack,which verifies the reliability of the Grain128 a.