# How to prove the security of the PRNG?

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

-

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.

-
+1, but how about PRNGs such as BBS which are at least reduced to well studied problems? –  mikeazo Oct 9 '13 at 22:34
@mikeazo: same issue; we have no proof that factorization (or any other problem in NP) is actually hard; evidence, yes, but no proof. –  poncho Oct 9 '13 at 22:47
If I'm not mistaken AES-CTR is secure even if $N$ is public and chosen by an adversary, as long as no two counter ranges overlap. –  nightcracker Oct 9 '13 at 22:57
@nightcracker: Yes, AES-CTR is secure if $N$ is public; it is not secure if $k$ is public... –  poncho Oct 10 '13 at 1:04

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.

-

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.

-

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:

-