Check in a branch with a major redesign on how entropy polling is performed.

Combine the fast and slow polls, into a single poll() operation.

Instead of being given a buffer to write output into, the EntropySource is
passed an Entropy_Accumulator. This handles the RLE encoding that xor_into_buf
used to do. It also contains a cached I/O buffer so entropy sources do not
individually need to allocate memory for that with each poll. When data
is added to the accumulator, the source specifies an estimate of the number
of bits of entropy per byte, as a double. This is tracked in the accumulator.
Once the estimated entropy hits a target (set by the constructor), the
accumulator's member function predicate polling_goal_achieved flips to true.
This signals to the PRNG that it can stop performing polling on sources,
also polls that take a long time periodically check this flag and return
immediately.

The Win32 and BeOS entropy sources have been updated, but blindly; testing
is needed.

The test_es example program has been modified: now it polls twice and outputs
the XOR of the two collected results. That helps show if the output is consistent
across polls (not a good thing). I have noticed on the Unix entropy source,
occasionally there are many 0x00 bytes in the output, which is not optimal.
This also needs to be investigated.

The RLE is not actually RLE anymore. It works well for non-random inputs
(ASCII text, etc), but I noticed that when /dev/random output was fed into
it, the output buffer would end up being RR01RR01RR01 where RR is a random
byte and 00 is the byte count.

The buffer sizing also needs to be examined carefully. It might be useful
to choose a prime number for the size to XOR stuff into, to help ensure an
even distribution of entropy across the entire buffer space. Or: feed it
all into a hash function?

This change should (perhaps with further modifications) help WRT the
concerns Zack W raised about the RNG on the monotone-dev list.

2 files changed, 67 insertions, 95 deletions

diff --git a/src/rng/randpool/randpool.cpp b/src/rng/randpool/randpool.cpp
index e35ee22ca..594916a84 100644
--- a/src/rng/randpool/randpool.cpp
+++ b/src/rng/randpool/randpool.cpp
@@ -1,7 +1,7 @@
-/*************************************************
-* Randpool Source File                           *
-* (C) 1999-2008 Jack Lloyd                       *
-*************************************************/
+/*
+* Randpool Source File
+* (C) 1999-2009 Jack Lloyd
+*/
 
 #include <botan/randpool.h>
 #include <botan/loadstor.h>
