[PYTHON-CRYPTO] CSPRNG schemes : Any comments?

[Andrew Archibald]

On Thu, Feb 15, 2001 at 10:29:17PM -0500, Bryan Mongeau wrote:
> > By the "GIL" you mean the Python interpreter lock in ceval.c?  That does
> > its swapping purely on user-space instructions, not hardware clock
> > cycles.  Seems to me the cryptographers are right.
>
> This is precisely the type of constructive input I was searching for.
> "Cycles" was terminology faux pas, I should have used "python virtual
> instructions" instead. I believe nevertheless that this thread swarm does
> produce true entropy. After all the primary goal of a CSPRNG and cryptography
> in general is not to make things impossible to defaet, but so diificult as to
> put it beyond everyone's reach.

Hmm.  Well, here's another terminological quibble:  the literature in
general seems to use "cryptographically strong pseudo-random number
generator" to mean a deterministic process which produces numbers which are
computationally infeasible to distinguish from randomness without knowing
the seed data.  (See Schneier's Applied Cryptography, p. 45, for example).

On the other hand, (drawing from the same source) a real random number
generator is one which produces genuinely unpredictable output, no matter
how much computational power is brought to bear.  Most sources are not
acutally completely random (disk timings) but do contain a few bits of
genuine unpredictability.

To get an unpredictable random number generator, you should use a CSPRNG
(using Schneier's terminology) and seed it with a genuine random number
generator.  And re-seed it, periodically, at controlled intervals and in
controlled amounts.

The key thing that seems to be missing from your scheme is any clear way to
estimate how much genuine unpredicatbility there is, coming from your race
conditions.  This is likely to depend on things like IO behaviour, platform
(are your threads pure python, OS threads, different CPUs, Java threads,
what?) and any number of other criteria which will be very difficult for
you to estimate.  So it will be very difficult to tell when you've
accumulated enough randomness to safely generate your RSA keys (for
example).

You should read the design documents for Yarrow.
http://www.counterpane.com/yarrow.html

It seems like your scheme might have some merit as a random input source
for Yarrow's generator if you could estimate how much unpredictability
it was generating.

> > > So far this defense has met with little acceptance, but this is to be
> > > expected in the crypto field. After all, most cryptographers will still
> > > blindly choose RSA over Elliptic Curves simply because they feel safer
> > > all sticking together, even though ECC is ten times as fast and has a key
> > > size that increases exponentially in security. For example, 160 bit ECC
> > > is equivalent to 1024 bit RSA whereas 256 bit ECC roughly equates to 4096
> > > bits in RSA.
> >
> > Oh dear, you're losing credibility fast.
>
> This is not constructive commentary. If you are referring to my CSPRNG
> scheme, then granted it is imperfect if used alone. If you are referring to
> my key strength approximations (which is what you quoted), then I invite you
> to look at:
>
> http://softlab.od.ua/products/ecbackup/info.html
>
> and draw your own conclusions. I admit to an approximation for brevity's sake.

Having read this and any number of other discussions of elliptic curves and
cryptography, I can agree with the statement that nobody understands
elliptic curves well enough to write good algorithms for them yet.
However, there are a great number of people looking very hard at them,
trying to understand them better.  Until people are more convinced that
there really is no faster algorithm for computing on elliptic curves, I'll
pay the minimal penalty for using mod p.

That page, by the way, is a very worrisome source of cryptographic data.
It never even hints at the possibility that a faster algorithm for
cracking ECC systems will be found.  How long did NFS take to discover
for numbers mod p?

But it would be nice to have an ECC implementation for python, to play
with.  Volunteer?

Andrew Archibald