6
$\begingroup$

Lets say I have 1000 bytes that are supposedly random. I want to verify to a certain certainty that they are indeed random and evenly distributed across all byte values. Aside from calculating the standard deviation and mean value, what are my options for a robust verification process?

$\endgroup$
  • 1
    $\begingroup$ See here about verifying pseudorandom number generators. You cannot, however, "verify to a certain certainty", since the problem isn't well-posed. $\endgroup$ – Yuval Filmus Dec 8 '16 at 7:11
7
$\begingroup$

You can't. Randomness is a property of the source, not a property of the values you get from that source. In other words, randomness is a statement about the probability distribution, not about some specific values sampled from that distribution; from a finite sample, you can't give a definite answer to your question.

Or, to quote Dilbert:

What you can do is perform some kind of statistical test, with the properties that (a) if it is truly random, it'll probably be accepted, (b) if it is not truly random, it might be accepted or might be rejected (no guarantees). In other words, if the statistical test rejects it, then odds are it wasn't random. However, if the statistical test doesn't reject it, you can't conclude anything -- it might be random, or it just be a good enough mimic to fool that one statistical test. Such statistical tests are often sufficient that they can reject many obviously-bad generators.

If that sounds like the kind of thing you're looking for, look up the DIEHARD test suite and related tools.

See also How can it be detected that a number generator is not really random?.

$\endgroup$
2
$\begingroup$

The best-effort verification is to estimate min-entropy. There are many, many ways to do that, each having their own pitfalls.

One interesting approach is to use algorithms that try to predict the next value using the previous values, as was explored in the paper Predictive Models for Min-Entropy Estimation. The paper also references the NIST Special Publication 800-90b (draft) which covers some methods for estimating min-entropy. You can find more information about random number generation at NIST's Random Number Generation page.

This is all much more relevant to random generators meant to be used in cryptographic contexts.

$\endgroup$
  • 1
    $\begingroup$ Can you elaborate on why you call that "best-effort", or what you mean by that? There are other alternatives, and as far as I am aware, estimating min-entropy isn't necessarily the best of all available alternatives. In many contexts where random generators are used in cryptographic contexts, estimating min-entropy isn't feasible (at least not from looking at 1000 bytes of output from the generator!). $\endgroup$ – D.W. Dec 8 '16 at 20:38
  • $\begingroup$ I'd claim that when people say "random" in the CS context, they usually mean it is not very predictable, which is the same thing as having high min-entropy. Given only a sequence of outputs from a source, it isn't possible to derive the min-entropy of the source, but we can get an approximation (with some error, and some chance of failure) using numerous methods. For the purposes of "verifying randomness", the error and failure chances make min-entropy estimation a "best-effort" technique since it doesn't actually prove anything one way or the other. $\endgroup$ – Extrarius Dec 8 '16 at 20:52

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.