4
$\begingroup$

Let's assume I have thousands of (pseudo-)random 4-byte values. The values are 4 byte random values which a blackbox device gave me. I got these values by requesting them. In between others might have requested them too (I don't know about that). Now I'd like to test them for randomness. There are tools for this like dieharder or the NIST Statistical Test Suite.

Is it valid to just concatenate the thousands of 4-byte values so that I end up with one very long byte (n * 1000 * 4 byte) stream which I then feed into these tools?

Is it correct that it doesn't matter for the tests how long the individual values (4-byte) were before? (Because the test tool wouldn't know that I had 4-byte values in the beginning, once I concatenated them?).

Edit: The question is meant as a general question. The actual underlying problem is how to examine seed values for randomness, which I obtained via UDS Security Access (see https://en.wikipedia.org/wiki/Unified_Diagnostic_Services#Services $27).

$\endgroup$
3
  • 1
    $\begingroup$ "Why did Paul get down votes?" Search the Dunning–Kruger effect. He doesn't know how hypothesis testing works. He doesn't understand entropy. He just recently learned the term I.I.D. and I'm 50-50 on whether he knows the definition. He is no expert on ent, dieharder, TestU01, etc. If you raised a parrot exposing it to a constant audio stream of cryptographers talking to each other then the bird would probably be false less often than he is. It's not worth correcting him because he'll just use the criticism to make his answers less obviously wrong and mislead more people. $\endgroup$ Nov 16, 2018 at 19:53
  • $\begingroup$ @FutureSecurity When we use an acronym like "IID", we don't put periods between the letters. I could be wrong though... $\endgroup$
    – Paul Uszak
    Nov 17, 2018 at 10:35
  • 1
    $\begingroup$ Before I forget again: The specific errors here are 1. Assurance that passing any empirical black box test gives you any confidence in RNG output (either in quality or security), 2. Recommendation of ent. (The name sounds like it should be useful but it's not much more advanced than something someone could program in an hour.) 3. Not understanding that you can only have more confidence with larger sample sizes. - Don't pity him though. Just one up vote is worth 5 down votes. And he regularly takes advantage of that. : ( $\endgroup$ Nov 21, 2018 at 18:40

3 Answers 3

4
$\begingroup$

Thousands of bytes isn't nearly enough samples for any powerful statistical test. The fewer samples you have the less sensitive a given test can be.

If you concatenate statistically independent uniform samples then tests should pass the resulting byte stream. It doesn't matter how the bits are rearranged as long as order doesn't depend on the value of those bits. (Reversing and bit interleaving but not rearranging bytes into ascending order.)

Some statistical tests aren't sensitive to order. Basic frequency tests and tests based on mean, median, variance, for example. However test suites include many different types of tests, some of which are order sensitive. Rearranged bits from an ideal random source should pass both order-sensitive and order-insensitive tests.

Different methods involving reordering are used in testing Non-Cryptographic RNGs. One improvement over a single pass over test data is to repeat the test with bit order reversed within each 32-bit word. This is documented in Sebastiano Vigna's papers involving RNG testing. This is done because the tests are less sensitive to patterns in low order bits and also because non-cryptographic RNGs are often "more" random in high bits and "less" random in low bits.

Round-robin interleaving of samples from multiple generators was done in a paper, "Better Splitable Pseudorandom Number Generators (and Almost As Fast)" as hack to test RNGs from the same family for correlations. It isn't a totally reliable method for detecting such correlations.

Other kinds of modifications to the test suites' inputs will have the same effect as reordering as long as they do not introduce bias. For example, negating each bit of output, XORing the stream by a constant, or using modular addition with a constant.

A Good RNG Will Pass no matter how you mutate (without bias) its output. A bad RNG Might fail or Might Not before or after transforming (scrambling) its output some way.

Such transformations Do Not Turn an Insecure RNG into a Secure RNG. A bad RNG can pass all or some statistical tests after applying various mutations. That does not mean that the input is actually random or unpredictable.

Positive RNG test suite results (failing a "randomness" test) usually indicate data is not random. There are false positive but they can be detected by running the tests multiple times with different data. False negatives, however, are a very serious flaw in RNG test suites.

Passing any number of statistical tests will not tell you if an RNG or cipher is secure. It is Very Easy to make an algorithm with enough apparent randomness to pass any black-box statistical tests you subject it to, but it's Much Harder to design a secure algorithm.

The same applies to output from a hardware TRNG. In fact you cannot tell the difference between truly random output and output generated from, say, a counter encrypted with a secret key known only to the manufacturers of the device. (As in a backdoored RNG.) Statistical tests cannot tell you how much entropy a hardware RNG produces. Nor can they tell you whether a noisy source is actually unpredictable.


In summary:

  • Passing RNG tests Does Not mean the output is actually pattern-free, statistically unbiased, or secure.
  • Failing the tests persistently indicates a definite problem.
  • An unbiased transformation applied to a uniform IID bit string results in a new string which is also unbiased.
  • Scrambling output can hide statistical artifacts but it Cannot turn insecure RNGs into secure RNGs.
  • RNG test suites are practically Useless for cryptography
  • Something can be apparently random without actually being unpredictable.
$\endgroup$
3
  • $\begingroup$ What's the difference between false -ve and false +ve wrt test suites? $\endgroup$
    – Paul Uszak
    Nov 16, 2018 at 3:21
  • $\begingroup$ That was an excellent answer, thank you. You said that RNG test stuites are practically useless for cryptography. I understand that passing RNG tests does not mean the output is pattern free, statistically unbiased or secure. But as you said failing tests peristently indicate a definite problem. Wouldn't they then actually help in terms that the "really bad" (in terms of there things like "there are patterns" and so on) RNGs would be found? So they can actually show that there is the a problem present, but they can't show the absence of a problem with the RNG. $\endgroup$
    – dudekowsky
    Nov 16, 2018 at 14:11
  • 1
    $\begingroup$ @dudekowsky Right. I meant "nearly useless" instead of "practically useless". (Tiny detail I missed while editing.) The difference, I think, is significant. The one use that keeps it from 100% useless is as a sanity check. In practice sanity checks are useful, other tests included. (Example) However there is a giant chasm between apparently random (which stats test can judge) and indistinguishable from random (which is a security requirement that PHDs need to judge). The one benefit (sanity check) may be outweighed by the drawback of giving a false sense of confidence. $\endgroup$ Nov 16, 2018 at 18:21
4
$\begingroup$

Is it valid to just concatenate the thousands of 4-byte values so that I end up with one very long byte (n * 1000 * 4 byte) stream which I then feed into these tools?

Is it correct that it doesn't matter for the tests how long the individual values (4-byte) were before?

Yes for both. The fact that others may have obtained (and removed) randomness from the source while it was sampled, or/and that the samples are grouped in some particular way for testing, does not prevent from testing what's obtained. And that can not cause a valid test to fail more often, assuming the source's full output is indistinguishable from random (including for said others trying to make the test pass, or fail).

On the other hand, those same facts could make the test become arbitrarily less capable of detecting some faults. As an extreme example, a source that always repeat each byte that it outputs might become indistinguishable from true random if we sub-sample its output, keeping every odd byte.

The actual underlying problem is how to examine seed values for randomness.

Dieharder or the NIST Statistical Test Suite alone can't give any assurance of that. At best, they can indicate a fail with high confidence, which saves from performing further work (beyond checking that the test was correctly performed/works). If they indicate pass, no other firm conclusion can be reached on that basis alone. It is needed to know how the seed values are generated, and that can't be determined by a test of the seed values.


As a proof that these tests can not validate the fitness for cryptographic purposes of a source of unknown build, consider a RNG with:

  • a real-time clock keeping UTC time in second, initializing 128-bit register at startup after a delay of 1 second
  • with the register then repeatedly encrypted using AES-256 and a key to produce the next register value, which concatenated 128-bit values form the bulk of the output, queried over a gigabit Ethernet interface.

This source will pass any black-box testing that does not reject a good generator, including tests scrutinizing power-on, as long as the test does not use AES-256 and the correct key.

But this source is disastrous from a cryptographic perspective. Given the key and when the black box was started, its output is predictable. Given the key and a fragment of a sequence, all the rest can be computed. Some party eating bytes from the source in the background can even decide what another party using the source will get!


As pointed by others, many statistical tests, including some of the DieHarder suite, require megabytes of input. The full Dieharder needs gigabytes.

However, in the context of a cryptographic RNG of proper structure, these tests requiring a lot of input are not needed. The tests that make sense are those on the unconditioned (or lightly conditioned) entropy source, used to seed a CSPRNG. The source is validated by tests which purpose is to ensure that it delivers some entropy. The CSPRNG is validated by examination of its design, and Known Answer Tests. Some monitoring in the RNG should detect a fault in the source and in this case prevent output. The combination might be checked by an extra test of the whole thing, but that's meaningful only if there is some assurance, obtained otherwise, that the overall structure really is the source seeding the CSPRNG, and being monitored.

$\endgroup$
-1
$\begingroup$

Yes concatenate them, but you'll find that randomness is somewhat of a function of sample size. The more stringent the test wanted, the larger a sample is required. Your idea of using dieharder is a non starter really, considering that a full un-throttled run (as shown here) can use ~250GB of data. You'll just wind yourself into spaghetti.

You're looking at a ball park figure of say 40KB. That's actually not a very long data set these days. I suggest that rather than waiting till the end of the world to generate a dieharder test set, you consider ent. It operates ideally with 500KB of data, but will produce a reasonable test with 40KB. If the numbers look reasonable, there is no cause for alarm. It will be very difficult indeed for anyone to challenge the randomness of a good 40KB ent test result. If any of the 5 individual tests fail dismally, be alarmed.

Expect something like this if the black box is good:-

Entropy = 7.995909 bits per byte.

Optimum compression would reduce the size
of this 40000 byte file by 0 percent.

Chi square distribution for 40000 samples is 225.80, and randomly
would exceed this value 90.59 percent of the times.

Arithmetic mean value of data bytes is 127.3208 (127.5 = random).
Monte Carlo value for Pi is 3.129312931 (error 0.39 percent).
Serial correlation coefficient is -0.003441 (totally uncorrelated = 0.0).

As the other answers have said, you can't validate the unpredictability of the numbers without taking the box apart. This is about the best you can hope for.

You may be able to fool ent with quite a concerted effort, but I'm sceptical. The real issue is why would someone be generating engine management data for real vehicles with the aim of fooling ad hoc ent tests? The would be weird.

Since some people advocate continuing with dieharder in this case, the following is the result of a dieharder run against 40KB of perfectly random IID data from /dev/urandom. It's totally rubbish and tells you absolutely nothing about the distribution of the sample. The thing to note though is the rewinds. Just the last test (dab_monobit2) rewound > 6 million times. That suggests dieharder inherently requires ~ 240GB of data without it having to regurgitate the same values over and over and over...

# The file file_input_raw was rewound 384 times
   diehard_birthdays|0.00065267|   WEAK   
# The file file_input_raw was rewound 10384 times
      diehard_operm5|0.00000000|  FAILED  
# The file file_input_raw was rewound 23184 times
  diehard_rank_32x32|0.00000000|  FAILED  
# The file file_input_raw was rewound 29184 times
    diehard_rank_6x8|0.00000000|  FAILED  
# The file file_input_raw was rewound 31805 times
   diehard_bitstream|0.00000000|  FAILED  
# The file file_input_raw was rewound 52777 times
        diehard_opso|0.00000000|  FAILED  
# The file file_input_raw was rewound 66758 times
        diehard_oqso|0.00000000|  FAILED  
# The file file_input_raw was rewound 73311 times
         diehard_dna|0.00000000|  FAILED  
# The file file_input_raw was rewound 73951 times
diehard_count_1s_str|0.00000000|  FAILED  
# The file file_input_raw was rewound 86751 times
diehard_count_1s_byt|0.00000000|  FAILED  
# The file file_input_raw was rewound 86991 times
 diehard_parking_lot|0.00000000|  FAILED  
# The file file_input_raw was rewound 87151 times
    diehard_2dsphere|0.00000000|  FAILED  
# The file file_input_raw was rewound 87271 times
    diehard_3dsphere|0.00000000|  FAILED  
# The file file_input_raw was rewound 110366 times
     diehard_squeeze|0.00000000|  FAILED  
# The file file_input_raw was rewound 110368 times
        diehard_sums|0.00183407|   WEAK   
# The file file_input_raw was rewound 111368 times
        diehard_runs|0.00000000|  FAILED  
        diehard_runs|0.00000000|  FAILED  
# The file file_input_raw was rewound 125325 times
       diehard_craps|0.00000000|  FAILED  
       diehard_craps|0.00000000|  FAILED  
# The file file_input_raw was rewound 325325 times
 marsaglia_tsang_gcd|0.00000000|  FAILED  
 marsaglia_tsang_gcd|0.00000000|  FAILED  
# The file file_input_raw was rewound 326325 times
         sts_monobit|0.00000000|  FAILED  
# The file file_input_raw was rewound 327325 times
            sts_runs|0.00000000|  FAILED  
# The file file_input_raw was rewound 328325 times
          sts_serial|0.00000000|  FAILED  
          sts_serial|0.00000000|  FAILED  
          sts_serial|0.00000000|  FAILED  
          sts_serial|0.00000000|  FAILED  
          sts_serial|0.00000000|  FAILED  
          sts_serial|0.00000000|  FAILED  
          sts_serial|0.00000000|  FAILED  
          sts_serial|0.00000000|  FAILED  
          sts_serial|0.00000000|  FAILED  
          sts_serial|0.00000000|  FAILED  
          sts_serial|0.00000000|  FAILED  
          sts_serial|0.00000000|  FAILED  
          sts_serial|0.00000000|  FAILED  
          sts_serial|0.00000000|  FAILED  
          sts_serial|0.00000000|  FAILED  
          sts_serial|0.00000000|  FAILED  
          sts_serial|0.00000000|  FAILED  
          sts_serial|0.00000000|  FAILED  
          sts_serial|0.00000000|  FAILED  
          sts_serial|0.00000000|  FAILED  
          sts_serial|0.00000000|  FAILED  
          sts_serial|0.00000000|  FAILED  
          sts_serial|0.00000000|  FAILED  
          sts_serial|0.00000000|  FAILED  
          sts_serial|0.00000000|  FAILED  
          sts_serial|0.00000000|  FAILED  
          sts_serial|0.00000000|  FAILED  
          sts_serial|0.00000000|  FAILED  
          sts_serial|0.00000000|  FAILED  
          sts_serial|0.00000000|  FAILED  
# The file file_input_raw was rewound 330325 times
         rgb_bitdist|0.00000000|  FAILED  
# The file file_input_raw was rewound 334325 times
         rgb_bitdist|0.00000000|  FAILED  
# The file file_input_raw was rewound 340325 times
         rgb_bitdist|0.00000000|  FAILED  
# The file file_input_raw was rewound 348325 times
         rgb_bitdist|0.00000000|  FAILED  
# The file file_input_raw was rewound 358325 times
         rgb_bitdist|0.00000000|  FAILED  
# The file file_input_raw was rewound 370325 times
         rgb_bitdist|0.00000000|  FAILED  
# The file file_input_raw was rewound 384325 times
         rgb_bitdist|0.00000000|  FAILED  
# The file file_input_raw was rewound 400325 times
         rgb_bitdist|0.00000000|  FAILED  
# The file file_input_raw was rewound 418325 times
         rgb_bitdist|0.00000000|  FAILED  
# The file file_input_raw was rewound 438325 times
         rgb_bitdist|0.00000000|  FAILED  
# The file file_input_raw was rewound 460325 times
         rgb_bitdist|0.00000000|  FAILED  
# The file file_input_raw was rewound 484325 times
         rgb_bitdist|0.00000000|  FAILED  
# The file file_input_raw was rewound 486325 times
rgb_minimum_distance|0.00000000|  FAILED  
# The file file_input_raw was rewound 489325 times
rgb_minimum_distance|0.00000000|  FAILED  
# The file file_input_raw was rewound 493325 times
rgb_minimum_distance|0.00000000|  FAILED  
# The file file_input_raw was rewound 498325 times
rgb_minimum_distance|0.00000000|  FAILED  
# The file file_input_raw was rewound 500325 times
    rgb_permutations|0.00000000|  FAILED  
# The file file_input_raw was rewound 503325 times
    rgb_permutations|0.00000000|  FAILED  
# The file file_input_raw was rewound 507325 times
    rgb_permutations|0.00000000|  FAILED  
# The file file_input_raw was rewound 512325 times
    rgb_permutations|0.00000000|  FAILED  
# The file file_input_raw was rewound 522325 times
      rgb_lagged_sum|0.00000000|  FAILED  
# The file file_input_raw was rewound 542325 times
      rgb_lagged_sum|0.00000000|  FAILED  
# The file file_input_raw was rewound 572325 times
      rgb_lagged_sum|0.00000000|  FAILED  
# The file file_input_raw was rewound 612325 times
      rgb_lagged_sum|0.00000000|  FAILED  
# The file file_input_raw was rewound 662325 times
      rgb_lagged_sum|0.00000000|  FAILED  
# The file file_input_raw was rewound 722325 times
      rgb_lagged_sum|0.00000000|  FAILED  
# The file file_input_raw was rewound 792325 times
      rgb_lagged_sum|0.00000000|  FAILED  
# The file file_input_raw was rewound 872325 times
      rgb_lagged_sum|0.00000000|  FAILED  
# The file file_input_raw was rewound 962325 times
      rgb_lagged_sum|0.00000000|  FAILED  
# The file file_input_raw was rewound 1062325 times
      rgb_lagged_sum|0.00000000|  FAILED  
# The file file_input_raw was rewound 1172325 times
      rgb_lagged_sum|0.00000000|  FAILED  
# The file file_input_raw was rewound 1292325 times
      rgb_lagged_sum|0.00000000|  FAILED  
# The file file_input_raw was rewound 1422325 times
      rgb_lagged_sum|0.00000000|  FAILED  
# The file file_input_raw was rewound 1562325 times
      rgb_lagged_sum|0.00000000|  FAILED  
# The file file_input_raw was rewound 1712325 times
      rgb_lagged_sum|0.00000000|  FAILED  
# The file file_input_raw was rewound 1872325 times
      rgb_lagged_sum|0.00000000|  FAILED  
# The file file_input_raw was rewound 2042325 times
      rgb_lagged_sum|0.00000000|  FAILED  
# The file file_input_raw was rewound 2222325 times
      rgb_lagged_sum|0.00000000|  FAILED  
# The file file_input_raw was rewound 2412325 times
      rgb_lagged_sum|0.00000000|  FAILED  
# The file file_input_raw was rewound 2612325 times
      rgb_lagged_sum|0.00000000|  FAILED  
# The file file_input_raw was rewound 2822325 times
      rgb_lagged_sum|0.00000000|  FAILED  
# The file file_input_raw was rewound 3042325 times
      rgb_lagged_sum|0.00000000|  FAILED  
# The file file_input_raw was rewound 3272325 times
      rgb_lagged_sum|0.00000000|  FAILED  
# The file file_input_raw was rewound 3512325 times
      rgb_lagged_sum|0.00000000|  FAILED  
# The file file_input_raw was rewound 3762325 times
      rgb_lagged_sum|0.00000000|  FAILED  
# The file file_input_raw was rewound 4022325 times
      rgb_lagged_sum|0.00000000|  FAILED  
# The file file_input_raw was rewound 4292325 times
      rgb_lagged_sum|0.00000000|  FAILED  
# The file file_input_raw was rewound 4572325 times
      rgb_lagged_sum|0.00000000|  FAILED  
# The file file_input_raw was rewound 4862325 times
      rgb_lagged_sum|0.00000000|  FAILED  
# The file file_input_raw was rewound 5162325 times
      rgb_lagged_sum|0.00000000|  FAILED  
# The file file_input_raw was rewound 5472325 times
      rgb_lagged_sum|0.00000000|  FAILED  
# The file file_input_raw was rewound 5792325 times
      rgb_lagged_sum|0.00000000|  FAILED  
# The file file_input_raw was rewound 6122325 times
      rgb_lagged_sum|0.00000000|  FAILED  
# The file file_input_raw was rewound 6123325 times
     rgb_kstest_test|0.00000000|  FAILED  
# The file file_input_raw was rewound 6138685 times
     dab_bytedistrib|0.00000000|  FAILED  
# The file file_input_raw was rewound 6139965 times
             dab_dct|0.00000000|  FAILED  
Preparing to run test 207.  ntuple = 0
# The file file_input_raw was rewound 6151212 times
        dab_filltree|0.00000000|  FAILED  
        dab_filltree|0.00000000|  FAILED  
Preparing to run test 208.  ntuple = 0
# The file file_input_raw was rewound 6154094 times
       dab_filltree2|0.00000000|  FAILED  
       dab_filltree2|0.00000000|  FAILED  
Preparing to run test 209.  ntuple = 0
# The file file_input_raw was rewound 6160594 times
        dab_monobit2|1.00000000|  FAILED  

You find that the full dieharder is best suited to photonic based TRNGs where it's commonly used.

$\endgroup$
18
  • $\begingroup$ Why did Paul get down votes? If you give him a down vote, could you please add a comment so that it is clear what's wrong with his answer? $\endgroup$
    – dudekowsky
    Nov 16, 2018 at 9:23
  • 3
    $\begingroup$ @dudekowsky: I did not downvote, but I do see issues with that answer. Some of DieHarder is usable with small sample size. Ent is a basic test, and recommending it is dangerous, especially without mentioning when it is useful, and most importantly when it is not. The answer focuses on the sample size, and does not answer the actual question (on sub-sampling, and alignment, if I get it correctly). $\endgroup$
    – fgrieu
    Nov 16, 2018 at 10:08
  • 3
    $\begingroup$ @dudekowsky: Ent is useful when testing samples which are known to be independent. It is terminally bad at detecting correlated samples. For example, a byte value that slowly increases and wraparounds, with just a little irregularity, is given a clean bill of health by Ent. And, like with all statistical tests, a success is, by itself, not an even an indication of cryptographic security. $\endgroup$
    – fgrieu
    Nov 16, 2018 at 13:11
  • 1
    $\begingroup$ @PaulUszak Interesting, I was able to fetch roughly 350 kByte. With that the percentage goes up to around 40 percent. $\endgroup$
    – dudekowsky
    Nov 16, 2018 at 15:32
  • 1
    $\begingroup$ @dudekowsky One other point. Check whether the numbers repeat exactly if you switch it off and on again... $\endgroup$
    – Paul Uszak
    Nov 16, 2018 at 16:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.