Tor Helleseth (University of Bergen): Breaking the filter generator

The filter generator is an important building block in many stream ciphers. The filter generator usually consists of an n-bit linear shift register that generates a maximal length linear sequence of period 2^n-1 and a nonlinear Boolean function of that combines bits from the shift register and creates an output bit z_t at any time t.The aim is to construct a pseudorandom sequence with good cryptographic properties. We give an overview of some of the existing basic cryptographic attacks on the filter generator. We also describe a recent new and improved algorithm that breaks most filter generators in less than exhaustive key search.