Understanding LFSR stream ciphers and the content scrambling system

Question

I'm a little confused over how exactly Linear Feedback Shift Registers (LFSR) work, I kind of get it, but not really, can someone help me understand it? I know it XORs bits in a loop against some mask, how is the shuffling defined?

A content scrambling system is a synchronous stream cipher made from 2 LFSRs of different lengths, one with 17 bits and the other with 25 bits. If a 40 bit key is loaded into the LFSRs, 2 bytes into the first LFSR and 3 bytes into the second remaining bits in all set to 1. The outputs are combined to produce the keystream.

How would I go about finding the max period of each LFSR? Is it as simple as $2^d-1$ (simple ($2^{17})-1=131071$ and ($2^{25})-1=33554431$) or is it a little more complex?

Why does the content scrambling system use different LFSR lengths, why must it be 17 and 25 and not something different?

How would I go about brute forcing it, and what would the complexity of the brute force attack be?

If i simply XOR the two LFSR outputs, what would be the result be like (I'm assuming there would be some sort of way to identify information out of it)? Would a known plain text attack prove effective?

Answer 1

• How would I go about finding the period of each LFSR?

If the polynomial generating an LFSR is primitive polynomial then the LFSR has maximal period, $2^\ell-1$ where $\ell$ is the length of the LFSR. It is general practice that they are chosen as primitive polynomials. In your case periods are $2^{17}-1$ and $2^{25}-1$ for $L_1$ with length 17 and $L_2$ with length 25, respectively.

In LFSR's there might be a negligible chance that the key is all-zero then the stream will be all-zero. To eliminate an all-zero case, the fourth-bit is injected with 1 for $L_1$ and $L_2$.

• Why does the content scrambling system use different LFSR lengths?

If the LFSR lengths and taps are the same, then there might be the case that the two LFSR produce the same stream to cancel each other. We can call this a weak-key.

More importantly, an LFSR is linear and linear systems are not secure in Cryptography. You need to add non-linearity. One way to achieve this is by Filtering the states of an LFSR with a non-linear function or using a combining function like in CSS.

In CSS the combining function is 8-bit adder. After 8-clock, which produce 8-bit per LFSR, these 2 bytes are added. The carry is saved for the next addition.

Since addition is non-linear in bit case, the non-linearity is achieved. Of course for security non-linearity is necessary but not sufficient. A good read for LFSR with non-linear combing functions is the correlation attack. A famous article is Decrypting a class of stream ciphers using ciphertext only by Siegenthaler (pay-walled). He showed that a correlation attack can be performed on non-linear combiners.

• How would I go about brute-forcing it, and what would the complexity of the brute force attack be?

To execute a brute force, you need keystream from the cipher. Assuming that you have;

• $2^{40}$- the keyspace is not hard to reach in 1996. The reason for low keyspace is well stated in Wikipedia;

  At the time CSS was introduced, it was forbidden in the United States for manufacturers to export cryptographic systems employing keys in excess of 40 bits

• In 1999 Stevenson showed 3 attacks including brute-force on CSS.

• Even DES with $2^{56}$- keyspace can be easily searched with special hardware ^§,‡ or cluster during 1999s.

• There is also a correlation attack that recovers the key with $2^{16}$ complexity.

• One can also, attack with guessing $L_1$ and determing the $L_2$ with $2^{16}$ complexity

• If I simply XOR the two LFSR outputs, what would be the result be like (I'm assuming there would be some sort of way to identify the information out of it)?

It will be completely linear and will be much more easy to attack; first, produce algebraic equations then solve by Gaussian elimination. As explained before, the basic countermeasure is adding non-linearity.

• Would a known plain text attack prove effective?

You need a keystream to attack therefore you need to know the plaintext.

---

^{§ RSA DES challange in 1997}

^{‡ DES hardware machines since 1997}