An Algebraic Cryptanalysis of Nonlinear Filter Generators using Gröbner bases

This paper presents an algebraic cryptanalysis of nonlinear filter generator. A linear shift register of length L filtered by a non linear boolear function f of degree deg(f) is equivalently described by a set of algebraic equations. More precisely, if N is the size of given output bits then we have a system of N algebraic equations of total degree deg(f) in L variables. By solving this system of equations we can recover all the possible initial state (the secret key) of the device . Gröbner is precisely an efficient tool for solving algebraic systems. Recently, very efficient algorithms (F_5 ) have been proposed which are several order of magnitude faster than the historical Buchberger algorithm. We show that with only a polynomial number of output bits we can recover in polynomial time the initial state. More precisely we can show that is enough to have (L^d) output bits with d where k is the number of variables of the filtering function. Surprisingly, for all the stream ciphers satisfying Golic's design criteria and filtering functions found in literature we found that d is much less than the predicted bound: for instance the Lili is of degree 6 but a simple Gröbner computations shows that it behaves like a degree 4 function. Even more surprisingly, we show experimentally that for some examples we can recover the initial state in polynomial time with only L + output bits. Different attacks have been implemented, and we give a list of timing experimented on many real size size (L80 bits) stream cipher