Can a PRNG with a fixed amount of entropy always be detected?

Question

Given a fixed seed (i.e. no ongoing source on entropy), is there (practically or theoretically) any PRNG algorithm that can generate an infinite sequence of random numbers such that an observer cannot detect that it is a PRNG rather than a genuinely random source ?

All widely adopted cryptographically secure PRNGs seem to use entropy collectors to supplement, but it's not clear if that's actually a required for any CSPRNG.

The reasoning behind this question is: If a hardware or software RNG has been compromised such that it's seeded with a known key and the RNG doesn't use any additional real entropy source, will there always be an external method of detecting that it's not a real random source.

Answer 1

No, there is no reliable way to detect such shenanigans (through external testing), if the adversary is sufficiently sophisticated and has the power to embed backdoors in the hardware you are using.

If the PRNG is specified to be a deterministic algorithm, then in principle one can run the PRNG on a known key and compare its output against the output from an independent implementation. NIST calls such a PRNG a "deterministic random bit generation" (DRBG) algorithm. In effect, you can use black-box testing of it to check that it seems to be working correctly, under testing conditions.

However, there are some major shortcomings in this testing-based methodology for checking the PRNG implementation. Just because the hardware works correctly under test conditions doesn't necessarily mean it will work correctly when you need it to.

One problem is that there's no way to verify that the hardware is actually deterministic. For instance, the hardware might behave correctly almost all of the time, except that under certain special environmental conditions, it behaves incorrectly. Those special environmental conditions might be arbitrarily hard to find during testing: e.g., the backdoor might be activated immediately after receipt of a network packet containing a magic 128-bit value (or some other "secret knock"). There's basically no good way to detect this kind of backdoor with black-box testing. Therefore, in practice, if you're concerned about backdoors in the hardware, you're not gonna be able to verify that the hardware PRNG is secure merely through external testing.

This problem is not limited to PRNGs; this problem is universal. This is true of all the hardware you use for computation. If your CPU has a backdoor, you're hosed -- period. There's no good way to verify that your CPU is free of backdoors, through external methods. That's life.

Answer 2

If one had a black box which implemented a good CSPRNG which was initialized with 256 bits of pure entropy and never leaked information about its state through any side channels, such a box would for all practical purposes be as secure as a source of perfect randomness.

If the initial quantity of entropy were lower (e.g. only 64 bits), then it may be possible to mount brute-force attacks on the output of the generator, but 128 bits would make such attacks essentially intractable, and 256 bits would make them impossible in the absence of side-channel leakage or cryptographic weaknesses. On the other hand, if there is any side-channel leakage that would occasionally make it possible to infer something about the state of the CSPRNG, such leakage may totally undermine the secrecy of all future output, and possibly past output as well.

Mixing in a certain amount of new entropy on an ongoing basis limits the damage caused by side-channel leakage. More importantly, adding in entropy in sufficiently-large chunks will ensures that even if an attacker managed to capture the state of the generator at some point in the past, an attacker won't be able to make useful inferences about the generator's state after new entropy is added.