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

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

• Comments are not for extended discussion; this conversation has been moved to chat. – Ella Rose Dec 27 '18 at 14:13
• To anyone just joining the bounty and would like to give this a shot, it would be best to go to the chat room above to read further comments and attempts. – Juxhin Dec 30 '18 at 11:12

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 edit this question get the C++ code 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 source of this answer.

• Wow, I completely missed the fact the $x^{16}$ should not be considered one of the tap indexes and in addition to that, the $0th$ index. Thank you very much @kelalaka -- I am quite happy to know that I was not far off. Regarding your 1st note, I came to a similar conclusion, but using that reasoning for this task unfortunately wouldn't have been enough. You have my thanks (and this bounty!). – Juxhin Jan 6 at 13:25
• Yes, the minimal polynomial and characteristic polynomial can be confusing. At first, I thought that the answer should be somewhere in the keystream, and I have to look for $2^16$ possible positions. But luckily, it was in the beginning of the stream. Have fun. – kelalaka Jan 6 at 13:32