Drop use of entropy estimation in Randpool for the same reason as HMAC_RNG.

As with HMAC_RNG, instead assume one bit of conditional entropy per byte
of polled material. Since they are no longer used, drop the entropy
estimation routines entirely.

6 files changed, 21 insertions, 147 deletions

diff --git a/doc/log.txt b/doc/log.txt
index 09c24ba10..a62993abe 100644
--- a/doc/log.txt
+++ b/doc/log.txt
@@ -1,5 +1,6 @@
 
 * 1.7.21, ????-??-??
+ - Drop use of entropy estimation in the PRNGs
  - Make algorithm lookup much more configuable
  - Add a function for runtime performance testing
  - Increase intervals between HMAC_RNG automatic reseeding
diff --git a/src/rng/hmac_rng/hmac_rng.cpp b/src/rng/hmac_rng/hmac_rng.cpp
index d85cebada..95b119b9d 100644
--- a/src/rng/hmac_rng/hmac_rng.cpp
+++ b/src/rng/hmac_rng/hmac_rng.cpp
@@ -4,7 +4,6 @@
 *************************************************/
 
 #include <botan/hmac_rng.h>
-#include <botan/entropy.h>
 #include <botan/loadstor.h>
 #include <botan/xor_buf.h>
 #include <botan/util.h>
diff --git a/src/rng/randpool/randpool.cpp b/src/rng/randpool/randpool.cpp
index 743123b9e..0017c476c 100644
--- a/src/rng/randpool/randpool.cpp
+++ b/src/rng/randpool/randpool.cpp
@@ -4,7 +4,6 @@
 *************************************************/
 
 #include <botan/randpool.h>
-#include <botan/entropy.h>
 #include <botan/loadstor.h>
 #include <botan/xor_buf.h>
 #include <botan/util.h>
@@ -109,7 +108,19 @@ void Randpool::reseed()
    {
    SecureVector<byte> buffer(128);
 
-   Entropy_Estimator estimate;
+   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)
@@ -117,24 +128,18 @@ void Randpool::reseed()
       u32bit got = entropy_sources[j]->fast_poll(buffer, buffer.size());
 
       mac->update(buffer, got);
-      estimate.update(buffer, got, 96);
+      entropy_est += got;
       }
 
-   /* Limit assumed entropy from fast polls (to ensure we do at
-   least a few slow polls)
-   */
-   estimate.set_upper_bound(256);
-
    // 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;
 
-      estimate.update(buffer, got, 256);
-
-      if(estimate.value() > 384)
+      if(entropy_est > 512)
          break;
       }
 
@@ -143,7 +148,7 @@ void Randpool::reseed()
    xor_buf(pool, mac_val, mac_val.size());
    mix_pool();
 
