1
$\begingroup$

I'm facing the problem of implementing pseudo random bit generator (PRBG) on a very low power device. NIST.SP800-22 "Statistical test suite for Pseudo Random Generators" suggests a suite of 15 tests for randomness.

  • Is there a way to use those tests as "randomness measures" except from pass / fail?

That is, suppose you want to do changes in your random generator, and to measure, whether you improved the randomness or not. The NIST suite suggests a way to decide whether you are random or not, but its hard to extract the information of "improvement": For two different algorithms, it may happen that for some tests the first gives higher p-value, for other tests the same PRBG gives lower p values, although both pass all tests. So'

  • is there some "measure of amount of randomness" test, or or how can NIST tests turn to be such?
Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ If one passes all tests, then you can increase the thresholds. Also, increasing the data size and sample size may help to distinguish. $\endgroup$ – kelalaka Aug 12 '20 at 8:44
  • $\begingroup$ The question is whether the threshold is a measure for the "quality of the randomness", as for some tests (of the 15) it becomes better, for others it become worse, there is no consistency among the various tests results... $\endgroup$ – Evgeni Vaknin Aug 12 '20 at 9:05
  • $\begingroup$ My advice is to disregard NIST SP800-22 or similar tests as a tool for defining a PRNG; because attempting that has a fair chance to lead to a PRNG that pass these tests, yet is terribly weak from a cryptographic standpoint. Rather, the choice should be for something that fits the requirements in term of resources used and thru-output, and has withstood some analysis. For a silicon or generic VHDL implementation, I'd consider A5/1 with larger registers, or Trivium. $\endgroup$ – fgrieu♦ Aug 14 '20 at 12:00
2
$\begingroup$

The various nist tests look for patterns which should not be present in random data. For any such pattern, e.g imbalance, repetition etc. you can ask youself what is he likelyhood of this strength imbalance or worse occuring in random data. this is the pValue.

If we toss a coin multiple times we can count heads and tails. The closer they are to even the better. We can quantify this as probability. We then look at longer sequences and also expect them to show up more or less with equal frequency and again we can calculate pValue to quantify how likly discrepencies found are to be chance. Most Nist tests already come with this built in.

We also like to analyze the cycle size of PRNGs even when they are too long to detect in a quick black box test this is another measure of "randomness".

Remember these tests are not sufficient for a PRNG to be secure. And though failing any means the stream is distinguishable from random it may still be decent for some cryptographic operations (Solitaire cipher as an example of a biased yet reasonably secure stream cipher).

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.