How to prove the security of the PRNG?

Question

Are there any realties tests or criterias that prove the security of the PRNG? What kind of tests or criteria?

Answer 1

We currently have no way to prove that a specific PRNG is cryptographically secure. In fact, we currently cannot prove that there exists a cryptographically secure PRNG (!).

If you scale back the requirement from "mathematical proof" to "something we generally accept", there's still no way for an automated test to verify that a specific output is cryptographically secure. Yes, it can run a series of statistical tests, and verify that, from that perspective, it looks like what we expect a random stream to be. However, that is not sufficient; to be cryptographically secure, we require that someone cannot devise a clever test (using knowledge of how the PRNG works internally) that distinguishes it from random. The hard word (for an automated test) is the word "clever"; automated tests have great difficulties with "cleverness".

Here's a little thought expirement that demonstrates one of the subtleties; suppose I generate a PRNG using AES in counter mode; that is, I pick an initial 128-bit value $N$ and an AES key $k$, and produce the sequence:

$AES_k(N), AES_k(N+1), AES_k(N+2), AES_k(N+3), ...$

If I pick $k$ and $N$ randomly, and keep them secret (and keep the number of outputs within the above sequence to significantly below $2^{64}$), then this is, as far as we know, a cryptographically secure PRNG.

However, suppose I do the same, but instead of picking $k$ randomly, I use a fixed public value. In that case, the sequence is known not to be a CSPRNG; it is easy to test (using two adjacent outputs), whether the output is from this specific PRNG.

Here's the point: publishing $k$ or keeping it secret does not actually change the output. However, even though it doesn't, it does change whether we have a CSPRNG or not.

So, going back to your question: we do have things that we believe are CSPRNG (such as the above AES counter mode with a secret key); why do we believe those? Well, that's because we have clever people (that is, people that have demonstrated skill in finding clever ways to break other CSPRNGs) analyze the PRNGs. It's not an ideal solution (it's possible that there is a way to break it, and our clever people missed it); however it's better than any other way we have.

Answer 2

The best that can be done for a PRNG is to reduce the problem of distinguishing its outputs from random (or predicting them) to some believed-to-be-hard problem. A PRNG based on AES in counter mode can be proven to be as secure as AES in some sense. Similarly a PRNG based on a HMAC-SHA256 can be shown to be as secure as HMAC-SHA256. There are PRNGs based on both in SP 800-90.

A PRNG is deterministic, so it can't provide any security unless it has some secret internal state that is unknown and impractical for an attacker to guess. Even if the PRNG algorithm is secure, the whole PRNG is secure only if it is initialized with an unguessable seed.

Answer 3

The NIST special publication 800-90 series (NIST SP 800-90A, NIST SP 800-90B and NIST SP 800-90C) contain a set of PRNGs and tests for cryptographically secure PRNGs. Unfortunatelly, right now (13/10/2013) the NIST website is down, however you can find copies of the NIST statistical test suite via Google at sites like this one.

Answer 4

How to prove the security of the PRNG?

My best advice would be to start with a statistical test suite like the one NIST describes in "A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications" (PDF).

It’s a battery of statistical tests to detect non-randomness in binary sequences constructed using random number generators and pseudo-random number generators utilized in cryptographic applications. The documentation and software is available at this page of the NIST website.

(If NIST STS doesn’t feel “complete”, you might want to know that other, more diverse test suites exist.)

Those tests are useful as a first step in determining whether or not a generator is suitable for a particular cryptographic application. Yet, you have to keep in mind that no statistical test can certify a generator to be appropriate for any particular use.

Simpler said: statistical testing cannot serve as a substitute for cryptanalysis. For that, you’ll have to dive into the cryptanalysis of random number generators. Cryptanalysis will help you check for potential weaknesses to several attacks (eg: input-based attacks, backtracking attacks, state compromise extension attacks, meet-in-the-middle attacks, etc.) and it can help you optimize the security of your individual RNG in case you detect a flaws which leads to a successful attack.

If you don’t know where to start with cryptanalysis, you might want to check on “Cryptanalytic Attacks on Pseudorandom Number Generators” (PDF). That paper provides some first insights on several attacks and provides some good examples by applying some of those attacks to real-world PRNGs.

In the end, all that will not be able to prove that your PRNG is cryptographically secure… as (up to the time of writing this) no one was able to prove that something like a “cryptographically secure random number generator” actually exists. Yet, if you do your statistical tests (and your RNG passes them) and if you invest a truckload of time to do a thorough cryptanalysis, you might be able to prove that your random number generator resists a (hopefully large) number of attacks – which is about as much as you can do to prove the cryptographic security of a random number generator.

Answer 5

As mentioned, most proofs of PRNG security are really proofs of a protocol that uses some underlying construct. The proofs say, "If the construct can't be broken, then the protocol that uses it can't be broken any easier than that." That makes all these proofs subject to the assumption that the underlying construct (like factoring, quadratic residuosity, etc.) is hard to break.

To address the last part of your question, PRNGs are evaluated in a number of different settings that are meant to mimic real-life attacks they face. Typically, this includes:

• known state attack, where you assume the attacker can peek at the internals of the PRG when output is generated,
• chosen state/input attack, where you assume the attacker can control the entropy updates or even the whole state of your PRG, and
• known key attack, where you assume the attacker knows the key (not the same as the seed, which is thought of more as the initial state) but not the state (current or past)

In each of these settings, algorithms are evaluated for their ability to:

• predict the next output,
• guess previous outputs (a property known as security against a future compromise, or forward security), and/or
• recover the seed

These papers give a formal treatment for security in PRGs:

• eprint.iacr.org/2005/029.pdf (Barak, Halevi, 2005)
• www.iacr.org/archive/eurocrypt2002/23320364/prng.pdf (Desai, et. al., 2002)