isUniformRNG

Nick Sabalausky via Digitalmars-d digitalmars-d at puremagic.com
Sun May 4 10:42:58 PDT 2014


On 5/4/2014 11:38 AM, Joseph Rushton Wakeling via Digitalmars-d wrote:
> On 04/05/14 16:28, Nick Sabalausky via Digitalmars-d wrote:
>> On a general level, I'm trying to grok the whole intent of
>> isUniformRNG and see
>> whether or not anything else may ever be needed in addition to
>> isUniformRNG. I'm
>> not trying to push an "isRNG", just trying to understand std.random's
>> current
>> intentions and reasoning, so I know how to work with it appropriately.
>
> Yea, it's a good question.  I think I would answer it as follows.
>
> [...]
>

Ok, I see. Thanks.

>> But more immediately, since Phobos lacks a crypto-secure RNG, I'm
>> implementing
>> NIST's Hash_DRBG (backed by the OS-provided
>> RtlGenRandom/CryptGenRandom and
>> "/dev/random" as entropy sources). Hopefully I can get it into a
>> Phobos-acceptable state.
>
>
> That's great -- I really look forward to seeing your work :-)  Can you
> give me some links to the spec?
>

The spec for Hash_DRBG is in "NIST Special Publication 800-90A" which 
also includes a few other crypto RNGs (including, unfortunately, the one 
with a known NSA backdoor, Dual_EC_DRBG, but it's easy enough to just 
not bother implementing that one):

http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf

That paper is linked to from here (seems to be down right now though):

http://csrc.nist.gov/groups/ST/toolkit/random_number.html

Which I found from here:

http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator#Standards


>> Now, I can follow the spec for the Hash_DRBG algorithm well enough,
>> but I'm not
>> really solid on random-number theory, so I can't be certain whether or
>> not
>> isUniformRNG is appropriate for this. I would assume "yes", but I
>> don't want to
>> assume. Hence my inquiries.
>
> I don't know that this necessarily needs too much in the way of
> random-number theory, but there are 3 questions that really need
> answering here:
>
>     * What's the type of number that this algorithm produces?
>

Just a string of random bits. Effectively unsigned integers.

>     * What's the min and max values produced, and are these
>       inclusive bounds, i.e. are the random numbers drawn
>       from the closed [min, max] interval?
>

It's all based on SHA hashes (of seeds, internal state, and some other 
stuff) and it doesn't explicitly exclude any output values. So if SHA is 
working as expected, then yea, I'd imagine it should be a closed 
interval over [0, 2^numBitsRequested - 1] where "numBitsRequested" is 
permitted by the spec to be any positive integer.

>     * Are these numbers uniformly distributed?
>

This is the part I've been a little unclear on, although maybe I'm just 
being paranoid about it. Doesn't a uniform distribution carry certain 
reliable statistical properties? I don't know whether that could be used 
to improve the likelihood of guessing future values. If so, then maybe 
the algorithm is designed to avoid that?

Then again, wouldn't the only alternative to uniform distribution be a 
weighted distribution? I can't imagine an RNG intended for crypto would 
be deliberately weighted (unless maybe there were some randomness to the 
weights...if that even makes any sense at all).

Maybe I'm just overthinking it?



More information about the Digitalmars-d mailing list