Return to NLFSR (thing)

Short for "nonlinear feedback shift register".

 

A nonlinear feedback shift register is a particular type of shift register, similar to a LFSR but where the state update is a nonlinear function of part of its own state (rather than a linear function of part of its own state).

These are often used as components in (hardware-efficient) stream ciphers, displaying a higher resistance towards correlation attacks than LFSR. On the other hand, unlike for LFSR, construction of large NLFSR with guaranteed long periods is not a trivial problem. An example of such NLFSR-based hardware-efficient cipher is Trivium.

Similar to what happens with a LFSR, a N-stage NLFSR contains N delay elements which store N bits of state (x0, x1, x2... x(N-2), x(N-1)). Each time the NLFSR is clocked, the bit stored in x0 is output, every other bit is shifted down a stage (x0 becomes the old x1, x1 becomes the old x2, etc.) and the last bit (x(N-1)) becomes the result of the nonlinear update function. This way of expressing a NLFSR is termed "Fibonacci configuration" (it can also be equivalently expressed in "Galois configuration", but that's beyond the scope of this writeup).

 


The properties of a specific N-stage NLFSR boil down to the chosen state update function. For example, the 24-stage NLFSR defined by the update function:

x(N-1) = x0 ⊕ x1 ⊕ x8 ⊕ x9 ⊕ x15 ⊕ (x7 AND x18)
(where ⊕ denotes XOR)

has the quasi-maximum period of 224-1 (where every state is in a big cycle, except for the all-zero state, which is a fixed point).

If wanted, this can be increased to 224 by changing the state update function to:

x(N-1) = x0 ⊕ x1 ⊕ x8 ⊕ x9 ⊕ x15 ⊕ (x7 AND x18) ⊕ z
(where z = (¬x1 AND ¬x2 AND ... AND ¬x22 AND ¬x23), and ¬ denotes the NOT operation)

which ensures every possible state (including the all-zero state) is in the same single maximal cycle.

 


Even though it's not easy to figure out which specific state update functions generate maximum (or quasi-maximum) period NLFSR (without actually running them through every state to verify), it's not difficult to guarantee that a certain state update function generates branchless state transitions (i.e. that every step is reversible and, therefore, the dynamic structure consists of pure cycles without state collisions). Particularly, it's enough to ensure that the state update function is of the form:

x(N-1) = x0 ⊕ g( x1, x2, ..., x(N-2), x(N-1) )
(where g() is an arbitrary boolean function with N-1 inputs and 1 output)

 


Reference:

Existing:

Non-Existing: