When does a feedback shift register count as non-linear?

Question

It seems that a feedback shift register is counted as a linear feedback shift register whenever it only includes XOR operations. This leads me to believe that a non-linear feedback shift register is any feedback shift register that does not just use XOR operations and would include the use of S-boxes, AND operations, permutations, and so forth. Am I correct?

Answer 1

Yes, you're right.

XOR is considered a linear function in this case. So the feedback into the registers is linear. A non linear feedback shift register is a more generalised example where the feedback function can be anything. You can also call them generalised linear feedback shift registers GLFSR). S-boxes, AND operations, permutations, and so forth are all good. So the re-entrant bit is more than just a simple XOR operation of register bits. This frees you from the rigidity of Galois, Fibonacci and other predefined taps. But then you'd have to make sure that lockup doesn't occur and the registers do not settle into some sort of funky stable pattern.

A picture showing a not so complex non linear feedback function f, but it could be anything as you suggest:-

This immediately brings up the interesting possibility of a secure hash function being f. Or would that just be too much..?

Answer 2

A shift register with all XOR operations feedback has Linear feedback. But also something with all modular additions has linear feedback. And many more operations operations qualify, we can do addition over any field.

If the operations aren't all addition over some field (and moving field elements around) it is non-linear. For example doing both addition and xor, or using both xor and And operations would produce non-linearity.