[Cryptography] "Practical Construction and Analysis of Pseudo-Randomness Primitives"

[John Denker]

On 6/21/21 11:15 AM, Caleb Cannon wrote:

> I wrote a PRNGG. That is, a pseudo random number generator generator.

Ruh roh.

> the part that I had the most trouble with was testing the quality of
> the random number generation.

It's good that you found this to be problematic. It means you were
paying attention. There's a reason why it's problematic. Consider
the following proverb:
	Testing can sometimes demonstrate the absence of randomness,
	but it can never demonstrate the presence of randomness.
				h/t Dykstra.

This is the reef upon which the entire PRNGG concept is guaranteed
to founder.

For the next level of detail, consider the contrast:

−− For some low-risk non-adversarial purposes, almost any RNG will
suffice. An encrypted counter will look random to any tester who
doesn't know the encryption key.

  Specifically: Practical application #1: An encrypted counter 
  works fine for Monte Carlo molecular dynamics, even if the
  encryption key is published, because the molecules don't read
  the literature. This has the advantage that the pseudo-random
  sequence can be replicated exactly, if desired.

  Practical application #2: Some radar systems use LFSRs to
  ensure that pulses don't conflict more often than randomly.
  Conversely, it is advantageous that the LFSR is trivial to
  cryptanalyze, for purposes other than pulse deconfliction.

++ However (!) for high-stakes applications, including ordinary
crypto applications, it is important to have a provably correct
RNG. That requires designing it systematically. That means having
a detailed understanding of how it works and why it works.

Such designs exist. The hard work has already been done. Anything 
else is a huge leap in the wrong direction.