10.6. Security of the LFSR Stream Cipher

The nature of the LFSR Stream cipher makes it vulnerable to a known-plaintext attack. Since LFSR is used primary by hardware devices that can’t be modified after production not many elements of the system can be changed. As a result, the number of bits of the system and the definition that determines future iterations should be assumed to be unchangeable and public information, as recovery of the physical device would allow an enemy to determine these values. Therefore, only the seed value should be considered secret and part of the key.

This was the case with the Enigma Machine used in World War II. The rotor wirings were the same in each machine and could not be changed once put into production. Therefore, you should assume those wiring configurations to be known by the enemy since it only takes one device being captured for the settings to be determined.

By guessing only a letter or two of the plaintext, and having the corresponding ciphertext allows the interceptor to potentially deduce enough information to recreate the entire keystream, and thus decipher the rest of the message.

Cracking the LFSR Stream Cipher via Known Plaintext

Suppose you intercept the enciphered Base64 message r8wJAb30 and you know the LFSR system used was 7-bit and had the definition: \(b_7 \leftarrow b_1' + b_3'\). You suspect the message pertains to the State of North Carolina so you guess the first two plaintext letters are NC. This will be all you need to know to determine the entire message!

The first two ciphertext letters, r8 in binary are 101011 111100 and the guessed plaintext letters, NC in binary are 001101 000010. XOR’ing these two binary numbers will yield the associated keystream that would map the guessed plaintext to the ciphertext.

\[\begin{split} \begin{array}{r} \texttt{001101 000010} \\ \oplus\text{ } \texttt{101011 111100} \\ \hline \texttt{100110 111110} \end{array} \end{split}\]

So the guessed keystream is

Putting the guessed keystream into a table, similar to when creating a LFSR stream yields:

\(b_7\)	\(b_6\)	\(b_5\)	\(b_4\)	\(b_3\)	\(b_2\)	\(b_1\)
						1
						0
						0
						1
						1
						0
						1
						1
						1
						1
						1
						0

Working the transition rules (\(b_1 \leftarrow b_2'\), \(b_2 \leftarrow b_3'\), etc.) in reverse you can start to reconstruct the table.

\(b_7\)	\(b_6\)	\(b_5\)	\(b_4\)	\(b_3\)	\(b_2\)	\(b_1\)
1	0	1	1	0	0	1
1	1	0	1	1	0	0
1	1	1	0	1	1	0
1	1	1	1	0	1	1
1	1	1	1	1	0	1
0	1	1	1	1	1	0
	0	1	1	1	1	1
		0	1	1	1	1
			0	1	1	1
				0	1	1
					0	1
						0

Revealing the associated seed value of 1011001. You can verify that the values in the table are valid for this seed and definition, and then continue to fill in the missing values.

\(b_7\)	\(b_6\)	\(b_5\)	\(b_4\)	\(b_3\)	\(b_2\)	\(b_1\)
1	0	1	1	0	0	1
1	1	0	1	1	0	0
1	1	1	0	1	1	0
1	1	1	1	0	1	1
1	1	1	1	1	0	1
0	1	1	1	1	1	0
1	0	1	1	1	1	1
0	1	0	1	1	1	1
0	0	1	0	1	1	1
0	0	0	1	0	1	1
0	0	0	0	1	0	1
0	0	0	0	0	1	0

At this point, you have everything you need to continue generating as many values of the 7-bit LFSR keystream as you need to decipher the rest of the message.

Continuing the guess forward so there’s a long enough keystream for the 8-character message (\(8 \text{ characters} \times 6 \text{ bits} = 48 \text{ bits}\)) you can obtain the keystream: 100110 111110 100010 010101 100001 110011 011111 010001.

XOR the keystream with the binary ciphertext: 101011 111100 110000 001001 000000 011011 110111 110100.

\[\begin{split} \begin{array}{r} \texttt{100110 111110 100010 010101 100001 110011 011111 010001} \\ \oplus\text{ } \texttt{101011 111100 110000 001001 000000 011011 110111 110100} \\ \hline \texttt{001101 000010 010010 011100 100001 101000 101000 100101} \end{array} \end{split}\]

Converting back to the Base64 plaintext, the message is finally revealed: NCSchool, and the cipher is broken.

Video Example

Here’s a second example of cracking an LFSR cipher in video format.

Summary of Results

The simplicity of LFSR is a double-edged sword. It allows for cheap and easy implementation in hardware devices, but with just a small amount of information about the plaintext, the LFSR can be completely broken by a known-plaintext attack. It’s much too easy to work backwards from the ciphertext stream to determine previous states of the LFSR system to ultimately retrieve the seed value.

There are modifications to the LFSR system that can reduce the vulnerability to known-plaintext attacks.