[Python-ideas] Should our default random number generator be secure?

[M.-A. Lemburg]

On 14.09.2015 23:19, Robert Kern wrote:
> On 2015-09-14 21:56, Sturla Molden wrote:
>> On 14/09/15 22:45, Robert Kern wrote:
>>> On 2015-09-14 20:07, Sturla Molden wrote:
>>>> On 14/09/15 19:15, M.-A. Lemburg wrote:
>>>>
>>>>> I am well aware that MT doesn't satisfy all empirical tests
>>>>> and also that it is not a CSPRNG
>>>>
>>>>> However, it has been extensively studied and it is proven to be
>>>>> equidistributed which is a key property needed for it to be used as
>>>>> basis for other derived probability distributions (as it done by the
>>>>> random module).
>>>>
>>>> And with this criterion, only MT and certain PCG generators are
>>>> acceptable.
>>>> Those are (to my knowledge) the only ones with proven equidistribution.
>>>
>>> Do not confuse k-dimensional equidistribution with "equidistribution".
>>> The latter property (how uniformly a single draw is distributed) is the
>>> one that the derived probability distributions rely upon, not the
>>> former.
>>
>> Yes, there was something fishy about this. k-dimensional equidistribution
>> matters if we simulate a k-dimensional tuple, as I understand it.
> 
> Yeah, but we do that every time we draw k numbers in a simulation at all. And we usually draw
> millions. In that case, perfect k=623-dimensional equidistribution is not really any better than
> k=1, provided that the PRNG is otherwise good.

Depends on your use case, but the fact that you can prove it is
what really matters - well, at least for me :-)

> The requirement for a good PRNG for simulation work is that it be *well* distributed in reasonable
> dimensions, not that it be *exactly* equidistributed for some k. And well-distributedness is exactly
> what is tested in TestU01. It is essentially a collection of simulations designed to expose known
> statistical flaws in PRNGs. So to your earlier question as to which is more damning, failing TestU01
> or not being perfectly 623-dim equidistributed, failing TestU01 is.

TestU01 includes tests which PRNGs of the MT type have trouble passing, since
they are linear. This makes them poor choices for crypto applications,
but does not have much effect on simulations using only a tiny part of the
available period.

For MT there's an enhanced version called SFMT which performs better
in this respect:

http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/M062821.pdf

(the paper also discusses the linear dependencies)

See http://www.jstatsoft.org/v50/c01/paper for a discussion of MT vs.
SFMT.

You can also trick TestU01 to have all tests pass by applying a non-linear
transformation (though I don't really see the point in doing this).

The WELL family of generators is an newer development, which provides
even better characteristics:

http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng.pdf

Also note that by seeding the MT in Python with truly random
data, the shortcomings of MT w/r to having problems escaping
"zeroland" (many 0 bits in the seed) are mostly avoided.

Anyway, it's been an interesting discussion, but I think it's time
to let go :-)

Here's a firt cut at an implementation of the idea to use OpenSSL's
rand API as basis for an RNG. It even supports monkey patching
the random module, though I don't think that's good design.

""" RNG based on OpenSSL's rand API.

    Marc-Andre lemburg, 2015. License: MIT

"""
# Needs OpenSSL installed: pip install egenix-pyopenssl
from OpenSSL import rand
import random, struct, binascii

# Number of bits in an IEEE float
BITS_IN_FLOAT = 53

# Scale to apply to RNG output to make uniform
UNIFORM_SCALING = 2 ** -BITS_IN_FLOAT

### Helpers

# Unpacker
def str2long(value):

    value_len = len(value)

    if value_len <= 4:
        if value_len < 4:
            value = '\0' * (4 - value_len) + value
        return struct.unpack('>L', value)[0]

    elif value_len <= 8:
        if value_len < 8:
            value = '\0' * (8 - value_len) + value
        return struct.unpack('>Q', value)[0]

    return long(binascii.hexlify(value), 16)

###

class OpenSSLRandom(random.Random):

    """ RNG using the OpenSSL rand API, which provides a cross-platform
        cryptographically secure RNG.

    """
    def random(self):

        """ Return a random float from [0.0, 1.0).

        """
        return (str2long(rand.bytes(7)) >> 3) * UNIFORM_SCALING

    def getrandbits(self, bits):

        """ Return an integer with the given number of random bits.

        """
        if bits <= 0:
            raise ValueError('bits must be >0')

        if bits != int(bits):
            raise TypeError('bits must be an integer')

        # Get enough bytes for the requested number of bits
        numbytes = (bits + 7) // 8
        x = str2long(rand.bytes(numbytes))

        # Truncate bits, if needed
        return x >> (numbytes * 8 - bits)

    def seed(self, value=None):

        """ Feed entropy to the RNG.

            value may be None, an integer or a string.

            If None, 2.5k bytes data are read from /dev/urandom and
            fed into the RNG.

        """
        if value is None:
            try:
                value = random._urandom(2500)
                entropy = 2500
            except NotImplementedError:
                return
        if isinstance(value, (int, long)):
            value = hexlify(value)
            entropy = len(value)
        else:
            value = str(value)
            entropy = len(value)

        # Let's be conservative regarding the available entropy in
        # value
        rand.add(value, entropy / 2)

    def _notimplemented(self, *args, **kwds):

        raise NotImplementedError(
            'OpenSSL RNG does not implement this method')

    getstate =  _notimplemented
    setstate = _notimplemented

### Testing

def install_as_default_rng():

    """ Monkey patch the random module

    """
    _inst = OpenSSLRandom()
    random._inst = _inst
    for attr in ('seed',
                 'random',
                 'uniform',
                 'triangular',
                 'randint',
                 'choice',
                 'randrange',
                 'sample',
                 'shuffle',
                 'normalvariate',
                 'lognormvariate',
                 'expovariate',
                 'vonmisesvariate',
                 'gammavariate',
                 'gauss',
                 'betavariate',
                 'paretovariate',
                 'weibullvariate',
                 'getstate',
                 'setstate',
                 'jumpahead',
                 'getrandbits',
                 ):
        setattr(random, attr, getattr(_inst, attr))

def _test():

    # Install
    install_as_default_rng()

    # Now run the random module tests
    random._test()

###

if __name__ == '__main__':
    _test()

-- 
Marc-Andre Lemburg
eGenix.com

Professional Python Services directly from the Experts (#1, Sep 14 2015)
>>> Python Projects, Coaching and Consulting ...  http://www.egenix.com/
>>> Python Database Interfaces ...           http://products.egenix.com/
>>> Plone/Zope Database Interfaces ...           http://zope.egenix.com/
________________________________________________________________________
2015-09-14: Released mxODBC Plone/Zope DA 2.2.3   http://egenix.com/go84
2015-09-18: PyCon UK 2015 ...                               4 days to go
2015-09-26: Python Meeting Duesseldorf Sprint 2015         12 days to go

   eGenix.com Software, Skills and Services GmbH  Pastor-Loeh-Str.48
    D-40764 Langenfeld, Germany. CEO Dipl.-Math. Marc-Andre Lemburg
           Registered at Amtsgericht Duesseldorf: HRB 46611
               http://www.egenix.com/company/contact/