1
$\begingroup$

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.

$\endgroup$

2 Answers 2

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

$\endgroup$
2
  • $\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, 2018 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, 2018 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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