# Understanding Cryptography by Christof Paar and Jan Pelzl - Chapter 2 Solutions - Ex2.11

- 7 mins

## Exercise 2.11

We want to perform an attack on another LFSR-based stream cipher. In order to process letters, each of the 26 uppercase letters and the numbers 0, 1, 2, 3, 4, 5 are represented by a 5-bit vector according to the following mapping:

We happen to know the following facts about the system:

• The degree of the LFSR is $m = 6$.
• Every message starts with the header WPI.

We observe now on the channel the following message (the fourth letter is a zero):

j5a0edj2b

1. What is the initialization vector?
2. What are the feedback coefficients of the LFSR?
3. Write a program in your favorite programming language which generates the whole sequence, and find the whole plaintext.
4. Where does the thing after WPI live?
5. What type of attack did we perform?

### Solution

This solution is verified as correct by the official Solutions for Odd-Numbered Questions manual.

1. The first thing we need to do is convert the chosen plaintext “WPI” into binary:

10110 01111 01000


We next need the first three latters of ciphertext converted into binary:

01001 11111 00000


To extrapolate the keystream that encrypted our chosen plaintext, we simply XOR the two:

11111 10000 00100


Given that we know the degree of the LFSR is 6, then the first 6 bits of the keystream must be the initialisation vector:

111111


2. To derive the feedback coefficients, we can exploit our knowledge of $2m$ bits of keystream:

$\begin{array}{c|c} s_{11} & s_{10} & s_9 & s_8 & s_7 & s_6 & s_5 & s_4 & s_3 & s_2 & s_1 & s_0 \\ \hline 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \end{array}$

The following simultaneous equations can be used to derive the feedback coefficients $p_i$:

If we plug in our known values for $s_i$ then we can express this as the following augmented matrix and perform Gauss-Jordan Elimination:

$\left[ \begin{array}{cccccc|c} 1 & 1 & 1 & 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 \end{array} \right]$
$\left[ \begin{array}{cccccc|c} 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 \end{array} \right]$

The matrix is now in reduced row echelon form, and the values $p_i$ can be read directly from the matrix:

$\begin{array}{c|c} p_5 & p_4 & p_3 & p_2 & p_1 & p_0 \\ \hline 0 & 0 & 0 & 0 & 1 & 1 \end{array}$

3. I wrote a python script which can perform many of the operations involved in this attack:

Note: This is not a remotely efficient implementation of an LFSR-based Stream Cipher.

The code above can do everything except perform the Gauss-Jordan Elimination to find the coefficients. This I did by hand. However, since a general algorithm exists, then there’s no reason the code couldn’t be extended to perform the full attack.

The full plaintext is revealed as:

WPIWOMBAT


3. The wombat is an animal that lives in Tasmania and South-Eastern Australia.

4. We performed a known-plaintext attack.