3
$\begingroup$

We need to verify two claims about a set of numbers:

  • They are random
  • They are unique in the set (the set is about 200 billion (2TB bin storage))

Supposedly, the numbers were generated by a TRNG (based on a radiation detector). The TRNG itself is a PCI Express card (which we do not have yet) and is probably a TRNG feeding a CSPRNG.

What ways are there to verify the claims? For randomness there are the NIST and other specs and tools.

But how can one tie a verification of the first claim to verifying the second (uniqueness in the set)? Keep in mind that the output of the TRNG has almost certainly been filtered from duplicates. That is most probably going to break the randomness tests.

$\endgroup$
  • $\begingroup$ Can you explain your reasoning for "Have in mind that the output of the TRNG have almost certainly been filtered from duplicates. That is most probably going to break the randomness tests."? I don't follow why that would break randomness tests if we would assume that the numbers in the set are truly random numbers. $\endgroup$ – AleksanderRas May 15 at 12:56
  • $\begingroup$ The requirement for the set is the numbers to be both random and unique. And in a true random set of numbers uniqueness is not a requirement. e.g. i can have repeating numbers. I am not competent enough to say that having no repeating numbers in a set will make it trully random. $\endgroup$ – zeridon May 15 at 13:04
  • 1
    $\begingroup$ In your use case: what is a number ? I.e. which size do number have? $\endgroup$ – Ruggero May 15 at 14:51
  • 1
    $\begingroup$ Also: 1) It's very unlikely to be a radiation detector, unless it's running inside Chernobyl. Hotbits is the only one I know and that would take 63 years to make 2TB. 2) A TRNG never feeds a CSPRNG. It's either an entropy source feeding a CSPRNG/extractor, or a TRNG. 3) You can't have filtered random output as it wouldn't be random in the uniformly distributed sense used here. $\endgroup$ – Paul Uszak May 17 at 11:52
  • $\begingroup$ Adding to Squeamish's answer, which is correct, you can prove from 1st principles that radiation is of a random distribution, but you'll need to prove there's not a bias source that is overriding the input. Atmospheric noise is random, and you can get cards with different transition metal isotopes. Be sure to read up on the card's specifications of the source. $\endgroup$ – b degnan May 17 at 16:56
4
$\begingroup$

There is no such thing as a random number and as such it is a category error to attempt to verify whether a particular set of numbers is ‘random’. There are random generators of numbers; the relevant question is whether you—or, more importantly, a well-funded adversary—can predict the output when you don't know it a priori. To answer that, you must:

  1. Study the physics of mechanism inside the device. Hire the world's best theoretical physicists to find the best model with humanity's current understanding of physics for how the mechanism behaves.
    • What verification can you do here? You, or the experimental physicists you hired, can devise experiments to rule out alternative hypotheses for how physics might work. But there's nothing at this stage that you can meaningfully do to the output of your RNG device.
  2. Study the engineering of the device. Hire competent engineers to determine whether there are ways for the device to fail, and if so, model how it will behave when it does fail.
    • What verification can you do here? You, or the statisticians you hired too, can devise a hypothesis test to distinguish a failed component from a working component based on the output of your RNG device.
    • Make sure that computing the hypothesis test doesn't leak secrets through side channels.
  3. If there is a CSPRNG involved, study the cryptography of the CSPRNG. Hire the smartest cryptanalysts in the world to find distinguishers for the CSPRNG.
    • What verification can you do here? You, or the cryptography engineers you hired too, can write automatic tests using known-answer test vectors to confirm that the CSPRNG implements the same design that has been subjected to decades of scrutiny and vetted by cryptanalysts publishing in serious peer-reviewed academic conferences around the world.
    • Note that the CSPRNG is essentially guaranteed to prevent hardware health tests, which is why you should apply those first to the hardware RNG output before conditioning it with a CSPRNG.

Alternatively, if you don't like these answers, I hear you can buy a book of certified random numbers from RAND Corporation, so named presumably because they're experts on the matter.


