This is from the transcript of Dan Boneh's Coursera Crypto course
https://www.coursera.org/learn/crypto/lecture/mQAkP/real-world-stream-ciphers
So it turns out this is easy to break in time roughly two to the seventeen. Now let me show you how. So suppose you intercept the movies, so here we have an encrypted movie that you want to decrypt. So let's say that this is all encrypted so you have no idea what's inside of here. However, it so happens that just because DVD encryption is using MPEG files, it so happens if you know of a prefix of the plaintext, let's just say maybe this is twenty bytes. Well, we know if you XOR these two things together, so in other words, you do the XOR here, what you'll get is the initial segment of the PRG. So, you'll get the first twenty bytes of the output of CSS, the output of this PRG. Okay, so now here's what we're going to do. So we have the first twenty bytes of the output. Now we do the following. We try all two to the seventeen possible values of the first LFSR. Okay? So two to the seventeen possible values. So for each value, so for each of these two to the seventeen initial values of the LFSR, we're gonna run the LFSR for twenty bytes, okay? So we'll generate twenty bytes of outputs from this first LFSR, assuming—for each one of the two to the seventeen possible settings. Now, remember we have the full output of the CSS system. So what we can do is we can take this output that we have. And subtract it from the twenty bites that we got from the first LFSR, and if in fact our guess for the initial state of the first LFSR is correct, what we should get is the first twenty-byte output of the second LFSR. Right? Because that's by definition what the output of the CSS system is. Now, it turns out that looking at a 20-byte sequence, it's very easy to tell whether this 20-byte sequence came from a 25-bit LFSR or not. If it didn't, then we know that our guess for the 17-bit LFSR was incorrect and then we move on to the next guess for the 17-bit LFSR and the next guess and so on and so forth. Until eventually we hit the right initial state for the 17-bit LFSR, and then we'll actually get, we'll see that the 20 bytes that we get as the candidate output for the 25-bit LFSR is in fact a possible output for a 25-bit LFSR. And then, not only will we have learned the correct initial state for the 17-bit LFSR, we will have also learned the correct initial state of the 25-bit LFSR. And then we can predict the remaining outputs of CSS, and of course, using that, we can then decrypt the rest of the movie.
I don't understand what he means by the sentence which I have bolded - "Now, it turns out that looking at a 20-byte sequence, it's very easy to tell whether this 20-byte sequence came from a 25-bit LFSR or not."
How do you tell this whether the 20-byte sequence came from a 25-bit LFSR?
