isUniformRNG

[Joseph Rushton Wakeling via Digitalmars-d]

On 11/05/14 05:58, Nick Sabalausky via Digitalmars-d wrote:
> The seed doesn't need to be compromised for synchronized RNGs to fubar security.

Before we go onto the detail of discussion, thanks very much for the extensive 
explanation.  I was slightly worried that my previous email might have come 
across as dismissive of your (completely understandable) concerns.  I'm actually 
quite keen that we can find a mutually agreeable solution :-)

> It's bad enough just to accidentally generate the same byte sequence for
> multiple things:
>
> struct CryptoRng { ulong internalState; ...etc... }
> CryptoRng myRand;
>
> // Oops! Duplicates internal state!
> ubyte[] getRandomJunk(CryptoRng rand) {
>      return rand.take(64).array();
> }
>
> // Oops! These are all identical! Passwords may as well be unsalted!
> auto saltForStevensPassword =  getRandomJunk(myRand);
> auto saltForSallysPassword =  getRandomJunk(myRand);
> auto saltForGregsPassword =  getRandomJunk(myRand);
>
> // Oops! Also identical!
> auto oneTimeURL1 =  "https://verify-email/a@a.a/"~getRandomJunk(myRand);
> auto oneTimeURL2 =  "https://verify-email/b@b.b/"~getRandomJunk(myRand);
> auto oneTimeURL3 =  "https://verify-email/c@c.c/"~getRandomJunk(myRand);
>
> May as well have just defined getRandomJunk as a constant ;)

Sure, but this is a consequence of two things (i) CryptoRng is a value type and 
(ii) it gets passed by value, not by reference.

In your example, obviously one can fix the problem by having the function 
declared instead as

     ubyte[] getRandomJunk(ref CryptoRng rand) { ... }

but I suspect you'd say (and I would agree) that this is inadequate: it's 
relying on programmer virtue to ensure the correct behaviour, and sooner or 
later someone will forget that "ref".  (It will also not handle other cases, 
such as an entity that needs to internally store the RNG, as we've discussed 
many times on the list with reference to e.g. RandomSample or RandomCover.)

Obviously one _can_ solve the problem by the internal state variables of the RNG 
being static, but I'd suggest to you that RNG-as-reference-type (which doesn't 
necessarily need to mean "class") solves that particular problem without the 
constraints that static internal variables have.

> Maybe not *too* terrible for randomized alien invader attack patterns (unless it
> makes the game boring and doesn't sell), but a fairly major failure for security
> purposes.
>
> There's another issue, too:
>
> First a little background: With Hash_DRBG (and I would assume other crypto RNGs
> as well), the RNG is periodically reseeded, both automatically and on-demand.
> This reseeding is *not* like normal non-crypto reseeding: With non-crypto
> reseeding, you're fully resetting the internal state to a certain specific value
> and thus resetting the existing entropy, replacing it with the fresh new
> entropy. But with Hash_DRBG, reseeding only *adds* additional fresh entropy -
> nothing gets reset. Any existing entropy still remains. So reseeding two
> different Hash_DRBGs with the *same* reseed data *still* results in two
> completely different internal states. This is deliberately defined by the NIST
> spec.
>
> There are reasons for that, but one noteworthy side-consequence is this: If all
> your Hash_DRBG's share the same internal state, then anytime one is reseeded
> with fresh entropy, they *all* benefit from the fresh entropy, for free.
>
> And as a (maybe smaller) additional benefit, if different parts of your program
> are using an RNG independently of each other, but the RNGs internally share the
> same state, then *each* component contributes additional (semi-)non-determinism
> to the pool. That part's true of other RNGs too, but the effect is compounded
> further by Hash_DRBG which updates the internal state differently depending on
> how much data is requested at each, umm...at each request.

This is a very interesting point.  My understanding is that in many (most?) 
programs, each individual thread does typically operate using a single RNG 
instance anyway.  The question for me is whether that's a design choice of the 
developer or something that is an unavoidable outcome of the RNG design.

For example, it's readily possible to just instantiate a single RNG (crypto or 
otherwise, as required) at the start of the program and pass that around: if 
it's a reference type (as I would argue it should be) then the effects you 
desire will still take place.

Alternatively, one can also implement a thread-global RNG instance which 
functions will use.  This is already done with rndGen, which is effectively a 
singleton pattern.  There's no reason why one couldn't also define a cryptoGen 
which works in a similar way, just using an instance of a cryto RNG where rndGen 
uses a Mersenne Twister:
https://github.com/D-Programming-Language/phobos/blob/d2f2d34d52f89dc9854069b13f52523965a7107e/std/random.d#L1161-L1174
https://github.com/WebDrake/std.random2/blob/a071d8d182eb28516198bb292a0b45f86f4425fe/std/random2/generator.d#L60-L81

The benefit of doing it this way, as opposed to static internal variables, is 
that you aren't then constrained to have only one single, effectively 
thread-global instance of _every_ RNG you create.

> However...the mentions of Minecraft did raise one point that I'll concede: If
> you have a multiplayer environment (or more generally, a large chunk of shared
> multi-computer data) that's randomly-generated, then a very careful usage of a
> shared seed and RNG algorithm could drastically reduce the network bandwidth
> requirements.

