Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question

1 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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