Discussion:
NLFSR vs. LFSR
(too old to reply)
Scott Herbert
2004-11-24 17:55:06 UTC
Permalink
Raw Message
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?

Thanks Scott.
Z
Greg Rose
2004-11-26 08:55:57 UTC
Permalink
Raw Message
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.

Loading...