Independent Pseudo Random Generators

Question

Is it sufficient to seed a pseudo-random number generator (PRNG) with two different values to be able to claim that we now have two independent PRNGs? Or is it that we have to use two functionally different generators for that?

Answer 1

The standard crypto engineering approximation of a pseudorandom generator (PRG) $f\colon \{0,1\}^k \to \{0,1\}^n$ for $k \lll n$ is that if you pick two independent uniform random keys $K_0$ and $K_1$, then the outputs $f(K_0)$ and $f(K_1)$ are independent uniform random bit strings too.

This applies to, e.g., the AES-CTR pseudorandom generator $$f(K) = \operatorname{AES256}_K(0) \mathbin\Vert \operatorname{AES256}_K(1) \mathbin\Vert \cdots,$$ provided $n \lll 2^{72}$ to avoid birthday distinguishers. However, it is not the case that simply picking two distinct keys $K_0$ and $K_1$ gives an approximation to two independent uniform random $n$-bit strings $f(K_0)$ and $f(K_1)$ at the expected security level, first because if the adversary knows the keys $K_0$ and $K_1$ then there's nothing random to the adversary, but also because even if the two keys merely have a relation known to the adversary, then the standard AES-256 related-key attacks of Biryukov and Khovratovich may apply to enable an attacker to distinguish $f(K_0)$ and $f(K_1)$ from two independent uniform random $n$-bit strings faster than generic attacks.

On the other hand, you can often use a pseudorandom function family (PRF) instead of a pseudorandom generator to get multiple independent strings out of a single key. For example, you can split the input to AES256 in the above construction into a 64-bit string index $i$ and a 64-bit block counter, and define $$F(K, i) = \operatorname{AES256}_K(i \mathbin\Vert 0) \mathbin\Vert \operatorname{AES256}_K(i \mathbin\Vert 1) \mathbin\Vert \cdots.$$ Then, as long as the total volume of data you generate from $F$ with a single key is much less than $2^{72}$ bits, $F(K, 0)$ and $F(K, 1)$ are approximately independent uniform random bit strings, as long as $K$ is a uniform random $k$-bit string not used for anything except an $F$ key.

All this depends on $f$ or $F$ actually being cryptographically secure, of course. If you use a linear congruential generator, or the Mersenne twister, you're dead in the water. But standard PRFs like ChaCha or KMAC, or PRPs (pseudorandom permutation families) like AES, are conjectured to be secure for the above ‘CTR mode’ construction of $f$ and $F$.

Obviously, in a strict probabilistic interpretation, it is not possible to get two independent uniform random strings of $n > k$ bits as a deterministic function of a uniform random string of $k$ bits. To formalize this (in the concrete setting), we quantify the adversarial advantage of a random algorithm $A\colon \{0,1\}^n \to \{0,1\}$ that tries to tell whether its input was drawn from the output of $f$ or not, defined as $$\operatorname{Adv}^{\operatorname{PRG}}_f(A) = |\Pr[A(f(K)) = 1] - \Pr[A(U) = 1]|,$$ where $K$ is a uniform random $k$-bit string and $U$ is a uniform random $n$-bit string. We then try to set a very small upper bound on $\operatorname{Adv}^{\operatorname{PRG}}_f(A)$ for all $A$, either by conjecturing it of $f$ as a primitive and enticing a lot of cryptanalysts to spend effort on it, or by building $f$ out of a primitive that cryptanalysts have already spent effort on and showing how a distinguisher for $f$ as a PRG can be used to construct an efficient algorithm to break the primitive.

(To extend this to the asymptotic setting where complexity theorists like to hang out, we consider a family of functions $f_k\colon \{0,1\}^k \to \{0,1\}^{p(k)}$ for some polynomial $p$, and try to show that $\operatorname{Adv}^{\operatorname{PRG}}_{f_k}(A) < \epsilon(k)$ for some negligible function $\epsilon$.)

Answer 2

If you are using a cryptographicly secure PRNG with a sufficiently large seed. Then it is expected to be infeasible to detect a relationship between the random stream output. If you find two carefully crafted seeds where the output streams then have some clear relationship it would be considered a (mild) weakness in the PRNG, and much more so with random seeds.

Answer 3

Yes this is done all the time with one generator. After all there are only a few good /recommended generators out there for cryptographic purposes.

There's a bioinfomatics paper that might be of interest. Good Practice in (Pseudo) Random Number Generation for Bioinformatics Applications suggests some values to the maximum run length of a PRNG. Not strictly crypto, but I've not seen anything else. Again not crypto, but there might be more guidance at CERN regarding their generators. There's a lot of stuff on that site.

In summary, it says that Knuth recommends a max. output of states /1000. However there is also a much more conservative limit of (states)^(1/3). Some some cryptographers have suggested using half of the bits of state as long as that is still of the order of 128 bits to prevent a brute force recovery of the seed. Although that seems to be creeping up to 256 bits, or even recommended by NIST these days.

Using the most conservative estimates from above (cube root of state), we get maximum runs of /dev/random's (ChaCha20) output of ~10^51 and CryptGenRandom's (RC4 + SHA1) output of ~10^205.

In conclusion there doesn't seem to be a firm best practice. This question seems to be a form of how random is random? That's always going to be difficult to answer.