-   entropy += estimate.value();
+   entropy = std::min<u32bit>(entropy + entropy_est, 8 * mac_val.size());
    }
 
 /*************************************************
@@ -155,9 +160,8 @@ void Randpool::add_entropy(const byte input[], u32bit length)
    xor_buf(pool, mac_val, mac_val.size());
    mix_pool();
 
-   Entropy_Estimator estimate;
-   estimate.update(input, length);
-   entropy += estimate.value();
+   // Assume 1 bit conditional entropy per byte of input
+   entropy = std::min<u32bit>(entropy + length, 8 * mac_val.size());
    }
 
 /*************************************************
@@ -173,7 +177,7 @@ void Randpool::add_entropy_source(EntropySource* src)
 *************************************************/
 bool Randpool::is_seeded() const
    {
-   return (entropy >= 384);
+   return (entropy >= 7 * mac->OUTPUT_LENGTH);
    }
 
 /*************************************************
diff --git a/src/utils/entropy.cpp b/src/utils/entropy.cpp
deleted file mode 100644
index 1562eb0d2..000000000
--- a/src/utils/entropy.cpp
+++ /dev/null
@@ -1,80 +0,0 @@
-/*************************************************
-* Entropy_Estimator Source File                  *
-* (C) 2008 Jack Lloyd                            *
-*************************************************/
-
-#include <botan/entropy.h>
-#include <botan/bit_ops.h>
-
-namespace Botan {
-
-/**
-Update the estimate
-*/
-void Entropy_Estimator::update(const byte buffer[], u32bit length,
-                               u32bit upper_limit)
-   {
-   u32bit this_buf_estimate = 0;
-
-   /*
-   This is pretty naive
-   */
-   for(u32bit j = 0; j != length; ++j)
-      {
-      byte delta = last ^ buffer[j];
-      last = buffer[j];
-
-      byte delta2 = delta ^ last_delta;
-      last_delta = delta;
-
-      byte delta3 = delta2 ^ last_delta2;
-      last_delta2 = delta2;
-
-      byte min_delta = delta;
-      if(min_delta > delta2) min_delta = delta2;
-      if(min_delta > delta3) min_delta = delta3;
-
-      this_buf_estimate += hamming_weight(min_delta);
-      }
-
-   this_buf_estimate /= 2;
-
-   if(upper_limit)
-      estimate += std::min(upper_limit, this_buf_estimate);
-   else
-      estimate += this_buf_estimate;
-   }
-
-/*************************************************
-* Estimate the entropy of the buffer             *
-*************************************************/
-u32bit entropy_estimate(const byte buffer[], u32bit length)
-   {
-   if(length <= 4)
-      return 0;
-
-   u32bit estimate = 0;
-   byte last = 0, last_delta = 0, last_delta2 = 0;
-
-   for(u32bit j = 0; j != length; ++j)
-      {
-      byte delta = last ^ buffer[j];
-      last = buffer[j];
-
-      byte delta2 = delta ^ last_delta;
-      last_delta = delta;
-
-      byte delta3 = delta2 ^ last_delta2;
-      last_delta2 = delta2;
-
-      byte min_delta = delta;
-      if(min_delta > delta2) min_delta = delta2;
-      if(min_delta > delta3) min_delta = delta3;
-
-      estimate += hamming_weight(min_delta);
-      }
-
-   return (estimate / 2);
-   }
-
-}
diff --git a/src/utils/entropy.h b/src/utils/entropy.h
deleted file mode 100644
index 24d2fbdbf..000000000
--- a/src/utils/entropy.h
+++ /dev/null
@@ -1,48 +0,0 @@
-/*************************************************
-* Entropy_Estimator Header File                  *
-* (C) 2008 Jack Lloyd                            *
-*************************************************/
-
-#ifndef BOTAN_ENTROPY_ESTIMATOR_H__
-#define BOTAN_ENTROPY_ESTIMATOR_H__
-
-#include <botan/types.h>
-#include <algorithm>
-
-namespace Botan {
-
-/**
-Naive Entropy Estimation using first, second, and third order deltas
-
-@todo It would be nice to extend this to test using zlib or bzip2 if
-those modules are compiled in to the library
-*/
-class BOTAN_DLL Entropy_Estimator
-   {
-   public:
-      Entropy_Estimator()
-         { last = last_delta = last_delta2 = 0; estimate = 0; }
-
-      /**
-      Return the current estimate
-      */
-      u32bit value() const { return estimate; }
-
-      /**
-      Set an upper bound on the estimate so far
-      */
-      void set_upper_bound(u32bit upper_limit)
-         { estimate = std::min(estimate, upper_limit); }
-
-      /**
-      Add more entropy data to the current estimation
-      */
-      void update(const byte buffer[], u32bit length, u32bit upper_limit = 0);
-   private:
-      u32bit estimate;
-      byte last, last_delta, last_delta2;
-   };
-
-}
-
-#endif
diff --git a/src/utils/info.txt b/src/utils/info.txt
index 99d589d8c..ffc19c852 100644
--- a/src/utils/info.txt
+++ b/src/utils/info.txt
@@ -22,8 +22,6 @@ data_src.cpp
 data_src.h
 datastor.cpp
 datastor.h
-entropy.cpp
-entropy.h
 exceptn.cpp
 exceptn.h
 loadstor.h