is it correct that for a nbit LFSR (galois algorithm in particular) the maximum number of unique 32byte keys can only be 255?

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

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

b) if above is correct then I can get up to 255 unique keys if using as minimum a 8bit_lsfr (2^8-1). right ?

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

d) So it doesnt make sense to increase the bits beyond 8 bits or is there another benefit for this particular case that I dont see ?

Thanks for any help in better understanding this in advance. Best Zaphoxx

edit: Clarifying what I mean with unique 32 byte key: when I generate multiple 32byte keys from an lsfr, then I save the generated keys in list and each key is only once in that list. I thought that when running a nbit lsfr 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 that question.

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

• thanks a lot for your response. you say 'once in a cycle', what is your definition of a cycle ? just want to make sure I got the same definition here. Thanks – Zapho Oxx May 16 '18 at 7:47
• a cycle is $2^n-1$ iterations long, where $n$ is the length of the register, so 255 in this case. – kodlu May 16 '18 at 8:15

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

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.