Change rand_pool_bytes_needed to handle less entropy than 1 per 8 bits

rand_pool_bytes_needed() was constructed in such a way that the
smallest acceptable entropy factor was 1 entropy bits per 8 bits of
data.  At the same time, we have a DRBG_MINMAX_FACTOR that allows
weaker source, as small as 1 bit of entropy per 128 bits of data.
The conclusion is that rand_pool_bytes_needed() needs to change to
support weaker entropy sources.  We therefore change the input of
entropy per byte to be an entropy factor instead.  This entropy factor
expresses how many bits of data it takes (on average) to get 1 bit of
entropy.

Reviewed-by: Matthias St. Pierre <Matthias.St.Pierre@ncp-e.com>
(Merged from https://github.com/openssl/openssl/pull/6150)

5 files changed, 28 insertions, 24 deletions

diff --git a/crypto/include/internal/rand_int.h b/crypto/include/internal/rand_int.h
index cf82e4a640..daec926c67 100644
--- a/crypto/include/internal/rand_int.h
+++ b/crypto/include/internal/rand_int.h
@@ -63,7 +63,8 @@ size_t rand_pool_length(RAND_POOL *pool);
 
 size_t rand_pool_entropy_available(RAND_POOL *pool);
 size_t rand_pool_entropy_needed(RAND_POOL *pool);
-size_t rand_pool_bytes_needed(RAND_POOL *pool, unsigned int entropy_per_byte);
+/* |entropy_factor| expresses how many bits of data contain 1 bit of entropy */
+size_t rand_pool_bytes_needed(RAND_POOL *pool, unsigned int entropy_factor);
 size_t rand_pool_bytes_remaining(RAND_POOL *pool);
 
 int rand_pool_add(RAND_POOL *pool,
diff --git a/crypto/rand/rand_lib.c b/crypto/rand/rand_lib.c
index 8a657c559d..050c9d23cc 100644
--- a/crypto/rand/rand_lib.c
+++ b/crypto/rand/rand_lib.c
@@ -87,7 +87,7 @@ size_t rand_acquire_entropy_from_cpu(RAND_POOL *pool)
     size_t bytes_needed;
     unsigned char *buffer;
 
-    bytes_needed = rand_pool_bytes_needed(pool, 8 /*entropy_per_byte*/);
+    bytes_needed = rand_pool_bytes_needed(pool, 1 /*entropy_factor*/);
     if (bytes_needed > 0) {
         buffer = rand_pool_add_begin(pool, bytes_needed);
 
@@ -158,7 +158,7 @@ size_t rand_drbg_get_entropy(RAND_DRBG *drbg,
     }
 
     if (drbg->parent) {
-        size_t bytes_needed = rand_pool_bytes_needed(pool, 8);
+        size_t bytes_needed = rand_pool_bytes_needed(pool, 1 /*entropy_factor*/);
         unsigned char *buffer = rand_pool_add_begin(pool, bytes_needed);
 
         if (buffer != NULL) {
@@ -488,11 +488,11 @@ unsigned char *rand_pool_detach(RAND_POOL *pool)
 
 
 /*
- * If every byte of the input contains |entropy_per_bytes| bits of entropy,
- * how many bytes does one need to obtain at least |bits| bits of entropy?
+ * If |entropy_factor| bits contain 1 bit of entropy, how many bytes does one
+ * need to obtain at least |bits| bits of entropy?
  */
-#define ENTROPY_TO_BYTES(bits, entropy_per_bytes) \
-    (((bits) + ((entropy_per_bytes) - 1))/(entropy_per_bytes))
+#define ENTROPY_TO_BYTES(bits, entropy_factor) \
+    (((bits) * (entropy_factor) + 7) / 8)
 
 
 /*
@@ -529,21 +529,21 @@ size_t rand_pool_entropy_needed(RAND_POOL *pool)
 
 /*
  * Returns the number of bytes needed to fill the pool, assuming
- * the input has 'entropy_per_byte' entropy bits per byte.
+ * the input has 1 / |entropy_factor| entropy bits per data bit.
  * In case of an error, 0 is returned.
  */
 
-size_t rand_pool_bytes_needed(RAND_POOL *pool, unsigned int entropy_per_byte)
+size_t rand_pool_bytes_needed(RAND_POOL *pool, unsigned int entropy_factor)
 {
     size_t bytes_needed;
     size_t entropy_needed = rand_pool_entropy_needed(pool);
 
-    if (entropy_per_byte < 1 || entropy_per_byte > 8) {
+    if (entropy_factor < 1) {
         RANDerr(RAND_F_RAND_POOL_BYTES_NEEDED, RAND_R_ARGUMENT_OUT_OF_RANGE);
         return 0;
     }
 
-    bytes_needed = ENTROPY_TO_BYTES(entropy_needed, entropy_per_byte);
+    bytes_needed = ENTROPY_TO_BYTES(entropy_needed, entropy_factor);
 
     if (bytes_needed > pool->max_len - pool->len) {
         /* not enough space left */
diff --git a/crypto/rand/rand_unix.c b/crypto/rand/rand_unix.c
index 9b6971c095..1f0084db4e 100644
--- a/crypto/rand/rand_unix.c
+++ b/crypto/rand/rand_unix.c
@@ -124,7 +124,7 @@ size_t rand_pool_acquire_entropy(RAND_POOL *pool)
     extern void s$sleep2(long long *_duration, short int *_code);
 #  endif
 
-    bytes_needed = rand_pool_bytes_needed(pool, 2 /*entropy_per_byte*/);
+    bytes_needed = rand_pool_bytes_needed(pool, 4 /*entropy_factor*/);
 
     for (i = 0; i < bytes_needed; i++) {
         /*
@@ -278,7 +278,7 @@ size_t rand_pool_acquire_entropy(RAND_POOL *pool)
     unsigned char *buffer;
 
 #   ifdef OPENSSL_RAND_SEED_GETRANDOM
-    bytes_needed = rand_pool_bytes_needed(pool, 8 /*entropy_per_byte*/);
+    bytes_needed = rand_pool_bytes_needed(pool, 1 /*entropy_factor*/);
     buffer = rand_pool_add_begin(pool, bytes_needed);
     if (buffer != NULL) {
         size_t bytes = 0;
@@ -300,7 +300,7 @@ size_t rand_pool_acquire_entropy(RAND_POOL *pool)
 #   endif
 
 #   ifdef OPENSSL_RAND_SEED_DEVRANDOM
-    bytes_needed = rand_pool_bytes_needed(pool, 8 /*entropy_per_byte*/);
+    bytes_needed = rand_pool_bytes_needed(pool, 1 /*entropy_factor*/);
     if (bytes_needed > 0) {
         static const char *paths[] = { DEVRANDOM, NULL };
         FILE *fp;
@@ -323,7 +323,7 @@ size_t rand_pool_acquire_entropy(RAND_POOL *pool)
             if (entropy_available > 0)
                 return entropy_available;
 
-            bytes_needed = rand_pool_bytes_needed(pool, 8 /*entropy_per_byte*/);
+            bytes_needed = rand_pool_bytes_needed(pool, 1 /*entropy_factor*/);
         }
     }
 #   endif
@@ -341,7 +341,7 @@ size_t rand_pool_acquire_entropy(RAND_POOL *pool)
 #   endif
 
 #   ifdef OPENSSL_RAND_SEED_EGD
-    bytes_needed = rand_pool_bytes_needed(pool, 8 /*entropy_per_byte*/);
+    bytes_needed = rand_pool_bytes_needed(pool, 1 /*entropy_factor*/);
     if (bytes_needed > 0) {
         static const char *paths[] = { DEVRANDOM_EGD, NULL };
         int i;
diff --git a/crypto/rand/rand_vms.c b/crypto/rand/rand_vms.c
index c50b4b2988..5561abcf73 100644
--- a/crypto/rand/rand_vms.c
+++ b/crypto/rand/rand_vms.c
@@ -58,10 +58,12 @@ static struct items_data_st {
 };
 
 /*
- * We assume there we get about 4 bits of entropy per byte from the items
- * above, with a bit of scrambling added rand_pool_acquire_entropy()
+ * This number expresses how many bits of data contain 1 bit of entropy.
+ *
+ * For the moment, we assume about 0.5 entropy bits per data bit, or 1
+ * bit of entropy per 2 data bits.
  */
-#define ENTROPY_BITS_PER_BYTE   4
+#define ENTROPY_FACTOR  2
 
 size_t rand_pool_acquire_entropy(RAND_POOL *pool)
 {
@@ -83,7 +85,7 @@ size_t rand_pool_acquire_entropy(RAND_POOL *pool)
     size_t i, j ;
     size_t tmp_length   = 0;
     size_t total_length = 0;
-    size_t bytes_needed = rand_pool_bytes_needed(pool, ENTROPY_BITS_PER_BYTE);
+    size_t bytes_needed = rand_pool_bytes_needed(pool, ENTROPY_FACTOR);
     size_t bytes_remaining = rand_pool_bytes_remaining(pool);
 
     /* Setup itemlist for GETJPI */
@@ -149,8 +151,9 @@ size_t rand_pool_acquire_entropy(RAND_POOL *pool)
     if (total_length > bytes_remaining)
         total_length = bytes_remaining;
 
+    /* We give the pessimistic value for the amount of entropy */
     rand_pool_add(pool, (PTR_T)data_buffer, total_length,
-                  total_length * ENTROPY_BITS_PER_BYTE);
+                  total_length / ENTROPY_FACTOR);
     return rand_pool_entropy_available(pool);
 }
 
diff --git a/crypto/rand/rand_win.c b/crypto/rand/rand_win.c
index 1d4420418e..f2059eb412 100644
--- a/crypto/rand/rand_win.c
+++ b/crypto/rand/rand_win.c
@@ -62,7 +62,7 @@ size_t rand_pool_acquire_entropy(RAND_POOL *pool)
 # endif
 
 # ifdef USE_BCRYPTGENRANDOM
-    bytes_needed = rand_pool_bytes_needed(pool, 8 /*entropy_per_byte*/);
+    bytes_needed = rand_pool_bytes_needed(pool, 1 /*entropy_factor*/);
     buffer = rand_pool_add_begin(pool, bytes_needed);
     if (buffer != NULL) {
         size_t bytes = 0;
@@ -76,7 +76,7 @@ size_t rand_pool_acquire_entropy(RAND_POOL *pool)
     if (entropy_available > 0)
         return entropy_available;
 # else
-    bytes_needed = rand_pool_bytes_needed(pool, 8 /*entropy_per_byte*/);
+    bytes_needed = rand_pool_bytes_needed(pool, 1 /*entropy_factor*/);
     buffer = rand_pool_add_begin(pool, bytes_needed);
     if (buffer != NULL) {
         size_t bytes = 0;
@@ -95,7 +95,7 @@ size_t rand_pool_acquire_entropy(RAND_POOL *pool)
     if (entropy_available > 0)
         return entropy_available;
 
-    bytes_needed = rand_pool_bytes_needed(pool, 8 /*entropy_per_byte*/);
+    bytes_needed = rand_pool_bytes_needed(pool, 1 /*entropy_factor*/);
     buffer = rand_pool_add_begin(pool, bytes_needed);
     if (buffer != NULL) {
         size_t bytes = 0;