# An (N)LFSR…but for bytes!

A linear feedback shift register can be thought of as an array of bits where NEW_BIT is calculated using F(REGISTERS). F is a function that takes values from two or more elements of REGISTERS and XORs them together. The new value of REGISTERS is equal to (in Python) [F(REGISTERS)] + REGISTERS[1:]. Do the dynamics change if we store values greater than 1 in each register, like say bytes? If F invoked operations other than XOR, then it seems like that would make it more like an NLFSR. Are the dynamics different there, too? Is something like this used by any cipher out there?

## 1 Answer

A classic linear feedback shift register is in fact a representation of operations in a modular ring of binary polynomials. In mathematical terms, you have a base field, which is $\mathbb{Z}_2$, the field with two elements (0 and 1); then a register of $n$ bits is a polynomial of degree at most $n-1$ in $\mathbb{Z}_2[X]$, and shifting the register is equivalent to multiplying the polynomial by $X$ modulo a given polynomial $P$ of degree $n$; that polynomial $P$ corresponds to the "feedback bits", i.e. which elements of the register you take to compute the new bit.

This model naturally extends to the case of using another base field or ring. For instance, if you use bytes and additions, then you are working with $\mathbb{Z}_{256}$, i.e. the integers modulo 256. With $n$ bytes, you still have polynomials of degree at most $n-1$, but this time in $\mathbb{Z}_{256}[X]$ (and it is still linear). Like the classic LFSR, taken alone as, say, a pseudo-random generator, it is still quite weak; moreover, $\mathbb{Z}_{256}$ is not a field, which tends to make matters worst (to express it "with the hands", additions modulo 256 will propagate carries only toward higher bits, so, in particular, the low bits of each byte will only depend on each other, not on the higher bits).

Now, symmetric algorithms are almost always built by assembling several (many) operations which, by themselves, would not constitute a cryptographic algorithm of any decent quality; for instance, SHA-256 is made out of about 2500 very simple elementary operations, the most complex of which being a simple addition. As such, LFSR expressed over various rings or fields can be used, and have been used, as building elements of larger algorithms. See for instance the Sosemanuk stream cipher, or the RadioGatún hash function.

A non linear feedback shift register would entail using operations that are not additions in some field of ring, i.e. not additions on integer or XOR. You could try some multiplications, but it will make analysis more complex with no clear immediate benefits. Remember that what is sought in symmetric algorithm design is a good trade-off between "mixing" (a generic terms for various concepts such as non-linearity and avalanche effects) and performance; moreover, we cryptographers really like to feel that we understand what we are doing, therefore "hard to analyse" is a bad thing, not a good thing.

• I thought addition isn't linear for bitwise operations. – Melab Sep 20 '17 at 2:47
• "Linear" is relative to a base field (or ring). Bitwise XOR is linear when the base field is $\mathbb{Z}_2$. Addition is linear when considering the base ring $\mathbb{Z}_r$ for some integer $r$ (here 256). Linearity is a relatively large concept. – Thomas Pornin Sep 20 '17 at 11:32
• So what kind of "non-linear" function would be a good one for analysis? – Melab Sep 20 '17 at 18:35