diff options
| -rw-r--r-- | doc/log.txt | 1 | ||||
| -rw-r--r-- | src/rng/hmac_rng/hmac_rng.cpp | 1 | ||||
| -rw-r--r-- | src/rng/randpool/randpool.cpp | 36 | ||||
| -rw-r--r-- | src/utils/entropy.cpp | 80 | ||||
| -rw-r--r-- | src/utils/entropy.h | 48 | ||||
| -rw-r--r-- | src/utils/info.txt | 2 |
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 |