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

- 7 mins- Return to index
- Exercise 2.1
- Exercise 2.2
- Exercise 2.3
- Exercise 2.4
- Exercise 2.5
- Exercise 2.6
- Exercise 2.7
- Exercise 2.8
- Exercise 2.9
- Exercise 2.10
- Exercise 2.11
- Exercise 2.12

## 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

- What is the initialization vector?
- What are the feedback coefficients of the LFSR?
- Write a program in your favorite programming language which generates the whole sequence, and find the whole plaintext.
- Where does the thing after WPI live?
- 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:

The following simultaneous equations can be used to derive the feedback coefficients \(p_i\):

\[s_5p_5 + s_4p_4 + s_3p_3 + s_2p_2 + s_1p_1 + s_0p_0 = s_6\] \[s_6p_5 + s_5p_4 + s_4p_3 + s_3p_2 + s_2p_1 + s_1p_0 = s_7\] \[s_7p_5 + s_6p_4 + s_5p_3 + s_4p_2 + s_3p_1 + s_2p_0 = s_8\] \[s_8p_5 + s_7p_4 + s_6p_3 + s_5p_2 + s_4p_1 + s_3p_0 = s_9\] \[s_9p_5 + s_8p_4 + s_7p_3 + s_6p_2 + s_5p_1 + s_4p_0 = s_{10}\] \[s_{10}p_5 + s_9p_4 + s_8p_3 + s_7p_2 + s_6p_1 + s_5p_0 = s_{11}\]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:

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

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.