Skip to Main content Skip to Navigation

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

Jean-Charles Faugère 1, 2 Gwénolé Ars
1 SPACES - Solving problems through algebraic computation and efficient software
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : 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 ciphers
Document type :
Complete list of metadata
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 6:57:03 PM
Last modification on : Friday, February 26, 2021 - 3:28:07 PM
Long-term archiving on: : Sunday, April 4, 2010 - 10:41:05 PM


  • HAL Id : inria-00071848, version 1


Jean-Charles Faugère, Gwénolé Ars. An Algebraic Cryptanalysis of Nonlinear Filter Generators using Gröbner bases. [Research Report] RR-4739, INRIA. 2003. ⟨inria-00071848⟩



Record views


Files downloads