10.4. Linear Feedback Shift Register (LFSR) Stream Ciphers#
A linear feedback shift register (LFSR) is a type of digital circuit that has several storage areas, each of which can hold 1 bit, connected in a chain. The output of each storage area is connected to the input of the next storage area in the chain, resulting in a circuit that shifts the data stored in it one place to the right each time the circuit is run. The way the storage areas are connected varies from circuit to circuit, and each configuration will change the pattern in which the bits move from one storage area to the next.
LFSRs have many important uses in digital communication, not just in cryptography. They are used in TV broadcast signals, data transfer via USB cable, and GPS navigation. LFSR circuits are still used to encrypt GSM cell phone signals, despite having serious security issues.
To learn more about how LFSR’s work, watch the 10-minute video below.
In this course, we will not use actual circuits to generate the pseudo-random keystream of bits, but first generate them by hand using the system described in the video, and later with Python code.
10.5. LFSR Stream Cipher#
Let’s encrypt the message C3P (shortened from C3P0) using a 4-bit LFSR with seed 0110 and definition: \(b_4 \leftarrow b_1' + b_2' + b_4'\)
The first step is to convert the ASCII string to binary:
ASCII plaintext: C3P
binary plaintext: 01000011 00110011 01010000
Next, compute the output stream of the LFSR so there are as many bits as needed for the message. In this case, 24.
\(b_4\) |
\(b_3\) |
\(b_2\) |
\(b_1\) |
|---|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Looking at the right-most column, you obtain the bitstream:
01101101 10110110 11011011
Performing the XOR Cipher on these keystreams:
Which when converted to Base64 yields LoWL
To decipher a LFSR Stream cipher, you need to perform a bitwise subtraction of the keystream fromt he ciphertext binary stream. Fortunately, bitwise subtraction is identical to bitwise addition, so you simply use the XOR operation again.
Base64 ciphertext: LoWL
binary ciphertext: 001011 101000 010110 001011
Using the same binary keystream: 011011 011011 011011 011011
Which converts back to the ASCII plaintext: C3P
Maximizing Period of Repeating Streams#
You may have noticed that in the previous example, the number of bits and the rules associated with those bits resulted in a less than ideal sequence of bits. In fact, the sequence generated was no better than a Caesar cipher, since bit \(b_1\) left the pattern 011 repeating over and over, resulting in the values 011011 aligned over each character.
When using a LFSR Stream to encipher a message, you should try a few rule configurations to make sure that the bitstream isn’t too predictable. As a general rule, if your LFSR system uses \(n\) bits, there is a rule system that will result in the bitstream not repeating itself for \(2^n - 1\) bits. You wouldn’t want to always use the same rule, because that would be too predictable for an eavesdropper to guess, but you should attempt to ensure that the bitstream does not repeat itself during the string used for enciphering the message.
The table below shows a selection of rules for different size LFSR systems that result in a maximum period, which is the number of bits before the pattern repeats.
Bits (\(n\)) |
Definition |
Period $\( ( 2^n-1 ) \)$ |
|---|---|---|
2 |
$\(b_2 \leftarrow b_1' + b_2'\)$ |
3 |
3 |
$\(b_3 \leftarrow b_1' + b_2'\)$ |
7 |
4 |
$\(b_4 \leftarrow b_1' + b_2'\)$ |
15 |
5 |
$\(b_5 \leftarrow b_1' + b_3'\)$ |
31 |
6 |
$\(b_6 \leftarrow b_1' + b_2'\)$ |
63 |
7 |
$\(b_7 \leftarrow b_1' + b_2'\)$ |
127 |
8 |
$\(b_8 \leftarrow b_1' + b_3' + b_4' + b_5'\)$ |
255 |