1
$\begingroup$

I'm testing my own PRNG generator which should has period $2^{38}$ bytes. So after exactly $2^{38}$ bytes it should start repeat. But PractRand find no anomalies after $2^{39}$ bytes.

Could it be that PractRand wouldn't detect this, or I had miscount something and the generator does not loop after that number of bytes?

$\endgroup$
4
  • $\begingroup$ You ran it on 500 GB? $\endgroup$
    – Paul Uszak
    Jan 15 at 13:37
  • $\begingroup$ No, you can use numbers from your program and redirect them directly to PractRand in console. Example: python3 Mygenerator.py | ./RNG_test stdin. Then the PractRand starts and tests until it fails. $\endgroup$
    – Tom
    Jan 15 at 14:19
  • $\begingroup$ But you ran it over $2^{39}$ bytes? $\endgroup$
    – Paul Uszak
    Jan 15 at 14:23
  • $\begingroup$ @PaulUszak Yes, I do. It works now almost 3 days and still didn't fail. Which of course is not unusual, many generators can do this. $\endgroup$
    – Tom
    Jan 15 at 14:26
1
$\begingroup$

I can't speak for your generator as I've not seen it. Is it cryptographically secure (as that's a little tricky to write and just because you can't recover the seed doesn't for one moment mean that others can't).

I am not surprised at all that PractRand doesn't detect a loop at >275 GB (See notes). I have no direct experience of PractRand, but irrespective of it's low pedigree, all of the 'standard' tests have problems. NIST's STS has a very narrow set of internal statistics which severely limits it's acceptable sample sizes. diehard has the infamous sums test and other weak tests. Recently dieharder has been found to have Kolmogorov–Smirnov test biases (~ 8 TB samples). And it's limited to ~250 GB of data. ent is missing several p values entirely. FIPS 140 is quite weak. Test U01 has to be complied with parameters that can be tweaked (why?). PractRand won't be any different, especially considering the limited number of developers working on it.

In summary, non of the available test suites are perfect and randomness is pesky. This is what we currently have though. I would suggest using another test suite for samples <275 GB and compare. Best of three runs is recommended. 275 GB of key material stretched out of one seed should be sufficient for most use cases anyway


Notes:

For testing the PractRand tests, simply generate 100 GB from /dev/urandom, copy it and concatenate so forming a roll over. See what happens for you.

I've just diehardered a concatenated file as 2 x 10 GB from /dev/urandom and it passed with two WEAKs:-

   sts_serial|   6|    100000|     100|0.99995833|   WEAK
  diehard_dna|   0|   2097152|     100|0.99637872|   WEAK

C'est la vie.

$\endgroup$
4
  • $\begingroup$ So it is possible to cheat this kind of testing tool. I will wait if the generator fails the tests after 2^40 bytes. That would mean the entire sequence was looped 4 times. Anyway it looks like, it can be looped many times as long as the entire sequence has perfect statistical properties, it can loop multiple times before statistical deviations will be detected. $\endgroup$
    – Tom
    Jan 15 at 20:33
  • $\begingroup$ @Tom Yes it seems so. But that's perhaps not surprising. The scan window on these tests just isn't large enough for massive data samples like yours. Also consider, dieharder rewinds data files if they're smaller than ~250 GB. My example above (2 x 10 GB) was rewound 11 times yet passed. So that's a scan window of <10 GB. $\endgroup$
    – Paul Uszak
    Jan 17 at 13:42
  • $\begingroup$ Yes, I forgot about that rewinds - that's true. I also noted passing tests with repetitions in dieharder. So in PractRand it could be the same. I will test a generator with a smaller state to estimate when they might fail. $\endgroup$
    – Tom
    Jan 18 at 15:05
  • $\begingroup$ After testing an 8-bit generator with a period of $2^{20}$ it failed in PractRand after $2^{24}$ tested 8-bit numbers. So it looped the stream several times before problems were detected. The same can be expected for the 16-bit generator I tested. I thought this software had loop detectors built in - but it doesn't. $\endgroup$
    – Tom
    Jan 18 at 16:34

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.