[PYTHON-CRYPTO] CSPRNG schemes : Any comments?

[Jeremy Hylton]

>>>>> "BM" == Bryan Mongeau <bryan at EEVOLVED.COM> writes:

  >> BTW, there is a Yarrow-160 implementation included in Pisces at
  >> http://www.cnri.reston.va.us/software/pisces

  BM> As for your Yarrow-160 implementation, I examined and tested it,
  BM> but ultimately needed more entropy than it could provide. But I

The Yarrow implementation has a few trivial entropy sources, but I
didn't make any effort to provide good sources.  On the other hand,
the source of entropy is orthogonal.  You could write your own sources
and use the rest of the implementation.

  BM> did have a few questions I would like to bounce off you now that
  BM> we're on that topic, if you don't mind. These popped into my
  BM> mind this morning:

  BM> 1- Why doesn't anyone use a block cipher in CBC mode to make
  BM> things even more funky in the random pools? The initialization
  BM> vector could be a hash slice of a given entropy pool... The
  BM> Yarrow specs uses 3des in counter mode, you use ECB.

The amkCrypto implementation does provide a counter mode.  I may be
incorrect, but I thought I had implemented counter mode using ECB.
The actual cipher call is to encrypt the counter using ECB.  Is this
incorrect? (It seems correct given the defintion in Sec. 5.1 of the
Yarrow paper.)

  BM> 2- I noticed in the Yarrow 160 spec section 4.2 that entropy
  BM> sources are closely tied to a given pool, be it the fast or slow
  BM> to prevent bogus entropy sources from reseeding the PRNG
  BM> continously. However, in the addSource() method, you add an
  BM> entropy source to both pools. Additionally, the addInput()
  BM> method alternates between pools, effectively leaving the PRNG
  BM> open to an iterative guessing attack should one entropy source
  BM> be vastly overestimating its contribution.

Sec. 5.2 of the Yarrow design ("Entropy Accumulator") says:

    Once we have collected enough entropy we apply the hash functions
    h to the concatenation of all inputs.  We alternate applying
    samples from each source to each pool.

I don't understand the kind of attack you mention, but agree that an
entropy source that vastly overestimates its contribution is a bad
thing.

  BM>                                            Also the
  BM> slowIntoFast() method calls addInput() which has a 50% chance of
  BM> adding the slow pool to the slow pool... As AMK would say, it's
  BM> a Bad Thing. :) Am I missing something here?

Yes.  There are two classes with addInput methods -- the
EntropyAccumulator and the Yarrow main class.  The slowIntoFast()
method calls addInput() on the fast pool directly.  This is *not* the
addInput() method on the Yarrow instance.

  BM> Don't get me wrong, I don't think your implementation is
  BM> insecure in any way.  In fact I believe it to be quasi
  BM> unbreakable.  I simply have issues with Yarrow and its rigid
  BM> implementation.

I'm the implementor not the designer :-).

  BM>                  Entropy collection routines are fine if you're
  BM> running a daemon or an entropy server that is given a period of
  BM> time to accumulate sufficient entropy, but most applications
  BM> require entropy on demand. Take for example pgp keygen that
  BM> prompts you to pound the keyboard until it's got enough
  BM> randomness. Effective granted, but crude.

Pisces comes with a Yarrow daemon that you could use for this
purpose.  I agree that collecting entropy is hard, e.g deciding what
sources to use and how to estimate the entropy they produce.

  BM> Here is a theory I would appreciate salient commentary on:

sci.crypt is probably a better place than python-crypto.  I don't know
the backgrounds of the contributors here well enough to have much
trust in their cryptographic expertise.  I place more stock in an
opinion from sci.crypt.  I'm sure we can develop good crypto APIs, but
I don't expect we'll be development new algorithms or techniques.

  BM> My defense lies partly in python's GIL, which by default is
  BM> acquired and released every 10 cycles (I believe). This constant
  BM> acquisition and release process, in conjunction with the other
  BM> system processes, has an effect of making *all* system
  BM> activities ( keyboard hits, mouse movements, disk and network
  BM> I/O, running hardware drivers, other processes running, etc.)
  BM> influence the overall outcome of the thread race. Iterate the
  BM> algorithm for a given number of rounds, and you have effectively
  BM> created an PRNG scheme that encompasses all the other methods of
  BM> entropy accumulation.

As others have said, Python's interpreter lock is released every 10
cycles.  What happens as a result of that depends on which thread are
runnable and how the OS and thread library do scheduling.  I wouldn't
expect to get much entropy out of it.

Jeremy