1
$\begingroup$

I am a bit confused on the metrics that can be applied to the output of (deterministic) pseudo-random number generators. I've run output from many RNGs through ENT. The only metrics that really differ between RNGs declared insecure (e.g. Cs rand()) and those declared as CSPRNGS (e.g. Javas SecureRandom) are the Chi-Square and the corelation coefficient.

My question(s) are/is: how meaningful are these metrics? What other metrics can be measured on the output of an RNG?

Improve this question
$\endgroup$
4
  • $\begingroup$ Can you please be explicit about what you are trying to measure with this metric? $\endgroup$
    – Mike Ounsworth
    Feb 12, 2016 at 23:34
  • $\begingroup$ NIST and the German BSI have tests on PRNG's... $\endgroup$
    – Maarten Bodewes ♦
    Feb 12, 2016 at 23:55
  • $\begingroup$ When recently the flaws in Google Chromes RNG were discovered one could see the non-randomness in a small sample of data (one computer screen). I'd like to know whether there are more sphisticated algorithms for pattern detection than looking at noise generated by the RNG under test. $\endgroup$
    – marstato
    Feb 13, 2016 at 0:06
  • $\begingroup$ I hope that practical cryptographers define "CSPRNG" in basically the same way pseudorandom generators are defined in the cryptographic literature, although their security is probably proven under stronger assumptions. This does not involve any specific "metric". Otherwise, I can't fathom what the term could really mean. $\endgroup$
    – fkraiem
    Feb 13, 2016 at 2:14

1 Answer 1

Reset to default
1
$\begingroup$

It's hard to say anything "meaningful" about an RNG without also talking about the operating system and hardware it's running on. You could have an output stream that looks completely random (ie is free of patterns), but if it gives you the same sequence of numbers each time you run it, it's not very random, now is it? The same is true if an attacker can guess the seed you're going to use. Talking about how the seed is generated very quickly leads you to talking about the operating system and the hardware.

Personally, I don't trust any measure of security that treats an RNG as a black box (ie only looks at the output stream). Detecting patterns in an output stream is a hard problem. Proving that there are no patterns in a finite sequence of numbers is (I suspect) provably impossible. Or more practically, for any given statistical test that you apply to my output stream, I can probably build a weak RNG that passes that test.

I prefer to judge an RNG in a white-box way by looking at:

  1. The quality of the seed. You quantify this by making arguments about the amount of entropy that the system as a whole (RNG + OS + hardware) can gather in the best / worst / average cases.
  2. The quality (and vulnerability-free-ness) of the mixing algorithm. This is hard to quantify, but I want to know that A) their algorithms follows the NIST guidelines for random number generation, and B) that their implementation is bug and vulnerability-free.

Even with full access to the source code / sample hardware, judging those two criteria is hard. Fortunately for me, there are NIST / FIPS certification labs that do this analysis for me, so in practice the question "how good is this RNG?" reduces to "is this implementation on the list?"

Additional thought: because of the way these things tend to gather entropy for their seed, you would probably find that the results of your ENT test would be very different if you ran them as part of boot-up on a headless, networkless Raspberry Pi, rather than on a busy desktop or server that's been up for a while.

Improve this answer
$\endgroup$

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.