3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – Ella Rose Dec 27 '18 at 14:13
  • $\begingroup$ 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. $\endgroup$ – Juxhin Dec 30 '18 at 11:12
1
+100
$\begingroup$

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 output the given key fragment. Once you get the taps, initialize the LFSR with the seed then decrypt the sequence.

Steps in details;

  1. Use Berlakamp-Massay algorithm to find a shortest LFSR (need not to be unique). 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 16 and the tap positions are

    0,1,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.

$\endgroup$
  • $\begingroup$ 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!). $\endgroup$ – Juxhin Jan 6 at 13:25
  • 1
    $\begingroup$ 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. $\endgroup$ – kelalaka Jan 6 at 13:32

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.