[ python-Bugs-917055 ] add a stronger PRNG

[SourceForge.net]

Bugs item #917055, was opened at 2004-03-15 21:46
Message generated for change (Comment added) made by rhettinger
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=105470&aid=917055&group_id=5470

Category: Python Library
Group: Feature Request
Status: Open
Resolution: None
Priority: 5
Submitted By: paul rubin (phr)
Assigned to: Raymond Hettinger (rhettinger)
Summary: add a stronger PRNG

Initial Comment:
The default Mersenne Twister algorithm in the Random
module is very fast but makes no serious attempt to
generate output that stands up to adversarial analysis.
 Besides cryptography applications, this can be a
serious problem in areas like computer games.  Sites
like www.partypoker.com routinely run online
tournaments with prize funds of 100K USD or more. 
There's big financial incentives to find ways of
guessing your opponent's cards with better than random
chance probability.  See bug #901285 for some
discussion of possible correlations in Mersenne
Twister's output.

Teukolsky et al discuss PRNG issues at some length in
their book "Numerical Recipes".  The original edition
of Numerical Recipes had a full blown version of the
FIPS Data Encryption Standard implemented horrendously
in Fortran, as a way of making a PRNG with no easily
discoverable output correlations.  Later editions
replaced the DES routine with a more efficient one
based on similar principles.

Python already has an SHA module that makes a dandy
PRNG.  I coded a sample implementation:

http://www.nightsong.com/phr/python/sharandom.py

I'd like to ask that the Python lib include something
like this as an alternative to MT.  It would be similar
to the existing whrandom module in that it's an
alternative subclass to the regular Random class.  The
existing Random module wouldn't have to be changed.

I don't propose directly including the module above,
since I think the Random API should also be extended to
allow directly requesting pseudo-random integers from
the generator subclass, rather than making them from
floating-point output.  That would allow making the
above subclass work more cleanly.  I'll make a separate
post about this, but first will have to examine the
Random module source code.

----------------------------------------------------------------------

>Comment By: Raymond Hettinger (rhettinger)
Date: 2004-03-16 06:49

Message:
Logged In: YES 
user_id=80475

It would have been ideal if the Random API had been 
designed with an integer generator at the core and floating 
point as a computed value, but that it the way it has been for 
a long time and efforts to switch it over would likely result in 
either incompatibility with existing subclasses or introducing 
new complexity (making it even harder to subclass).  I think 
the API should be left alone until Py3.0.

The attached module would make a good recipe on ASPN 
where improvements and critiques can be posted.  Do you 
have links to research showing that running SHA-1 in a 
cipher block feedback mode results in a cryptographically 
strong random number generator -- the result seems likely, 
but a research link would be great.  Is there a link to 
research showing the RNG properties of the resulting 
generator (period, equidistribution, passing tests for 
randomness, etc)?  Also, is there research showing the 
relative merits of this approach vs MD5, AES, or DES?

If something like this gets added to the library, I prefer it to 
be added to random.py using the existing API.  Adding yet 
another random module would likely do more harm than 
good.

One other question (I don't know the answer to this):  would 
including a cryptographically strong RNG trigger US export 
restrictions on the python distribution?

----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=105470&aid=917055&group_id=5470