Re: SHA-based subclass for random module

From: Paul Rubin (//phr.cx_at_NOSPAM.invalid)
Date: 03/22/04 

Date: 21 Mar 2004 15:16:02 -0800

python@rcn.com (Raymond Hettinger) writes:
> > If we're selecting a PRNG for a third
> > time, let's stop cutting corners and take care of the problem once and
> > for all.
>
> No corners were cut. MT is a state-of-the-art psuedo random number
> generator. The problem is that you want encryption.

This sha prng module was motivated partly by your own remark in sf bug
#901285 that MT output may not be sufficiently correlation-free if you
take pairs of 16-bit integers from it, in a context having nothing to
do with encryption. Anyway, despite how it may sound, I don't have
any desire to use the random module for encryption (I'd use different
API's for that). I just want to be able to write applications that
use random numbers without having any doubts about whether the random
numbers are good enough. Teukolsky et al in "Numerical Recipes",
which is not a cryptography book, explain that a good way to do that
is to use cryptographic primitives, so I'm proposing a module that
does it that way.

The application in numerics could be something like: I run some
half-hour simulation using MT, and get results that subjectively seem
a bit peculiar. So I run it again using the crypto-based generator
and maybe that takes three hours, but if I still see similarly
peculiar-looking results, I now can be pretty confident that it's not
some consequence of the RNG internals. It subjectively seems to me
that the Gnome version of Freecell is easier to play than the Windows
version (i.e. it deals easier hands), so that's a semi-real-world
example of this situation. (In this instance I suspect Freecell is
using some pathetic linear PRNG or something like that, but I haven't
yet bothered to look at the code).

There's also some applications (like online games) that need secure
random numbers, as mentioned in 917055. The people implementing these
things usually aren't even thinking about cryptography.

> > No, I wanted cryptographic strength to both the left and right,
>
> That makes sense. Still, the hashing step protects you. Given a
> series of 10,000 bits from the generator, do you have any means of
> deducing either a) the state of MT, b) what came before, or c) what
> comes after?

Cryptographic strength to the left means I shouldn't be able to
recover what came before, even given the current output of getstate()
on the generator (see the Yarrow paper for some rationale for wanting
this protection). I haven't seen any claim that MT was designed to
resist that.

I'm not adamant that this is a crucial property of a deterministic
PRNG; I implemented it because I saw it as straightforward to do and
figured it might as well be included, so that we can say that we did
the most thorough possible job, followed the Yarrow paper's
prescriptions, etc. If there's a deliberate decision to abandon the
property, that can make the generator a bit simpler and faster, and
I'm willing to code one that way for purposes of comparison. I just
don't think such decisions should be driven by implementation
accidents. (They should also be documented).

> I'm keeping an open mind but will abandon this patch unless the tone
> improves.

I don't mean to bash anyone and I'm sorry if it came across that way.
As I see it, the Random module provides an extensible API so that it's
easy to add different kinds of generators that the user can select
from depending on his or her needs. It then supplies the WH generator
(I guess for backwards compatibility) and the MT generator (for
reasonably good output and very high performance). The philosophy of
this sha module (as I see it) is to supply a third alternative in that
same flexible spirit: one that goes all-out to make the best possible
output, even if that results in only reasonable performance, while
also having increased portability through use of a standard underlying
primitive. Do you also see that as an appropriate goal? If not, we
should try to identify exactly what we're trying to do instead.

Relevant Pages

  • Re: SHA-based subclass for random module
    ... The problem is that you want encryption. ... >This sha prng module was motivated partly by your own remark in sf bug ... So I run it again using the crypto-based generator ... mathematicians who wanted to sell my company a better statistics tool. ...
    (comp.lang.python)
  • MT19337 for stream encryption?
    ... I am a novice at cryptography, so excuse my intrusion, but I'd like to ... Our application needs a very fast yet secure encryption method. ... We would, of course, forego using the PRNG seed generator for MT19337 ...
    (sci.crypt)
  • Re: Question About Cryptographically Hashing a Hash (SHA-512), Then Hashing That Hash, Etc.
    ... random number generator is initialized, ... because the "cycle" is all of the ... Aren't you confusing PRNG and TRNG here? ...
    (sci.crypt)
  • Re: Pseudo Random Number Generator test results
    ... definition of algorithmic randomness, but the point is that there is no ... A more useful criterion for a software PRNG is that there is no ... cryptography, and such PRNG's are sometimes called CPRNG's or CSPRNG's ... message is just XOR it with the CTR output, but you can also use the CTR ...
    (comp.lang.forth)
  • Re: Question About Cryptographically Hashing a Hash (SHA-512), Then Hashing That Hash, Etc.
    ... Another implication is that this a very weak generator, ... Aren't you confusing PRNG and TRNG here? ... But nobody has claimed that this LCG is a TRNG. ... never repeating until the whole cycle is NOT a feature of any ...
    (sci.crypt)