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.

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

Date: 2004-03-16 06:52

Message: Logged In: YES user_id=80475

One other thought: if cryptographic strength is a goal, then seeding absolutely should require a long seed (key) as an input and the time should *never* be used.

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

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?

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