2
$\begingroup$

What are the tests which a regular PRNG would fail but a CSPRNG would succeed? Is it just the next-bit test or are there multiple other tests which a PRNG which is not a CSPRNG would fail? Would a PRNG which is not a CSPRNG pass the Chi Square tests?

$\endgroup$
2
  • 1
    $\begingroup$ No, a PRNG may well meet any statistical requirements, i.e. generate well distributed random values. To make it fail you'd have to look at the inner structure and find vulnerabilities there, or possibly calculate the initial seed value. Of course, if the PRNG is sufficiently bad it may fail the tests. If it uses a small enough seed then it possible to show that it is not good by just looping through all possible seed values. $\endgroup$
    – Maarten Bodewes
    Nov 30 '20 at 11:44
  • $\begingroup$ @MaartenBodewes - what about the next-bit test? Why can't it be used $\endgroup$
    – user93353
    Dec 1 '20 at 4:29
4
$\begingroup$

What are the tests which a regular PRNG would fail but a CSPRNG would succeed?

The goal of a PRNG, and the duty of a CSPRNG, is to have an output that can't be distinguished from true randomness (with a significant advantage, by a program that can actually be run). Thus it's a failure of a PRNG, and a capital offense for a CSPRNG, if it does not pass all randomness tests it receives (assumed correct and well used, including correctly interpreting the results, which by nature are uncertain to a degree).

Nevertheless, a few bad PRNGs which fail some generic statistical tests like Ent, Diehard, Dieharder, TestU01, NIST SP800-22 rev 1a. More PRNGs fail only specific tests designed with knowledge of the PRNG design.

A well-designed and well-implemented CSPRNG will, by definition, pass all tests. That's including the above list of tests. We can have a (faint) hope that running some tests in this list disprove that a PRNG is a CSPRNG.

Caveat: that's essentially useless to argue (much less, prove) that a PRNG is a CSPRNG (which requires analysis at the design) or well implemented (which require looking at the implementation, and test vectors). Much like analyzing statistics on winning a lottery is not useful to argue that this lottery system is run honestly.

Addition (as rightly suggested by @SEJPM): We can't stress it too much, don't count on generic statistical tests to find weaknesses in PRNGs, or worse CSPRNGs (rather, count on CSPRNGs to help debug statistical tests). A CSPRNGs requires a sound design, and years of analysis, of its design and/or of the primitive(s) it uses, by smart motivated cryptanalysts. Only after they failed to find a theoretical distingisher do we have a serious candidate CSPRNG.


Would a PRNG which is not a CSPRNG pass the Chi Square tests?

That depends on PRNG and test parameters (that might also depend on the seed used). For many non-crypto PRNGs in actual use, and all CSPRNGs, yes. For others, that depends a lot on if the test is run for a long enough sample, and on if the χ2 test is bidirectional or not.


Why do you need to know the PRNG Design?

In cryptography, adversaries are assumed to know everything about the system attacked except the key (that is, for a PRNG, the seed), by Kerckhoffs's principle. They will design clever algorithms, perhaps dedicated hardware (e.g. the bombe), in order to break the system (that is, for a PRNG, distinguish the output from random, or worse predict future output from past output).

And in practice, that makes a helluva of a difference. It's easy to devise a test that predicts the next outputs of MT19937 knowing earlier ≈19968 bits, using a specifically designed test for that generator. Most tests not specifically designed for the class of generators MT19937 belongs to will give its output a clean bill of health.

Why can't the next-bit test be used to distinguish a CSPRNG from a PRNG without knowledge of the PRNG design?

The next bit test is theoretical. Unlike the 5 families of statistical tests I linked to, it's not a program that can be run to completion on a sample of the output(s) of the PRNG tested.

No practical test on the output of a candidate CSPRNG can confirm it's one.

$\endgroup$
5
  • $\begingroup$ Why do you need to know the PRNG Design? Why can't the next-bit test be used to distinguish a CSPRNG from a PRNG without knowledge of the PRNG design? $\endgroup$
    – user93353
    Dec 1 '20 at 4:28
  • 1
    $\begingroup$ as the answer points out, the next bit test is theoretical, depends on ensembles of arithmetic circuits or probabilistic turing machines. you may need to read up/learn more if you don't understand why your proposal cannot be implemented. $\endgroup$
    – kodlu
    Dec 1 '20 at 8:33
  • $\begingroup$ @fgrieu - thank you for the answer. One more question - Are there any tests which can tell whether a PRNG is a good PRNG or not - I am talking about where it's a good PRNG, not whether it's a cryptographically secure or not. Are there tests which both PRNGs & CSPRNGs will pass. $\endgroup$
    – user93353
    Dec 1 '20 at 12:37
  • $\begingroup$ @user93353: you are on a crypto group, thus a good PRNG is a CSPRNG. All tests can sometime tell that a PRNG is not good/is not a CSPRNG. No test can tell that a PRNG is good. That said, if (for the sake of the argument) I had to rely on tests to choose a single one among unknown PRNGs which design I can't examine, I'd run Dieharder and TestU01, and perhaps (if I can get it to run, never tried) the NIST suite, and pick the slowest of the fast-enough PRNGs that survive. But if I had SHA-256, and performance was not a major issue, I'd just make a simple CSPRNG out of that. $\endgroup$
    – fgrieu
    Dec 1 '20 at 13:31
  • $\begingroup$ @fgrieu - I am asking about a test which can tell if it's a good PRNG even if its not a CSPRNG - a test which shows that the distribution is random. I know this is a crypto group. But I would like to know which test to ignore because its only relevant to non-CS PRNGS. $\endgroup$
    – user93353
    Dec 1 '20 at 17:35

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.