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?


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

Courtesy of Gregory Kesden

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

  • $\begingroup$ So CSS is a form of DRM, which in general (DRM), seems to generate a large amounts of scrutiny. Is there a good reason for this? Is it because AACS also failed? $\endgroup$
    – Anan
    Sep 17, 2019 at 16:34
  • $\begingroup$ @Anan some need links. $\endgroup$
    – kelalaka
    Sep 17, 2019 at 16:36
  • $\begingroup$ My browser cache clears when I close my tabs (I probably should have bookmarked for reference), but when I was searching around for info on CSS there were mentions of inherent flaws (but no super heavy details) in DRM as a whole. They were on google scholar, I do remember the name Jonker if that helps, it was an amusing name to say. Can't seem to find the exact ones I was reading through, Jonker seems to bring up a lot of identity based DRM proposals however. $\endgroup$
    – Anan
    Sep 17, 2019 at 16:43
  • $\begingroup$ en.wikipedia.org/wiki/Advanced_Access_Content_System#Security $\endgroup$
    – kelalaka
    Sep 17, 2019 at 16:45
  • $\begingroup$ always been told never to rely on wiki, but as it stands both were seemingly initially broken by key extractions. Also the line "The AACS key extractions highlight the inherent weakness in any DRM system" indicates the all DRM systems are vulnerable to some form of key extraction? Or were you saying that the flaw is that some DRM need links, and I misread the whole thing? $\endgroup$
    – Anan
    Sep 17, 2019 at 16:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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