Algebraic Attacks on Combiners with Memory and Several Outputs

Algebraic attacks on stream ciphers [9] recover the key by solving an overdefined system of multivariate equations. Such attacks can break several interesting cases of LFSR-based stream ciphers, when the output is obtained by a Boolean function, see [9-- 11]. Recently this approach has been successfully extended also to combiners with memory, provided the number of memory bits is small, see [1, 11, 2]. In [2] it is shown that, for ciphers built with LFSRs and an arbitrary combiner using a subset of k LFSR state bits, and with l state/memory bits, a polynomial attack always do exist when k and l are fixed