As for detecting duplicates, it depends on what units the data are in. Duplicate bits? Well, there's only two possible bits, so you probably have duplicates unless you've found new kinds of bits hitherto unknown to humankind! Duplicate terabit-length bit strings? You probably have only one of those even if you have several terabytes of data. But maybe you meant something like 32-bit or 256-bit strings. One way to detect duplicates in a large list is to sort it—costing $O(n \log n)$ time in the naive view of things, or $O(n \sqrt n)$ in the more realistic area-time metric which may become relevant in large volumes of data—and then scan through it for duplicates. But this seems to be a general non-cryptographic algorithm question.

$\endgroup$
  • 1
    $\begingroup$ Would the downvoter care to elaborate on what you disagreed with? $\endgroup$ – Squeamish Ossifrage May 17 at 15:06
  • $\begingroup$ Thanks for the clarifications @Squeamish. After reading your answer i do realize the question was posited incorrectly and is mostly algorythm/programming related. Nevertheles i believe your answers covers the bases (and goes as such) $\endgroup$ – zeridon May 18 at 7:04
  • $\begingroup$ It's obvious that the question is about applying randomness tests such as the NIST SP800-22 distinguishability tests or TestU01 to this set of filtered TRNG (or whatever it is) output. These are tests for patterns that would be very improbable for uniformly distributed IID random variables. That sort of test can be done without an engineering analysis of any kind. (There is a problem, of course, given that duplicates have been filtered; that's what the question is about.) $\endgroup$ – Mars Jun 10 at 16:09
  • $\begingroup$ @Mars It appears to me that this question is about verifying the randomness and uniqueness of outputs of a physical device. If the device fails the NIST SP800-22 tests or TestU01 or dieharder or whatever, then it is so astonishingly predictable that it can be distinguished by someone who didn't even know they were trying to attack it. It would be awfully convenient if we could choose our adversaries to be so stupid they will plug up their ears and shut their eyes to relevant information, but here on crypto.se we assume our adversaries are smart and know everything about how the system works. $\endgroup$ – Squeamish Ossifrage Jun 10 at 16:19
  • $\begingroup$ S.O., thanks, I understand. I was focusing only on the words in the question, which don't mention crypto issues per se--though granted, this is crypto.SE. :-) On the other hand, I have been assuming that even here, in addition to concerns about security, statistical randomness of sets of numbers might be important for some applications. In that case, the test suites would matter. OP accepted your answer, though, suggesting that they really were more concerned about security. $\endgroup$ – Mars Jun 10 at 16:27
2
$\begingroup$

@SqueamishOssifrage has given an accepted answer, so I assume that it addresses your concerns. However the question as stated was about randomness tests, and I think there's something to add concerning that aspect of the question.

I am more familiar with the TestU01 than NIST tests, but based on what I've read in Johnston's Random Number Generators--Principles and Practices, I believe that the following is true for at least most of the NIST SP800-22 tests as well.

These are tests such that, if your numbers were generated by a series of independent uniformly distributed random variables--which is what I take a uniformly distributed TRNG to be supposed to produce--then it would be very improbable that the set of numbers would exhibit the patterns that these tests look for. That is why the tests are based on p-values: A small p-value for a test means that the test is detecting a pattern that would be very improbable if the numbers were generated by a uniformly distributed TRNG, providing evidence that the numbers are not like those that would be expected from such a TRNG.

Your problem is that you believe that the numbers are unlike those produced by a TRNG in that duplicates have been removed--or at least you hope that they have been.

(Ruggero's question in comments and Squeamish Ossifrage's comments about the size of the numbers is relevant here. If they were 16-bit numbers, for example, then given the size of your set, you would be guaranteed to have duplicates.)

So, in theory, you could take each test in the NIST suite or TestU01, and work out what patterns would be improbable on the assumption that duplicates have been removed, using this to construct new tests. Then apply your alternative tests to the numbers. This would require some statistical reasoning and hopefully not a lot of extra coding. TAOCP volume 2, chapter 3 would be a good starting point. It's old, and there are additional tests in the recent test suites (with smaller p-values required for failure, I believe). However, Knuth walks you through the reasoning processes for constructing these tests and provides a semi-cookbook/semi-theoretical introduction to the relevant statistical methodology.

Alternatively, given the size of your numbers and the size of the set, maybe it is possible to prove that the tests in the test suites would not be very sensitive to the presence or absence of a few duplicates. In that case, you could use the test suites as is, and use a separate duplicate-finding algorithm to test for uniqueness, as Squeamish Ossifrage suggested.

