4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I guess this will depend on what you mean with "independent". Of course with a secure PRNG and two different seeds they would run independently. However, you might still have to take into account that you can reach a cycle. Usually that would be computationally impossible because the size of the cycles are huge due to the size of the state - but that doesn't make it theoretically independent. And when it comes to functional different: how much different do they need to be? Just XOR'ing all the output bits with 1 doesn't seem enough to me. $\endgroup$ – Maarten - reinstate Monica Jan 21 '18 at 16:45
2
$\begingroup$

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$.)

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is there a criteria for "sufficiently large" and "carefully crafted" seeds for a cryptographically secure PRNG to be producing samples that are independent across the two streams? $\endgroup$ – robinw Jan 21 '18 at 4:46
  • $\begingroup$ Large enough for it to be infeasible to brute force. If the inner state is large enough we can ignore birthday paradox and depending on strength of attacker I would recommend at least 100 bits. Possibly more for a nation-state actor brute-forcing your random seed. $\endgroup$ – Meir Maor Jan 21 '18 at 4:53
  • $\begingroup$ By carefully crafted, I said it is possible a PRNG could have a weakness where related weak seeds produce related streams but this would be weakness requiring carefull cryptanalysis to find. I don't actually know of such an example. $\endgroup$ – Meir Maor Jan 21 '18 at 4:55
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The maximum run length shouldn't apply to ChaCha20 since it uses a PRF and not a PRP. $\endgroup$ – forest Jan 8 at 9:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.