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
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 .
- Every message starts with the header WPI.
We observe now on the channel the following message (the fourth letter is a zero):
- 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?
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:
2. To derive the feedback coefficients, we can exploit our knowledge of bits of keystream:
The following simultaneous equations can be used to derive the feedback coefficients :
If we plug in our known values for 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 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:
3. The wombat is an animal that lives in Tasmania and South-Eastern Australia.
4. We performed a known-plaintext attack.