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

[Ray Dillinger]

On 6/22/21 12:34 AM, John Denker via cryptography wrote:
>
> ++ 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.
>

I think I disagree in several small ways.

     First, the OP was asking specifically about pseudorandom number
generators, not random number generators.  If we suppose that they know
what they want and there's a reason, it's reasonable to suppose that a
random number generator does not have properties essential to their
application.  The most obvious PRNG application is repeatable random
testing.  The most obvious adversarial PRNG application is probably a
stream cipher. In both cases an RNG won't help.

     There are several RNGs with security proofs.  But pay attention to
what is proven and under what conditions.  If any of those things is not
true then the proof is not applicable.  And in practice it's
depressingly likely that at least one of the assumptions that security
rests on will be violated in some times and places.

     In fact it happens all the time, by accident. Someone "virtualizes"
a model of the machine so they can run fifty of them on a server, and
the virtual machine has things that look to it like sensors of some
natural process, or some unique machine identification, and aren't. So
the line of inference from natural process to binary output is cut.

     But that's not the only way conditions can be violated.  Sometimes
hardware failure leads to an 'all-zeros' read from a device, and if that
was one that the RNG depended on, then it's not secure.

     So... yeah, I don't put much stock in proofs about RNG security. 
You still have to prove that the premises are true, that the axiom is
valid in every case, and that the conclusions state all of the
requirements you've got, and that the inference from premise to
conclusion will not be subverted by false readings, broken or shared
sensing hardware, or myriad other things that violate the conditions
that the proof is based on.

    "Proven Secure" has nice properties, but If the security proof
requires something to be true that there's any possibility may not be
true in practice, in any case in the wide world, (eg somebody
virtualizes the machine etc) then the proof is invalid.  So it becomes
just another stream of probably-unpredictable bits to your application.

     So, get your "Proven secure" bits, for sure.  Fill your randompool
all the way up. But then mix in bits from three different PRNGs, every
hardware sensor you can find, the time of day, the IP address, the NAS
address, the CPU ID, and everything else you can think of.  Put in
enough to fill your randompool at least three more times.  And proceed
hoping that at least a couple of those things are and remain completely
unpredictable to whatever opponent there is.  The RNG alone will be
enough if the conditions supporting its proof are met.  But they may not
be, so have some depth behind that hard but brittle line.

Bear