Is it correct that for a n-bit LFSR (Galois algorithm in particular), the maximum number of unique 32-byte keys can only be 255?

Question

In fact, I have more than one question. For a CTF challenge, I am currently reading up on LFSRs. The code the challenge provides as an example is a 5-bit LFSR, and it generates from its bit sequences a 32-byte key (8-bit to one byte and this 32 times). So the first and last bytes of the key are the same for this particular 5-bit case as after $2^5-1$ iterations, the whole sequence repeats. Also, if I understand the whole logic behind a LSFR right, I can produce $2^5-1$ unique keys only for the 5-bit version. (starting with one particular seed, e.g., $s=1$). Also, I can have $2^5$ different initial seeds. So, according to my tests, this will not produce an additional 31 unique 32-byte keys but only duplicate keys in a shifted sequence.

Questions:

a) are the above statements as written correct, or did I miss something?

b) if the above is correct, then I can get up to 255 unique keys if using, as a minimum, an 8-bit LFSR ($2^8-1$). Right?

c) I will always get a max of 255 unique keys even if I increase the bits of the LFSR as I can only have 255 unique bytes, and the byte sequence will repeat. Is that correct?

d) So it doesn't make sense to increase the bits beyond 8 bits, or is there another benefit for this particular case that I don't see?

---

Edit:

Clarifying what I meant with unique 32-byte key: when I generate multiple 32-byte keys from an LFSR, I save the generated keys in a list, and each key appears only once in that list. I thought that when running an n-bit LFSR, the maximum number of 'unique' keys would be 255, but that might not be true, and I'll need to recheck that. Maybe someone can clarify this.

Answer 1

An $n-$ bit primitive LFSR generates the $2^n-1$ unique nonzero $n$ tuples exactly once in a cycle.

Take $n=8$ and your questions all have the answer yes, except the all zero seed will not give any tuple other than the all zero tuple.

However, such an $n$bit primitive LFSR generates all $k$ tuples, for $k\leq n,$ (provided its initial loaading is nonzero)

$$2^{n-k}$$ times if the $k$tuple is not all zeroes, and $$2^{n-k}-1$$ times if the $k$ tuple is all zero.

So these $k$ tuples are not unique, repeat at pseudorandom times along the cycle, but you do get the all zero $k$ tuple occur naturaly in the scheme.

Example: $n=4,k=3.$ There should be 2 of each nonzero 3-tuple in a period while the zero 3 tuple should occur exactly once. The sequence below is a primitive LFSR sequence. I have taken $2^4-1+2=17$ symbols instead of 15, so I can examine the 3-tuples starting within one period from position 1 to position 15. I grouped in 5's to make it easy to see positions

00100.11010.11110.00

001 occurs twice, starting in position 1 and 4

010 occurs twice, starting in position 2 and 8

100 occurs twice, starting in position 3 and 14

etc.

000 occurs once, starting in position 15

Answer 2

What's in propositions a) b) is correct, for both Galois and Fibonacci LFSR, subject to two missing conditions:

• The initial value is not all-zero; otherwise the key output is always all-zero.
• The polynomial is primitive (Joerg Arndt's useful and ugly page of mathematical data has those up to degree 11 and one per degree up to 660); otherwise the period will be shorter.

Proposition c), thus d), do not hold. Subject to the above conditions, the period of the generator for a polynomial of degree $n$ is $2^n-1$ bits, which is coprime with $8$ (the number of bits in an octet), hence the period at the octet level is $2^n-1$ octets.