Decrypting Ciphertext with partial Key Fragment using LFSR and Berlekamp-Massey

Question

Edit

Does the state register (the LFSR) always have to remain with 16 bits (I'm assuming yes).

If so, are we shifting the register right by one (lfsr>>1) and inserting the output bit onto the left-most bit (lfsr>>1 | bit<<15) which allows us to wraparound within the same 16-bit address space.

So with this in mind, how does one generate the continuous keystream given:

seed: 1100101001110101

taps: 3, 12, 14, 15

---

Assuming you are given the following information:

Seed: 1100101001110101

Key Fragment: 000100011110101100001101101111101

And the following ciphertext/encrypted stream: 10101011000000010010110011001100101000010101010101010111101111110111010000010011

I am seemingly unable to decrypt the entire text into some ASCII values (UTF-8 decoded). I initially wrote a Berlekamp-Massey implementation and an online calculator to grab the tap positions of the above key fragment, which returned the following polynomial:

$$x^{15} + x^{14}+x^{12}+x^{3}+1$$

Fibonacci LFSR implemented in Rust:

fn next(&mut self) -> Option<(u16, u16)> {
    self.bit = ((self.lfsr >> self.taps[0]) ^ (self.lfsr >> self.taps[1]) ^
                (self.lfsr >> self.taps[2]) ^ (self.lfsr >> self.taps[3])) & 1;

    self.lfsr = (self.lfsr >> 1) | (self.bit << 15);

    if self.lfsr != self.seed {
        Some((self.bit, self.lfsr))
    } else {
        None
    }
}

• The key fragment never appears in the generated key stream, indicating something probably went wrong.
• The decrypted cipher doesn't map to ASCII values, just cryptic UTF-8 symbols.

The Berlekamp-Massey implementation is based off of the following whitepaper - https://www.osti.gov/servlets/purl/12658

And the full code can be found here - https://gist.github.com/JuxhinDB/ef8dac92b5af5de2e365d326b8dbc410

Answer 1

TL;DR:

If you have a similar question, then use the online Berlakamp-Massey algorithm to get the minimal polynomial by providing the given keystream, then get the C++ code from github and then replace your tap positions, seed, and ciphertext and then compile and run.

---

The answer is attraction

How to get it

What is given: We have given the following information;

• Key fragment
• seed
• ciphertext

Attack idea: The key fragment is given to calculate the shortest LFSR that outputs the given key fragment. Once you get the taps, initialize the LFSR with the seed then decrypt the ciphertext stream.

Steps in details;

1. Use Berlakamp-Massay algorithm to find a shortest LFSR (need not to be unique). An online version is used.

2. The output is given as $x^{16} + x^{12} + x^3 + x^1 + 1$

3. As noted on the online site the size of the LFSR is 16 and the tap positions are

   0,1,3,12

     xxxxxxxxxxxxxxxx <-|
     || |       |       |
     ++-+-------+-------|  
     01 3       12
   

4. Initialize the LSFR of size 16 with the seed and this tap positions. Run the LFSR and get the keystream; 11001010011101010101100010111110110000000011011000100011110101100001101101111101

5. X-or the keystream with the ciphertext

6. Convert the plaintext to ASCII to get

   attraction

---

note 1: if you x-or the 16-bit seed with the ciphertext you will get the at. This has a very low probability to contain two letters from the English Alphabet. If we assume that only small English letters are used then the probability is $26^2/256^2 \approx 1.031\%$. This was the actual clue int the question. And, normally, real stream ciphers don't start immediately form the initialization. They step for a certain amount from the beginning.

note 2: A sample C++ code can be found in the github.