Bugs item #917055, was opened at 2004-03-16 02:46 Message generated for change (Comment added) made by phr 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-17 09:05

Message: Logged In: YES user_id=72053

There are no research results that I know of that can distinguish the output of sha1-ofb from random output in any practical way. To find such a distinguisher would be a significant result. It's a safe bet that cryptographers have searched for distinguishers, though I don't promise to have heard of every result that's been published. I'll ask on sci.crypt if anyone else has heard of such a thing, if you want. SHA1-HMAC is generally considered to be indistinguishable from a PRF (pseudorandom function, i.e. a function selected at random from the space of all functions from arbitrary strings to 160-bit outputs; this term is from concrete security theory). MD5 is deprecated these days and there's no point to using it instead of sha1 for this.

I'm not sure what happens if randint is added to the API. If you subclass Random and don't provide a randint method, you inherit from the base class, which can call self.random() to get floats to make the ints from.

US export restrictions basically don't exist any more. In principle, if you want to export something, you're supposed to send an email to an address at the commerce department, saying the name of the program and the url where it can be obtained and a few similar things. In practice, email to that address is ignored, they never check anything. I heard the address even stopped working for a while, though they may have fixed it since then. See http://www.bxa.doc.gov/Encryption/ for info. I've emailed notices to the address a few times and never heard back anything. Anyway, I don't think this should count as cryptography; it's simply using a cryptographic hash function as an PRNG to avoid the correlations in other PRNG's; scientific rationale for doing that is given in the Numerical Recipes book mentioned above.

The code that I linked uses the standard API but I wonder if the floating point output is optimally uniform, i.e. the N/2**56 calculation may not be exactly the right thing for an ieee float64.

Using the time of day is what the Random docs say to do by default. You're correct that any security application needs to supply a higher entropy seed.

I would like it very much if the std lib included a module that read some random bytes from the OS for OS's that support it. That means reading /dev/urandom on recent Un*x-ish systems or Cygwin, or calling CryptGenRandom on Windows. Reading /dev/urandom is trivial, and there's a guy on the pycrypt list who wrote a Windows function to call CryptGenRandom and return the output through the Python API. I forwarded the function to Guido with the author's permission but nothing seemed to happen with it. However, this gets away from this sharandom subclass. I'd like to make a few more improvements to the module but after that I think it can be dropped into the lib. Let me know what you think.

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

Comment By: Raymond Hettinger (rhettinger) Date: 2004-03-16 11: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 11: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?

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