@@ -14,9 +14,9 @@ namespace Botan {
 
 namespace {
 
-/*************************************************
-* PRF based on a MAC                             *
-*************************************************/
+/**
+* PRF based on a MAC
+*/
 enum RANDPOOL_PRF_TAG {
    CIPHER_KEY = 0,
    MAC_KEY    = 1,
@@ -25,14 +25,14 @@ enum RANDPOOL_PRF_TAG {
 
 }
 
-/*************************************************
-* Generate a buffer of random bytes              *
-*************************************************/
+/**
+* Generate a buffer of random bytes
+*/
 void Randpool::randomize(byte out[], u32bit length)
    {
    if(!is_seeded())
       {
-      reseed();
+      reseed(8 * mac->OUTPUT_LENGTH);
 
       if(!is_seeded())
          throw PRNG_Unseeded(name());
@@ -49,15 +49,15 @@ void Randpool::randomize(byte out[], u32bit length)
       }
    }
 
-/*************************************************
-* Refill the output buffer                       *
-*************************************************/
+/**
+* Refill the output buffer
+*/
 void Randpool::update_buffer()
    {
    const u64bit timestamp = system_time();
 
-   for(u32bit j = 0; j != counter.size(); ++j)
-      if(++counter[j])
+   for(u32bit i = 0; i != counter.size(); ++i)
+      if(++counter[i])
          break;
    store_be(timestamp, counter + 4);
 
@@ -65,17 +65,17 @@ void Randpool::update_buffer()
    mac->update(counter, counter.size());
    SecureVector<byte> mac_val = mac->final();
 
-   for(u32bit j = 0; j != mac_val.size(); ++j)
-      buffer[j % buffer.size()] ^= mac_val[j];
+   for(u32bit i = 0; i != mac_val.size(); ++i)
+      buffer[i % buffer.size()] ^= mac_val[i];
    cipher->encrypt(buffer);
 
    if(counter[0] % ITERATIONS_BEFORE_RESEED == 0)
       mix_pool();
    }
 
-/*************************************************
-* Mix the entropy pool                           *
-*************************************************/
+/**
+* Mix the entropy pool
+*/
 void Randpool::mix_pool()
    {
    const u32bit BLOCK_SIZE = cipher->BLOCK_SIZE;
@@ -90,10 +90,10 @@ void Randpool::mix_pool()
 
    xor_buf(pool, buffer, BLOCK_SIZE);
    cipher->encrypt(pool);
-   for(u32bit j = 1; j != POOL_BLOCKS; ++j)
+   for(u32bit i = 1; i != POOL_BLOCKS; ++i)
       {
-      const byte* previous_block = pool + BLOCK_SIZE*(j-1);
-      byte* this_block = pool + BLOCK_SIZE*j;
+      const byte* previous_block = pool + BLOCK_SIZE*(i-1);
+      byte* this_block = pool + BLOCK_SIZE*i;
       xor_buf(this_block, previous_block, BLOCK_SIZE);
       cipher->encrypt(this_block);
       }
@@ -101,61 +101,33 @@ void Randpool::mix_pool()
    update_buffer();
    }
 
-/*************************************************
-* Reseed the internal state                      *
-*************************************************/
-void Randpool::reseed()
+/**
+* Reseed the internal state
+*/
+void Randpool::reseed(u32bit poll_bits)
    {
-   SecureVector<byte> buffer(128);
+   Entropy_Accumulator accum(poll_bits);
 
-   u32bit entropy_est = 0;
-
-   /*
-   When we reseed, assume we get 1 bit per byte sampled.
-
-   This class used to perform entropy estimation, but what we really
-   want to measure is the conditional entropy of the data with respect
-   to an unknown attacker with unknown capabilities.  For this reason
-   making any sort of sane estimate is impossible. See also
-      "Boaz Barak, Shai Halevi: A model and architecture for
-       pseudo-random generation with applications to /dev/random. ACM
-       Conference on Computer and Communications Security 2005."
-   */
-
-   // First do a fast poll of all sources (no matter what)
-   for(u32bit j = 0; j != entropy_sources.size(); ++j)
+   for(u32bit i = 0; i != entropy_sources.size(); ++i)
       {
-      u32bit got = entropy_sources[j]->fast_poll(buffer, buffer.size());
-
-      mac->update(buffer, got);
-      entropy_est += got;
-      buffer.clear();
-      }
+      entropy_sources[i]->poll(accum);
 
-   // Then do a slow poll, until we think we have got enough entropy
-   for(u32bit j = 0; j != entropy_sources.size(); ++j)
-      {
-      u32bit got = entropy_sources[j]->slow_poll(buffer, buffer.size());
-
-      mac->update(buffer, got);
-      entropy_est += got;
-
-      if(entropy_est > 512)
+      if(accum.polling_goal_achieved())
          break;
-      buffer.clear();
       }
 
-   SecureVector<byte> mac_val = mac->final();
+   SecureVector<byte> mac_val = mac->process(accum.get_entropy_buffer());
 
    xor_buf(pool, mac_val, mac_val.size());
    mix_pool();
 
-   entropy = std::min<u32bit>(entropy + entropy_est, 8 * mac_val.size());
+   entropy = std::min<u32bit>(entropy + accum.bits_collected(),
+                              8 * mac_val.size());
    }
 
-/*************************************************
-* Add user-supplied entropy                      *
-*************************************************/
+/**
+* Add user-supplied entropy
+*/
 void Randpool::add_entropy(const byte input[], u32bit length)
    {
    SecureVector<byte> mac_val = mac->process(input, length);
@@ -166,25 +138,25 @@ void Randpool::add_entropy(const byte input[], u32bit length)
    entropy = std::min<u32bit>(entropy + length, 8 * mac_val.size());
    }
 
-/*************************************************
-* Add another entropy source to the list         *
-*************************************************/
+/**
+* Add another entropy source to the list
+*/
 void Randpool::add_entropy_source(EntropySource* src)
    {
    entropy_sources.push_back(src);
    }
 
-/*************************************************
-* Check if the the pool is seeded                *
-*************************************************/
+/**
+* Check if the the pool is seeded
+*/
 bool Randpool::is_seeded() const
    {
    return (entropy >= 7 * mac->OUTPUT_LENGTH);
    }
 
-/*************************************************
-* Clear memory of sensitive data                 *
-*************************************************/
+/**
+* Clear memory of sensitive data
+*/
 void Randpool::clear() throw()
    {
    cipher->clear();
@@ -195,17 +167,17 @@ void Randpool::clear() throw()
    entropy = 0;
    }
 
-/*************************************************
-* Return the name of this type                   *
-*************************************************/
+/**
+* Return the name of this type
+*/
 std::string Randpool::name() const
    {
    return "Randpool(" + cipher->name() + "," + mac->name() + ")";
    }
 
-/*************************************************
-* Randpool Constructor                           *
-*************************************************/
+/**
+* Randpool Constructor
+*/
 Randpool::Randpool(BlockCipher* cipher_in,
                    MessageAuthenticationCode* mac_in,
                    u32bit pool_blocks,
@@ -234,9 +206,9 @@ Randpool::Randpool(BlockCipher* cipher_in,
    entropy = 0;
    }
 
-/*************************************************
-* Randpool Destructor                            *
-*************************************************/
+/**
+* Randpool Destructor
+*/
 Randpool::~Randpool()
    {
    delete cipher;
diff --git a/src/rng/randpool/randpool.h b/src/rng/randpool/randpool.h
index f6bae9d52..46683934e 100644
--- a/src/rng/randpool/randpool.h
+++ b/src/rng/randpool/randpool.h
@@ -1,7 +1,7 @@
-/*************************************************
-* Randpool Header File                           *
-* (C) 1999-2008 Jack Lloyd                       *
-*************************************************/
+/*
+* Randpool Header File
+* (C) 1999-2008 Jack Lloyd
+*/
 
 #ifndef BOTAN_RANDPOOL_H__
 #define BOTAN_RANDPOOL_H__
@@ -13,9 +13,9 @@
 
 namespace Botan {
 
-/*************************************************
-* Randpool                                       *
-*************************************************/
+/**
+* Randpool
+*/
 class BOTAN_DLL Randpool : public RandomNumberGenerator
    {
    public:
@@ -24,11 +24,11 @@ class BOTAN_DLL Randpool : public RandomNumberGenerator
       void clear() throw();
       std::string name() const;
 
-      void reseed();
-      void add_entropy_source(EntropySource*);
-      void add_entropy(const byte[], u32bit);
+      void reseed(u32bit bits_to_collect);
+      void add_entropy_source(EntropySource* es);
+      void add_entropy(const byte input[], u32bit length);
 
-      Randpool(BlockCipher*, MessageAuthenticationCode*,
+      Randpool(BlockCipher* cipher, MessageAuthenticationCode* mac,
                u32bit pool_blocks = 32,
                u32bit iterations_before_reseed = 128);