Building Key Streams from PRNGs

I am reading an intro book about cryptography and the author tries to explain why using pseudo random number generators is vulnerable.

Given PRNG equation;

\begin{align} S_0 &= \text{seed}\\ S_{i+1} &\equiv A\cdot S_i + B \mod m, i = 0,1,\ldots \end{align}

where we choose $$m$$ to be 100 bits long and $$S_i,A,B \in \{0,1,\ldots,m−1\}.$$ Since this is a stream cipher, we can encrypt

$$y_i \equiv x_i + s_i \mod 2$$

Further in the text:

But Oscar can easily launch an attack. Assume he knows the first 300 bits of plaintext (this is only 300/8=37.5 byte), e.g., file header information, or he guesses part of the plaintext. Since he certainly knows the ciphertext, he can now compute the first 300 bits of key stream as: (Equation 1) $$s_i \equiv y_i + x_i \mod m, \; i=1,2,\ldots,300$$

There are several things about the paragraph above that I don't understand.

• Firstly, by what mechanism could Oscar gain the first 300 bits of plaintext? It makes little sense for Alice (the person who tries to securely communicate with Bob) to send encrypted and plain text together.
• Is there a situation this happens?
• How exactly could Oscar predict the word and location of cyphertext?

Secondly, I don't understand how Equation 1 was derived?

I appreciate any help.

• Firstly, by what mechanism could Oscar gain the first 300 bits of plaintext? It makes little sense for Alice (the person who tries to securely communicate with Bob) to send encrypted and plain text together.

This is called a Known-Plaintext Attack (KPA). In some real-world examples, this attack makes sense. Also, we want our cipher to resist to KPA, we don't rely on attackers not being able to find known-plaintexts.

Why would Alice send the plaintext together with ciphertext? If so, what is the aim of encryption?

• Is there a situation this happens?

This is taken from Mark Burnett's answer

Example: We saw this with the old pkzip encryption method. In this case if you had any of the unencrypted files in the archive, you could use that to obtain the key to break the rest.

Also, in some militaries, the message must be started with

FROM: Name_of_the_Sender


If you are intercepting the encrypted messages, this means that you know at least the first line plus 3 more characters from the plaintext.

• How exactly could Oscar predict the word and location of cyphertext?

If you know the context, you can guess about the plaintext. Then you need to solve the equations for position $$i$$ to get the key. Once a candidate key is found, decrypt the rest of the ciphertext to see that is is not a false positive key. If false-positive, try next guess, if not wonderful.

Cryptanalysis is not an easy job but once successful gives lots of pleasure.

• I see. Thank you! Also every html page would start with <!DOCTYPE>. DO you have an idea from where equation 1 came? – sanjihan Sep 20 '19 at 12:06
• From the PRNG equation. could you check my $LaTeX$ edits? – kelalaka Sep 20 '19 at 12:10
• In this context, $x_i$ is plaintext, $y_i$ is ciphertext, and $s_i$ is the key stream. – kelalaka Sep 20 '19 at 19:40
• One Property for stream cipher is to have unpredictible PRG. given first 'i' bits of PRG , if an attacker can predict rest of the bits then PRG is not secure. if attacker knows few plaintext bits For ex. SMTP start with From: then he can simply XOR the cipher text with plaintext and it can get few bits of PRG, then he can predict the rest of the bits. once he gets it then he can recover plaintext. – SSA Dec 17 '20 at 13:50
• @SSA thanks, and that is generally true, however, this question is already defined an ill PRNG that can be solved to reveal A and B work known-plaintext attack that the OP missed to see. This question is not based on the properties of the PRNGs. – kelalaka Dec 17 '20 at 14:01

The generator you have shown above is linear congruential generator and it is a weak PRG.

-Given a few sequences, one can easily predict the next $${s_i}$$ Look at this link. https://research.nccgroup.com/wp-content/uploads/2020/07/randomness.pdf where it solves for a and b in the form of sequences. $${a= \frac{x_{n+2}-x_{n+1}}{x_{n+1}-x_n} }$$ and $${b= \frac{x_n \cdot x_{n+2}-(x_{n+1})^2}{x_n-x_{n+1}}}$$