The Fault Cube Attack And Slid Pairs Research On Trivium

Trivium is the most preferred algorithm proposed by eSTREAM project. As a typical representative of epochal stream cipher, it has caught lots of attention from cryptographists. In recent years, research on Trivium has become a hot topic in stream cipher, especially in cryptanalysis.The design of Trivium combines the idea of circularly updating inner state and the nonlinear feedback, which makes its structure seem simple but actually with high security. In this brand-new design, the proposals of Trivium have fully realized the weakness of earlier linear stream cipher, and drawn on some excellent designing ideas from block cipher. At the same time, it also considers the ability to resist all existing attacks, especially algebraic attack, correlation attack and differential cryptanalysis. Since Trivium was proposed in 2005, although some scaled-down variants of Trivium have been shown insecure, the full-scale version still remains unbroken. In this thesis, we further make some research on the cryptanalysis of Trivium and obtain the following three main results:1. Based on cube attack and fault analysis, we first innovatively propose the fault cube attack on Trivium. The basic idea of the attack is to inject faults in proper position of the inner state, divide the initialization into two parts with fewer rounds, and use the cube attack efficiently to analyze the two parts individually, then combining the cube attack of two parts as a full attack of the algorithm according to the fault injection position. This technique effectively improves the cube attack through fault injection and can attack scaled-down Trivium variants up to 1056 initialization rounds with complexity O(253).2. On the research of Trivium, we found an interesting and significant phenomenon that some key/IV pairs can produce identical keystreams up to a shift. In this sense, these key/IV pairs are actually cyclically equivalent, which are called key/IV slid pairs in this thesis. In this thesis, we use SAT solvers to solve the nonlinear systems of equations describing key/IV slid pairs, and find many key/IV slid pairs up to 195-bit shifts. Compared with known results, the number of key/IV slid pairs found and the efficiency of the searching algorithm are both remarkably improved.3. The chose-IV statistical analysis has been a hot topic in the early research on the cryptanalysis of Trivium. Based on many cryptanalysts'research, a typical framework for chose-IV statistical analysis has been formed. However, in such framework, only the relative cryptographic properties of one keystream bit's algebraic normal form are concerned. In this thesis, we further consider a relatively longer keystream's algebraic normal form, and propose a new framework for chose-IV statistical analysis. Some improvements are obtained in the chose-IV statistical analysis on Trivium by use of this framework.