*Post by Scott Herbert*Is there any proof that LFSR are less secure then non-liner versions?

Or could someone point me in the direction of any work being done in this area?

If you use the output of the LFSR directly, it's... well... linear.

The problem with that is that (assuming the LFSR taps are known) with

any N

outputs, you can form a set of N linear equations in the N unknown

register bits

and solve them using Gaussian elimination. Even if the length and tap

positions are unknown, the Berlekamp-Massey algorithm will tell you

everything you didn't know, based on just over 2*N bits.

Nonlinear registers might be attackable in the same way, if the degree

of nonlinearity is not very high; just treat each higher-degree term

as if it was a new variable. This is called "linearization" and is the

basis of the new algebraic attacks. So you definitely need high

algebraic complexity. But even that might not be enough. The problem

with nonlinear FSRs is that it's pretty hard to prove anything about

them, in terms of period or nonlinear complexity. You might have

something that looks great but falls into small cycles, for example.

Greg.