Building Key Streams from PRNGs

Question

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.

Answer 1

• 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
TO: Name_of_the_Receiver

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.

Answer 2

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}}}$$