Move Entropy_Estimator to utils/entropy.h (from anon namespace in HMAC_RNG

implementation), remove freestanding estimate_entropy function, change
Randpool to use entropy estimator.

8 files changed, 157 insertions, 101 deletions

diff --git a/src/rng/hmac_rng/hmac_rng.cpp b/src/rng/hmac_rng/hmac_rng.cpp
index 1a9fedb6c..769cdf4b2 100644
--- a/src/rng/hmac_rng/hmac_rng.cpp
+++ b/src/rng/hmac_rng/hmac_rng.cpp
@@ -4,6 +4,7 @@
 *************************************************/
 
 #include <botan/hmac_rng.h>
+#include <botan/entropy.h>
 #include <botan/loadstor.h>
 #include <botan/xor_buf.h>
 #include <botan/util.h>
@@ -13,58 +14,6 @@
 
 namespace Botan {
 
-namespace {
-
-class Entropy_Estimator
-   {
-   public:
-      Entropy_Estimator()
-         { last = last_delta = last_delta2 = 0; estimate = 0; }
-
-      u32bit value() const { return estimate; }
-
-      void set_upper_bound(u32bit upper_limit)
-         { estimate = std::min(estimate, upper_limit); }
-
-      void update(const byte buffer[], u32bit length, u32bit upper_limit = 0);
-   private:
-      u32bit estimate;
-      byte last, last_delta, last_delta2;
-   };
-
-void Entropy_Estimator::update(const byte buffer[], u32bit length,
-                               u32bit upper_limit)
-   {
-   u32bit this_buf_estimate = 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;
-
-      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;
-   }
-
-}
-
 /*************************************************
 * Generate a buffer of random bytes              *
 *************************************************/
@@ -227,6 +176,10 @@ void HMAC_RNG::reseed_with_input(const byte input[], u32bit input_length)
    SecureVector<byte> prk = extractor->final();
    prf->set_key(prk, prk.size());
 
+   // Total gathered entropy is at most PRK bits (likely less, really,
+   // since PRF will probably hash it down further)
+   estimate.set_upper_bound(prk.size());
+
    K.clear();
    counter = 0;
 
diff --git a/src/rng/hmac_rng/hmac_rng.h b/src/rng/hmac_rng/hmac_rng.h
index dbadb2a04..e735a7899 100644
--- a/src/rng/hmac_rng/hmac_rng.h
+++ b/src/rng/hmac_rng/hmac_rng.h
@@ -13,12 +13,14 @@
 namespace Botan {
 
 /**
-HMAC_RNG - based on the design described in"On Extract-then-Expand Key
-Derivation Functions and an HMAC-based KDF" by Hugo Krawczyk
+HMAC_RNG - based on the design described in "On Extract-then-Expand
+Key Derivation Functions and an HMAC-based KDF" by Hugo Krawczyk
 (henceforce, 'E-t-E')
 
 However it actually can be parameterized with any two MAC functions,
-not restricted to HMAC (this is also described in Krawczyk's paper)
+not restricted to HMAC (this variation is also described in Krawczyk's
+paper), for instance one could use HMAC(SHA-512) as the extractor
+and CMAC(AES-256) as the PRF.
 */
 class BOTAN_DLL HMAC_RNG : public RandomNumberGenerator
    {
@@ -32,8 +34,8 @@ class BOTAN_DLL HMAC_RNG : public RandomNumberGenerator
       void add_entropy_source(EntropySource* es);
       void add_entropy(const byte[], u32bit);
 
-      HMAC_RNG(MessageAuthenticationCode*,
-               MessageAuthenticationCode*);
+      HMAC_RNG(MessageAuthenticationCode* extractor,
+               MessageAuthenticationCode* prf);
 
       ~HMAC_RNG();
    private:
diff --git a/src/rng/randpool/randpool.cpp b/src/rng/randpool/randpool.cpp
index dd80a7f70..743123b9e 100644
--- a/src/rng/randpool/randpool.cpp
+++ b/src/rng/randpool/randpool.cpp
@@ -4,6 +4,7 @@
 *************************************************/
 
 #include <botan/randpool.h>
+#include <botan/entropy.h>
 #include <botan/loadstor.h>
 #include <botan/xor_buf.h>
 #include <botan/util.h>
@@ -108,40 +109,41 @@ void Randpool::reseed()
    {
    SecureVector<byte> buffer(128);
 
-   u32bit gathered_entropy = 0;
+   Entropy_Estimator estimate;
 
    // First do a fast poll of all sources (no matter what)
    for(u32bit j = 0; j != entropy_sources.size(); ++j)
       {
       u32bit got = entropy_sources[j]->fast_poll(buffer, buffer.size());
-      u32bit entropy = std::min<u32bit>(96, entropy_estimate(buffer, got));
 
       mac->update(buffer, got);
-
-      gathered_entropy += entropy;
+      estimate.update(buffer, got, 96);
       }
 
-   // Limit assumed entropy from fast polls to 256 bits total
-   gathered_entropy = std::min<u32bit>(256, gathered_entropy);
+   /* 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());
-      u32bit entropy = std::min<u32bit>(256, entropy_estimate(buffer, got));
 
       mac->update(buffer, got);
 
-      gathered_entropy += entropy;
-      if(gathered_entropy > 512)
+      estimate.update(buffer, got, 256);
+
+      if(estimate.value() > 384)
          break;
       }
 
    SecureVector<byte> mac_val = mac->final();
+
    xor_buf(pool, mac_val, mac_val.size());
    mix_pool();
 
-   entropy += gathered_entropy;
+   entropy += estimate.value();
    }
 
 /*************************************************
@@ -153,7 +155,9 @@ void Randpool::add_entropy(const byte input[], u32bit length)
    xor_buf(pool, mac_val, mac_val.size());
    mix_pool();
 
-   entropy += entropy_estimate(input, length);
+   Entropy_Estimator estimate;
+   estimate.update(input, length);
+   entropy += estimate.value();
    }
 
 /*************************************************
diff --git a/src/utils/entropy.cpp b/src/utils/entropy.cpp
new file mode 100644
index 000000000..1562eb0d2
--- /dev/null
+++ b/src/utils/entropy.cpp
@@ -0,0 +1,80 @@
+/*************************************************
+* 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
new file mode 100644
index 000000000..24d2fbdbf
--- /dev/null
+++ b/src/utils/entropy.h
@@ -0,0 +1,48 @@
+/*************************************************
+* 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 b20a16a56..0f0a18a35 100644
--- a/src/utils/info.txt
+++ b/src/utils/info.txt
@@ -19,6 +19,8 @@ charset.cpp
 charset.h
 datastor.cpp
 datastor.h
+entropy.h
+entropy.cpp
 loadstor.h
 mem_ops.h
 mlock.cpp
diff --git a/src/utils/util.cpp b/src/utils/util.cpp
index af1c62ebd..f8b98fcb8 100644
--- a/src/utils/util.cpp
+++ b/src/utils/util.cpp
@@ -64,36 +64,4 @@ u32bit dl_work_factor(u32bit bits)
 #endif
    }
 
-/*************************************************
-* 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/util.h b/src/utils/util.h
index 62ecb948d..d0e2e110a 100644
--- a/src/utils/util.h
+++ b/src/utils/util.h
@@ -30,7 +30,6 @@ BOTAN_DLL u32bit round_down(u32bit, u32bit);
 /*************************************************
 * Work Factor Estimates                          *
 *************************************************/
-BOTAN_DLL u32bit entropy_estimate(const byte[], u32bit);
 BOTAN_DLL u32bit dl_work_factor(u32bit);
 
 }