Fast Correlation Attacks And Design Of Small State Stream Ciphers

Stream cipher is a symmetric encryption algorithm based on the concept of pseudorandom key stream generator,and it is an important branch in the field of modern cryptography.In practical applications,hardware-oriented stream ciphers often have higher requirements for storage,so the concept of lightweight stream ciphers came into being,and its design requirements are to reduce the internal state as much as possible.The three cryptographic algorithms Mickey,Grain v1 and Trivium in the hardware field finally screened out by the EU project e STREAM are all lightweight stream ciphers.But in order to resist the time-memory-data trade-off(TMDTO)attack,the design of all these ciphers must follow the rule of birthday security-the length of the internal state is at least twice the length of the initial key,which leads to that a larger internal state is used to generate the Key stream.This makes the design of lightweight stream ciphers challenging.In order to solve this problem,small-state stream ciphers(SSCs)were created,whose internal state length is less than the security level-twice the key size,without compromising its effectiveness against TMDTO attacks.The main feature of small-state stream ciphers is that the initial key(or initialization vector IV)is not only used for initialization,but also used for the key stream generation process.This design idea helps to design a stream cipher with a smaller size and a lower power consumption.Since 2015,based on this design idea,Sprout,Fruit-v1,Fruitv2,Fruit-80,Willow,Fruit-F and other small-state stream ciphers have been proposed.At the same time,the corresponding security analysis has proved that these structures are not completely safe.This paper summarizes the development history of small-state stream ciphers since its birth in 2015,including the general structure of each algorithm,design principles,various analysis methods,and the development trends in the future.It is found that there is still a lack of relevant theories in the research field of small-state stream ciphers.So this encourages researchers to study the security of these small-state stream ciphers,continuously improve their design guidelines,and propose a stream cipher structure with better performance.Based on this paper,the work done is as follows:First of all,the current development status of small-state stream ciphers is sorted out,and summarized,including: the design and defects of various versions of small-state stream ciphers;the current status of security analysis of small-state stream ciphers;the design guidelines and the design direction for small-state stream ciphers.Secondly,based on the fast correlation attacks(FCA)on small-state stream ciphers proposed by Chinese scholar Zhang Bin in 2018,combined with the decomposition and elimination linearization technology which has been applied to the linearization analysis of block ciphers,an improved FCA is applied to the small-state cipher Fruit-80,and its attack complexity is better than exhaustive search attack.Subsequently,according to the design theory of the existing small-state stream ciphers,based on Fruit-80,a new small-state stream cipher structure,Fruit-W,was tried to be designed.Compared with the previous small-state stream ciphers,it has the least number of register usage and initialization rounds without compromising security,thus reducing power consumption and circuit area.And we implement it in software,and test the randomness of the generated key stream.The security analysis of the structure has been carried out.The analysis results show that the structure can effectively resist fast correlation attacks,TMDTO attacks,guessing and decision attacks,and weak key attacks,etc.,and can successfully pass the statistical detection of NIST and National Secrets.