[ python-Bugs-917055 ] add a stronger PRNG

[SourceForge.net]

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.

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

>Comment By: paul rubin (phr)
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?

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

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