Brute force against computational security

Question

One-time pad is secure under brute force with respect to either of the definitions \begin{align} \Pr[M = m] &= \Pr[M = m | C = c]\\ \Pr[C = c | M = m_0] &= \Pr[C = c | M = m_1] \end{align}

basically because the key and message spaces are the same, and $\oplus$ is closed under these spaces.

Given the argument above, I don't understand precisely how computationally secure schemes are compromised under brute force. In particular, how would any of the two equations above be violated given the scheme $$\mathsf{Enc}(m, k) = m \oplus G(k),$$ where $G$ is a pseudorandom generator.

Answer 1

For a (fixed-length) cipher to meet your first condition, it needs to be the case that it's no easier to guess the plaintext if you have the ciphertext than it is to guess the plaintext without the ciphertext. Now, suppose I send a random 1024-bit string XORed with $G(k)$ for some 128-bit $k$ and computationally secure $G$. The probability that my message is $0\ldots0$ is exactly $2^{-1024}$. I encrypt my message with a 128-bit key selected uniformly at random from the space of 128-bit keys to get $c$. Now suppose you intercept $c$. You know it's encrypted with some key $k$; you know there are $2^{128}$ such keys. That means that there are only $2^{128}$ possible decryptions -- at most 1 per key. This is why the keyspace of a perfectly secure scheme must be at least as big as the message space: knowing the ciphertext means that the number of possible messages is reduced to the number of possible keys, and if there are fewer keys than messages we've eliminated a lot of messages. That means that knowing "this ciphertext can decrypt to $m$" tells us that it's much more likely to be $m$ than we had suspected beforehand.

If $K=k$, then $M=c\oplus G(k)$. So, $$\Pr[M=c \oplus G(k)|C=c] \ge \Pr[K=k]=2^{-128}\ne 2^{-1024}$$ for any $k$. Suppose, for instance, that you try $k=1\ldots1$ and find that $c\oplus G(k)=0\ldots0$. You now know that $$\Pr[M=0\ldots0|C=c]\ge\Pr[K=1\ldots1]=2^{-128}\ne 2^{-1024}=\Pr[M=0\ldots0]$$ after a very quick computation (just one evaluation of $G$). That means that even with a computationally secure cipher, given $c$ an attacker can easily find a message $m$ such that $\Pr[M=m|C=c]\ge 2^{|k|}$ -- specifically, $\mathsf{Dec}(c,0...0)$. And that violates $\Pr[M=m|C=c]=\Pr[M=m]$ in a single evaluation of $\mathsf{Dec}$.

Answer 2

If G is PRNG, there are two issues:

First, not all PNRGs are cryptographically secure. You have to use a cryptographicaly secure PRNG, a CSPRNG. If the PRNG was not cryptographically secure, one might, for example, perform a known-plaintext attack.

Second, if $n = |k|$, we have only $2^n$ possible keys. For a given cryptotext, there are only $2^n$ possible plaintexts. Theoretically, this provides some information: it changes the probabilities. Some possible plaintexts $m$ of the length are impossible (i.e. there is no key $k$ such that $d_k(c) = m$). The other plaintexts are thus more probable.

Assuming there is not a pair of keys $k_1, k_2$ such that $k_1 <> k_2 \wedge d_{k_1}(m) = d_{k_2}(m)$, then $Pr[M = m] = 2^{-|m|}$, but $Pr[M = m| C = c] = 2^{-min(|k|, |m|)}$. For $|k| < |m|$, i.e. when the key is shorter than the plaintext, these probabilities will differ.

More practically speaking, attacker often knows format of the data or the data maybe contain a hash.

Of course, if $n$ is large enough, then exhaustive search is virtually impossible. In fact, this scheme is used: It is called a stream cipher. (The definition of a stream cipher might be slightly different, but it is virtually the same.)

Answer 3

Since this question topic is about OTP and random number generator let me add my RNG class description as an answer here. It may be of use for you...

There are 2 main classes of RNGs (Random Number Generators): Deterministic and Non-Deterministic.

Deterministic RNGs are:

PRNG (Pseudo Random Number Generator)

CSPRNG (Cryptographically Secure Pseudo Random Number Generator)

Non-Deterministic RNGs are:

CSRNG (Cryptographically Secure Random Number Generator), not to be confused with CSPRNG!

TRNG (True Random Number Generator)

PRNGs are useful for generating good random numbers for any application (e.g. lotteries) except for OTP keys and encryption where PRNGs are useless and not recommended, because a) the attacker only requires the seed (init vector, usually a single 32-bit longint or 64-bit integer number) to generate the whole sequence of random numbers and b) only if the attacker knows a sequence of generated random numbers he can mathematically compute the next random numbers for that sequence or even derive the seed number from them!

TRNGs are unique and very useful for encryption, because they are not required to work with seeds or random IV (Initialisation Vectors)! A TRNG usually produces an infinite stream of random numbers (bits or bytes for that matter) which are generated not by software but by some outside random source.

The outside random source can be anything from radioactive decay, atmospheric noise, white, brown or pink noise from a TV set, static interference from hardware components (such as USB or computer chips) or in the simplest way from keystrokes pressed by a human source, as presented in my topic True Random Number Generator by Milliseconds per keystroke (TRNG-Kms). The same can be done with mouse movements to generate truly non-determinstic numbers. "Non-deterministic" means truly random! And it does not require seeds or other intialisation vectors as mentioned.