Algebraic Attacks On Nonlinear Combiners With Memory

Algebraic attacks is a new attack method occurred in recent years, which completely attributes the security problem to the solution of the overdefined system of multivariate equations. Since the solvability of such multivariate equations were always ignored for many of the synchronous stream ciphers when they were designed, these algorithms are difficult to defend such new attack methods.Some results of algebraic attacks on stream ciphers are summarized and algebraic attacks on nonlinear combiners are also discussed in this paper. By using the Groebner bases theory and elimination theorem, we constructed a new algorithm of the algebraic attacks on nonlinear combiners with memory based on the previous works, and also analyzed its computation complexity in detail. We put the new algorithms into the algebraic attacks on the E₀ algorithm and the SNOW algorithm, and also evaluate the computation complexity of the algebraic attacks in the end.