encryptionstream-cipher

A known-plaintext attack on an LFSR-based stream cipher

I am reading a book about Cryptography, and I am stuck in a question. I am really trying to solve it for weeks. But I think the problem is I couldn't understand the whole picture. The question was like this :

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

1- What is the degree m of the key stream generator?
2- What is the initialization vector?
3- Determine the feedback coefficients of the LFSR.
4- Draw a circuit diagram and verify the output sequence of the LFSR.

Many thanks for your help to me to understand cryptography and LFSR.

Solution

  • You are referring to Understanding Cryptography by Paar and Pelzi, right? The second chapter can be found online on the Springer site which should be legal given Springer is the publisher.

    I'd say the second list is the ciphertext, i.e. the plaintext XORed with the keystream. The keystream would then be 

        1001 0010 0110 1101 1001 0010 0110
XOR 1011 1100 0011 0001 0010 1011 0001
=   0010 1110 0101 1100 1011 1001 0111

    or 

    0010111 0010111 0010111 0010111

    grouped in blocks of 7 bits. Given theorem 2.3.1 "The maximum sequence length generated by an LSFR of degree m is (2^m)-1" you can guess that the degree might be 3, as the sequence length of the LSFR appears to be 7. Note that the degree counts the internal states of the LSFR and does not refer to the degree of the polynomial. According to formula (2.1) its degree is one less.

    So what you want to calculate is a solution to the equations 

    p(0,0,1)=0
p(0,1,0)=1
p(1,0,1)=1

    for p(s_0,s_1,s2)=p_0*s_0+p_1*s_1+p_2+s_2 and check that rest of the key stream matches this formula, too. Doing this you end up with the following matrix:

    0 0 1 | 0
0 1 0 | 1
1 0 1 | 1

    So p_0=1, p_1=1 and p_2=0. Which does match the rest of the keystream.