You may also recall earlier games like Elite which were able to "store" whole 
universes on a single 5 1/4" floppy by virtue of auto-generating that universe 
from a repeatable random sequence.  It was amazing what could be done on the old 
BBC Micro :-)

> I do agree strongly that there's a major difference between "relying on
> deterministic sequence from an RNG" and "principle of design".
>
> However, I also maintain that the "principle of design" case demands you should
> *NOT* get the same results from RNGs unless you *specifically intend* to be
> "relying on deterministic sequence from an RNG". After all, they *are* supposed
> to be "random number generators". That's their primary function.
>
> I do believe strongly in the same principles of encapsulation that you do. But
> the thing is, the usual rules of proper encapsulated design are deliberately and
> fundamentally predicated on the assumption that you *want* reliably predictable
> deterministic behavior. The vast majority of the time, that's a correct
> assumption - but the whole *point* of an RNG is to *not* be deterministic. Or at
> least to get as close to non-determinism as reasonably possible within a
> fundamentally deterministic system.
>
> Since the basic goals of RNGs are in fundamental disagreement with the
> underlying assumptions of usual "well encapsulated" design, that calls into
> question the applicability of usual encapsulation rules to RNGs.
>
> At the risk of being presumptuous, I think you do agree on some level. Isn't
> that the whole reason you've proposed that RNGs change from structs to classes?
> Because you don't want identical sequences from RNGs unless *specifically*
> intended, right? The only parts of that I've intended to question are:

I completely agree that _unintended_ identical RNG sequences are a very bad 
thing that must be avoided.  I think that we're in disagreement only about how 
best to achieve that in a sane/safe/uncomplicated way.  With luck we will find 
something that works for both of us :-)

What I feel is that static internal variables go too far in the opposite 
direction: they make it impossible to have even _intentionally_ identical RNG 
sequences.  There's no way, for example, to .save or .dup an RNG instance with 
this design.

However, the effect of a common and reliable source of randomness, used by all 
parts of the program, can be implemented instead by a thread-global singleton 
instance of an RNG as described above.  This seems to me to be a better solution 
as it gives you what you achieve using static variables, but without preventing 
you from instantiating as many other independent RNG instances as you like.

> A. Does that really necessitate moving to classes?

No, the important distinction is value vs. reference types, not structs v. 
classes.  One could implement the RNGs as struct-based reference types.

I wrote a class-based implementation because I wanted to see how that came out 
to various struct-based approaches monarch_dodra and I had tried.  I do think 
that it offers much value in terms of simplicity and elegance of design, but 
there may be other costs that make it untenable.  I am not sure the correct 
choice will be apparent until the current work on memory allocation settles down.

> B. Are there any legitimate use-cases for "specifically relying on deterministic
> sequence from an RNG"?

Well, when I was writing large-scale scientific simulations, it was certainly 
useful to be able to re-run them with the same random sequence.  Given the 
number of random variates I was generating in the process, it was not really 
practical to store the sequence on memory or disk.  The same is true of many 
circumstances where one is writing a program that relies on randomness, but 
wants to test it reliably.

However, fundamentally this comes down to a design point.  Pseudo-random RNGs 
are _always_ deterministic in their operation once seeded.  The difference we're 
really talking about here is whether the source of randomness used by different 
parts of a program is thread-global or not.

And so, the question becomes rather, "Is it legitimate to enforce a 
thread-global source of randomness in all circumstances?"  I'd say the answer to 
that is a definite no.

Bear in mind that one nasty consequence of using static internal variables to 
force thread-global behaviour is that it means that the presence or absence of 
unittests might affect the actual running program.  Consider:

     struct SomeRNG { private static InternalState _internals; ... }

     unittest
     {
         SomeRNG rng;
         rng.seed(KnownSeed);
         // verify that SomeRNG produces expected sequence of variates
     }

Now when you start your _actual_ program, the internal state of SomeRNG will 
already have been set by the unittests.  Obviously if you are doing things 
properly you will scrub this by re-seeding the RNG at the start of your program 
proper, but the risk is clearly still there.

> For B, the above example of "reducing bandwidth/storage requirements for a large
> set of shared random-generated data" is making me question my former stance of
> "No, there's no legitimate use-case". If B falls (and I suppose it maybe it
> does), then A does too, and classes would indeed be necessary.

Yes, I think that is one very good example of a use-case, which is probably one 
shared between a bunch of different applications in practice (scientific 
simulation, games, probably other stuff too).

As I said before, I don't think it mandates _classes_, but it does mandate 
reference-type RNGs that are properly encapsulated.

> But that's all for non-crypto RNGs. For crypto-RNGs, determinism is *never*
> anything more than a concession forced by the deterministic nature of the
> machines themselves. FWIW, this does mean  crypto-RNGs can go either struct or
> class, since the internal states really should be tied together anyway (in order
> to prevent their *outputs* from being tied together).

What do you think about the global-singleton-instance pattern as a way of 
achieving what you want?

I think I will stop my reply here for now, because I think that your response to 
this question (and the explanations leading up to it) probably determines how I 
will respond to your later remarks.  What are your thoughts?

Best wishes,

     -- Joe