1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

|improve this answer|||||
$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Zapho Oxx May 16 '18 at 7:47
  • $\begingroup$ a cycle is $2^n-1$ iterations long, where $n$ is the length of the register, so 255 in this case. $\endgroup$ – kodlu May 16 '18 at 8:15
0
$\begingroup$

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.

|improve this answer|||||
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.