[Phys-L] RNG quality issues and recommendations

[John Denker <jsd@av8n.com>]

On 02/26/2014 04:08 PM, Craig Wiegert wrote:

> In terms of pseudo-RNGs, there are several statistical tests, like
> Knuth's serial and gap tests, and some in the "DieHard battery", that
> look for the sort of bias that would skew a "throw out and re-roll"
> strategy.

Yes.  Also Maurer's "Universal" Statistical Test.

> I'd expect any pRNG worth its salt to pass these. 

Big smile.  Both halves of that statement are true and
important.

The idea of vetoing out-of-range random numbers and drawing
again is entirely valid in general, and verrrrry widely
used.  It is among other things essentially the definition
of Monte Carlo integration.

Using this trick to convert draw-with-replacement into
draw-without-replacement is entirely kosher.  Of course
no matter what you are doing, you can always screw up
the implementation ... but still the basic idea is sound.

You would think "any" PRNG would be good enough for this
purpose.  Physics applications such as molecular dynamics
and Monte Carlo integration are among the *least* demanding
PRNG applications.  That's because they are non-adversarial.
The molecules in the molecular dynamics simulation are not
going to mount a cryptanalytic attack against your PRNG.

  In contrast, other PRNG applications such as high-
  stakes gaming, cryptography, military and business
  strategy etc. are verrry much more demanding.  That's
  because the adversary finds it worthwhile to devote
  enormous resources to breaking your PRNG.

    FWIW the weakest link in any decent modern crypto-
    logically strong pseudo-random number generator 
    (SCPRNG) is the /seed/ ... and this is where the 
    physics comes to the rescue.  At some point you 
    need a hardware RNG (HRNG) to seed your PRNG, and 
    the HRNG depends on physics.

    For non-adversarial applications you don't need to
    worry about the seed, and indeed you might sometimes
    /want/ to re-run the program with the same seed.

On the third hand, there are still a lot of software
packages running around with incredibly bad PRNGs, so
bad that they can't be trusted even for the most 
benign non-demanding tasks.

>  Do I go to the same pRNG well for all of
> my random number needs, or is it prudent to use different pRNGs (perhaps
> the same algorithm but with different seeds) for each type of quantity?

There is AFAICT never a good reason to use multiple
PRNGs in parallel.  If it's a good PRNG, the outputs
are IID (independent and identically distributed).
There are no significant correlations.  Nothing 
can be more random than this.

  Conversely, if the PRNG is so screwed up that the
  second-order statistics can't be trusted, the
  first-order statistics can't be trusted either.

If your PRNG is so untrusted that you are asking
questions like this, you need a better PRNG, stat.

For any physics purpose I can imagine, running a
cryptologic hash function in counter mode should
be good enough, with a verrrry wide margin of
safety.  Open-source code for SHA-1 and SHA-256
is lying around just about everywhere.

Running a strong block cipher such as AES in
counter mode also works, and requires slightly
fewer CPU cycles.  There is some really efficient
AES code lying around.