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

- 3 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.10

We conduct a known-plaintext attack on an LFSR-based stream cipher. We know that the plaintext sent was:

1001 0010 0110 1101 1001 0010 0110

By tapping the channel we observe the following stream:

1011 1100 0011 0001 0010 1011 0001

- What is the degree of the key stream generator?
- What is the initialization vector?
- Determine the feedback coefficients of the LFSR.

### Solution

*This solution is verified as correct by the fact that it produces sensible output which can be fed back in for confirmation.*

1. By XORing the ciphertext stream with the keystream, we get the following:

0010 1110 0101 1100 1011 1001 0111

If we arrange this into 7 bit blocks then we can easily see that the key repeats every 7 bits. The period of the LFSR is therefore 7.

0010111 0010111 0010111 0010111

Since the period of an LFSR (with primitive polynomial) is defined by , we can rearrange this to :

Therefore the degree of the LFSR must be 3.

2. The first bits of the keystream are , so therefore the initialisation vector must be:

3. Using the following 3 bits of the keystream (since we require key bits for an attack), we can construct a set of simultaneous equations where the unknowns are the feedback coefficients that produced those next three values:

Using our specific values, we get the following:

This can be converted into an augmented matrix and solved via Gauss-Jordan Elimination:

The matrix is now in reduced row echelon form, which allows the values of the unknowns to be read directly from the matrix. The feedback coefficients of the LFSR are , which is represented graphically as follows:

To double check that our solution is correct, we can run the reconstructed LFSR outselves to be sure that it produces the same keystream:

Given that this LFSR outputs the same keystream, we have proved the correctness of our derived coefficients.