Study Of Algebraic Attacks On Stream Ciphers

Security analysis of the key stream generators is always at the central of the research on stream ciphers. This thesis mainly analyzes the algebraic attacks on stream ciphers. The computational complexity and memory demand are investigated when algebraic attacks apply to a few stream generators. We also present the recent results we obtained about algebraic attacks and some other attacks on stream ciphers. 1. Algebraic attacks on stream ciphers are investigated. We present the methods of algebraic attacks and computational complexities in which the nonlinear filter generators are only partially known or totally unknown. 2. We present and investigate the computational complexity of a new fast algorithm for constructing depressed functions based on cryptographic functions splitting idea. An improved version of the algorithm is also provided. When applied to LILI-128 cryptographic system to construct depressed functions, the new algorithm obtains a lower computational complexity. 3. We propose a new resynchronization attack based on the difference performances of combinational functions. This attack can get a system of linear equations or of low-degree equations about initial key,and recovers the initial key by solving the system of equations. When implemented to the Toyocrypt scheme, our method gains a lower computational complexity. 4. Another resynchronization attack is also proposed, which is the combination of the differential cryptanalysis and algebraic attack. We use it to cryptanalyze the LILI-128 scheme.