EDIT: Another option would be to add back duplicates, and then run the NIST or TestU01 suites. This is not as crazy as it might sound. On the assumption that the generation process is uniform and independent for each number produced, there is a probability distribution over numbers of duplicates (given the size of the set and the number of bits in the numbers). You might want to test for duplicates first, but if there are none, then you can use a sampling method to add them back with probabilities equal to the probabilities of their appearance in the first place. I know of at least one scientific paper that had to do something roughly analogous to this in order to apply statistical tests that the authors had designed. (I'll add the citation if anyone's interested, but it's far from cryptography, and finding the relevant part of the paper and understanding what they're doing requires some explanation.)

ANOTHER EDIT: @SqueamishOssifrage's comments made me realize that I should emphasize that PRNG test suites like TestU01, NIST SP800-22, or Dieharder were originally designed for people developing PRNGs. They may be designed to be easy to use, but it would be worth at least skimming the background documentation for TestU01. Implicit in my statements above about what is probable or improbable is that the improbable can happen. That is, one can get a test "failure" even if the set of numbers being tested should be considered OK, because it is only probable that a good set of numbers will pass each test. If you can test lots of numbers, this is less likely, but it's still possible. (However, I believe that by default TestU01 uses very small p-values such as $10^{-10}$ as standards for failure. That is, failure means that your data has patterns in it that would only have a 1/10000000000 chance of occurring if it had been generated by a truly uniformly distributed generator. On the other hand, there are multiple tests in TestU01, so your data gets multiple chances to exceed this limit. But it is an extreme limit nonetheless.)

$\endgroup$
  • $\begingroup$ This advice isn't wrong, and I have no criticism of the algorithms or their mathematical analysis provided by Knuth, but there is some very important perspective missing from Knuth and—based on a cursory skim—from Johnston on the meaning of these randomized hypothesis tests, leading to essentially wrong interpretations. These are decision rules designed with certain frequentist properties as binary hypothesis tests—false alarm rate (‘statistical significance’), statistical power to detect deviations, etc. For perspective, consider this answer. $\endgroup$ – Squeamish Ossifrage Jun 10 at 18:27
  • $\begingroup$ The trick of adding duplicates back in is cute! Can you expand on how you do this, and prove that the resulting distribution is correct or quantify how far off it is from the null hypothesis of the TestU01 tests? $\endgroup$ – Squeamish Ossifrage Jun 10 at 20:50
  • $\begingroup$ @SqueamishOssifrage re "This advice". Beautiful answer. Sure, there're additional subtleties. My answer doesn't just summarize Knuth or Johnston. Not clear to me whether you're in disagreement with how non-CS PRNGs continue to be developed and tested. Johnston is not great on statistical subtleties but he tries. Kneusel 2018 book less so. L'Ecuyer & Simard's TestU01 paper, L'Ecuyer's handbook chapters are better. I'm interested in lit on stat testing of PRNGs as uniform dist generators, though; pointers welcome. (I'm more interested in probability, modeling than crypto. Don't kick me out. :-) $\endgroup$ – Mars Jun 11 at 3:19
  • 1
    $\begingroup$ @SqueamishOssifrage re "trick": Did I forget "left as an exercise for the reader"? Off top of my head, for N values before pruning, with r-bit numbers as values, use multinomial dist for each possible count for each of the 2^r values, with prob 1/2^r for each draw. Gives you probs of (N - dupes) total current size. Now use your favorite stat inf method (frequentist/Bayesian/likelihoodist/etc to estimate N and dupe counts. Sample from your numbers until you get N (maybe requires finesse--not sure). Test that. Maybe test multiple versions. Have lots of CPU cycles on hand. (Proof? exercise.) $\endgroup$ – Mars Jun 11 at 3:29
  • $\begingroup$ What I meant is not that your answer is missing perspective that you'll find in Knuth or Johnston, but that Knuth and Johnston are missing perspective: these tests have frequentist properties of false alarm rates (‘statistical significance’) for null hypotheses, statistical power to detect particular alternative hypotheses, etc., and that entire conceptual framework is missing from Knuth and (based on my cursory skim) Johnston. This has real consequences: if you write automatic software tests for your sampler with a null hypothesis, and apply statistical tests, and they fail, what then? $\endgroup$ – Squeamish Ossifrage Jun 11 at 3:37

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.