0
$\begingroup$

Is there a straightforward way to employ NIST Statistical Test Suite for testing a biased generator (e.g. with 0.6 probability of 1)? By straightforward way I mean one not requiring nontrivial code modification.

$\endgroup$
0
$\begingroup$
  1. Please note that official test suite is long unmaintained and known to be buggy, not fully consistent with its documentation etc. There are some reimplementations (I can recommend the reimplementation made by David Johnston in Python, but maybe some other is even better) which should be probably the way to go.
  2. AFAIK the tests mostly just try to verify that input numbers used in given way give mostly results in given range expected for truly random numbers. You could possibly use exactly the same tests, just put in another expected ranges of results, as for biased generator the expected ranges are different. That's simple modification from programmer's viewpoint, but actually computing (or just measuring from simulations?) what are the new proper ranges could turn out to be a considerable (math?) work.
  3. And of course, the crucial question is why do you want to actually use the test suite and why do you consider the tests chosen by NIST to be the ones that should be used to evaluate the generator. The consensus today is probably that "universal" test suites are of limited use when it comes to cryptographic RNG, as any of them can check just limited amount of possible non-random patterns. The tests included in the batteries are just trying to cover most common non-randomness, so you can effortlessly prove many badly designed generators to be indeed bad. Once you are trying something more, like proving some generator to be actually good, or trying to understand some generator better, the situation is different. You should already know something non-universal about your generator (like that it is biased and at least some hypothesis why it is biased) and you should probably design your own tests based on your knowledge and check NIST suite just for inspiration.
$\endgroup$
  • $\begingroup$ Thank you for a detailed answer! My goal here is not to prove correctness but to find vulnerabilities in a generator which I suppose to be far from perfect. This is why I decided to start with test batteries (starting with NIST as a result of lack of experience in the field). However, the problem is that I don't have direct access to the generator. I can consume its output only as a mapping of randomly generated fixed size series of uniformly distributed bits to single bit values with some unknown but certainly trivial function (the source of the bias in the probability). $\endgroup$ – Anton Dmitriev Nov 5 '20 at 17:37
  • $\begingroup$ The idea of finding new ranges by means of simulation looks great to me! $\endgroup$ – Anton Dmitriev Nov 5 '20 at 17:38

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.