Allow for higher granularity of entropy estimates by using 'double'
[openssl.git] / crypto / rand / md_rand.c
index 5b2db35..34843d0 100644 (file)
  * [including the GNU Public Licence.]
  */
 
+#define ENTROPY_NEEDED 16  /* require 128 bits = 16 bytes of randomness */
+
+#ifndef MD_RAND_DEBUG
+# ifndef NDEBUG
+#   define NDEBUG
+# endif
+#endif
+
+#include <assert.h>
 #include <stdio.h>
-#include <sys/types.h>
 #include <time.h>
 #include <string.h>
-#include "e_os.h"
-#include "crypto.h"
+
+#include "openssl/e_os.h"
+
+#include <openssl/crypto.h>
+#include <openssl/err.h>
 
 #if !defined(USE_MD5_RAND) && !defined(USE_SHA1_RAND) && !defined(USE_MDC2_RAND) && !defined(USE_MD2_RAND)
-#ifndef NO_MD5
-#define USE_MD5_RAND
-#elif !defined(NO_SHA1)
+#if !defined(NO_SHA) && !defined(NO_SHA1)
 #define USE_SHA1_RAND
-#elif !defined(NO_MDC2)
+#elif !defined(NO_MD5)
+#define USE_MD5_RAND
+#elif !defined(NO_MDC2) && !defined(NO_DES)
 #define USE_MDC2_RAND
 #elif !defined(NO_MD2)
 #define USE_MD2_RAND
 #else
-We need a message digest of some type 
+#error No message digest algorithm available
 #endif
 #endif
 
@@ -84,7 +95,7 @@ We need a message digest of some type
  */
 
 #if defined(USE_MD5_RAND)
-#include "md5.h"
+#include <openssl/md5.h>
 #define MD_DIGEST_LENGTH       MD5_DIGEST_LENGTH
 #define MD_CTX                 MD5_CTX
 #define MD_Init(a)             MD5_Init(a)
@@ -92,7 +103,7 @@ We need a message digest of some type
 #define        MD_Final(a,b)           MD5_Final(a,b)
 #define        MD(a,b,c)               MD5(a,b,c)
 #elif defined(USE_SHA1_RAND)
-#include "sha.h"
+#include <openssl/sha.h>
 #define MD_DIGEST_LENGTH       SHA_DIGEST_LENGTH
 #define MD_CTX                 SHA_CTX
 #define MD_Init(a)             SHA1_Init(a)
@@ -100,7 +111,7 @@ We need a message digest of some type
 #define        MD_Final(a,b)           SHA1_Final(a,b)
 #define        MD(a,b,c)               SHA1(a,b,c)
 #elif defined(USE_MDC2_RAND)
-#include "mdc2.h"
+#include <openssl/mdc2.h>
 #define MD_DIGEST_LENGTH       MDC2_DIGEST_LENGTH
 #define MD_CTX                 MDC2_CTX
 #define MD_Init(a)             MDC2_Init(a)
@@ -108,7 +119,7 @@ We need a message digest of some type
 #define        MD_Final(a,b)           MDC2_Final(a,b)
 #define        MD(a,b,c)               MDC2(a,b,c)
 #elif defined(USE_MD2_RAND)
-#include "md2.h"
+#include <openssl/md2.h>
 #define MD_DIGEST_LENGTH       MD2_DIGEST_LENGTH
 #define MD_CTX                 MD2_CTX
 #define MD_Init(a)             MD2_Init(a)
@@ -117,7 +128,7 @@ We need a message digest of some type
 #define        MD(a,b,c)               MD2(a,b,c)
 #endif
 
-#include "rand.h"
+#include <openssl/rand.h>
 
 /* #define NORAND      1 */
 /* #define PREDICT     1 */
@@ -127,17 +138,22 @@ static int state_num=0,state_index=0;
 static unsigned char state[STATE_SIZE+MD_DIGEST_LENGTH];
 static unsigned char md[MD_DIGEST_LENGTH];
 static long md_count[2]={0,0};
+static double entropy=0;
 
 const char *RAND_version="RAND" OPENSSL_VERSION_PTEXT;
 
 static void ssleay_rand_cleanup(void);
 static void ssleay_rand_seed(const void *buf, int num);
-static void ssleay_rand_bytes(unsigned char *buf, int num);
+static void ssleay_rand_add(const void *buf, int num, double add_entropy);
+static int ssleay_rand_bytes(unsigned char *buf, int num);
+static int ssleay_rand_pseudo_bytes(unsigned char *buf, int num);
 
 RAND_METHOD rand_ssleay_meth={
        ssleay_rand_seed,
        ssleay_rand_bytes,
        ssleay_rand_cleanup,
+       ssleay_rand_add,
+       ssleay_rand_pseudo_bytes,
        }; 
 
 RAND_METHOD *RAND_SSLeay(void)
@@ -153,22 +169,49 @@ static void ssleay_rand_cleanup(void)
        memset(md,0,MD_DIGEST_LENGTH);
        md_count[0]=0;
        md_count[1]=0;
+       entropy=0;
        }
 
-static void ssleay_rand_seed(const void *buf, int num)
+static void ssleay_rand_add(const void *buf, int num, double add)
        {
-       int i,j,k,st_idx,st_num;
+       int i,j,k,st_idx;
+       long md_c[2];
+       unsigned char local_md[MD_DIGEST_LENGTH];
        MD_CTX m;
 
 #ifdef NORAND
        return;
 #endif
 
+       /*
+        * (Based on the rand(3) manpage)
+        *
+        * The input is chopped up into units of 20 bytes (or less for
+        * the last block).  Each of these blocks is run through the hash
+        * function as follows:  The data passed to the hash function
+        * is the current 'md', the same number of bytes from the 'state'
+        * (the location determined by in incremented looping index) as
+        * the current 'block', the new key data 'block', and 'count'
+        * (which is incremented after each use).
+        * The result of this is kept in 'md' and also xored into the
+        * 'state' at the same locations that were used as input into the
+         * hash function.
+        */
+
        CRYPTO_w_lock(CRYPTO_LOCK_RAND);
        st_idx=state_index;
-       st_num=state_num;
 
-       state_index=(state_index+num);
+       /* use our own copies of the counters so that even
+        * if a concurrent thread seeds with exactly the
+        * same data and uses the same subarray there's _some_
+        * difference */
+       md_c[0] = md_count[0];
+       md_c[1] = md_count[1];
+
+       memcpy(local_md, md, sizeof md);
+
+       /* state_index <= state_num <= STATE_SIZE */
+       state_index += num;
        if (state_index >= STATE_SIZE)
                {
                state_index%=STATE_SIZE;
@@ -179,6 +222,14 @@ static void ssleay_rand_seed(const void *buf, int num)
                if (state_index > state_num)
                        state_num=state_index;
                }
+       /* state_index <= state_num <= STATE_SIZE */
+
+       /* state[st_idx], ..., state[(st_idx + num - 1) % STATE_SIZE]
+        * are what we will use now, but other threads may use them
+        * as well */
+
+       md_count[1] += (num / MD_DIGEST_LENGTH) + (num % MD_DIGEST_LENGTH > 0);
+
        CRYPTO_w_unlock(CRYPTO_LOCK_RAND);
 
        for (i=0; i<num; i+=MD_DIGEST_LENGTH)
@@ -187,7 +238,7 @@ static void ssleay_rand_seed(const void *buf, int num)
                j=(j > MD_DIGEST_LENGTH)?MD_DIGEST_LENGTH:j;
 
                MD_Init(&m);
-               MD_Update(&m,md,MD_DIGEST_LENGTH);
+               MD_Update(&m,local_md,MD_DIGEST_LENGTH);
                k=(st_idx+j)-STATE_SIZE;
                if (k > 0)
                        {
@@ -198,31 +249,64 @@ static void ssleay_rand_seed(const void *buf, int num)
                        MD_Update(&m,&(state[st_idx]),j);
                        
                MD_Update(&m,buf,j);
-               MD_Update(&m,(unsigned char *)&(md_count[0]),sizeof(md_count));
-               MD_Final(md,&m);
-               md_count[1]++;
+               MD_Update(&m,(unsigned char *)&(md_c[0]),sizeof(md_c));
+               MD_Final(local_md,&m);
+               md_c[1]++;
 
                buf=(const char *)buf + j;
 
                for (k=0; k<j; k++)
                        {
-                       state[st_idx++]^=md[k];
+                       /* Parallel threads may interfere with this,
+                        * but always each byte of the new state is
+                        * the XOR of some previous value of its
+                        * and local_md (itermediate values may be lost).
+                        * Alway using locking could hurt performance more
+                        * than necessary given that conflicts occur only
+                        * when the total seeding is longer than the random
+                        * state. */
+                       state[st_idx++]^=local_md[k];
                        if (st_idx >= STATE_SIZE)
-                               {
                                st_idx=0;
-                               st_num=STATE_SIZE;
-                               }
                        }
                }
        memset((char *)&m,0,sizeof(m));
+
+       CRYPTO_w_lock(CRYPTO_LOCK_RAND);
+       /* Don't just copy back local_md into md -- this could mean that
+        * other thread's seeding remains without effect (except for
+        * the incremented counter).  By XORing it we keep at least as
+        * much entropy as fits into md. */
+       for (k = 0; k < sizeof md; k++)
+               {
+               md[k] ^= local_md[k];
+               }
+       CRYPTO_w_unlock(CRYPTO_LOCK_RAND);
+       
+#ifndef THREADS        
+       assert(md_c[1] == md_count[1]);
+#endif
+       if (entropy < ENTROPY_NEEDED) /* stop counting when we have enough */
+           entropy += add;
        }
 
-static void ssleay_rand_bytes(unsigned char *buf, int num)
+static void ssleay_rand_seed(const void *buf, int num)
+       {
+       ssleay_rand_add(buf, num, num);
+       }
+
+static int ssleay_rand_bytes(unsigned char *buf, int num)
        {
        int i,j,k,st_num,st_idx;
+       int ok;
+       long md_c[2];
+       unsigned char local_md[MD_DIGEST_LENGTH];
        MD_CTX m;
        static int init=1;
        unsigned long l;
+#ifndef GETPID_IS_MEANINGLESS
+       pid_t curr_pid = getpid();
+#endif
 #ifdef DEVRANDOM
        FILE *fh;
 #endif
@@ -233,10 +317,29 @@ static void ssleay_rand_bytes(unsigned char *buf, int num)
 
        for (i=0; i<num; i++)
                buf[i]=val++;
-       return;
+       return(1);
        }
 #endif
 
+       /*
+        * (Based on the rand(3) manpage:)
+        *
+        * For each group of 10 bytes (or less), we do the following:
+        *
+        * Input into the hash function the top 10 bytes from the
+        * local 'md' (which is initialized from the global 'md'
+        * before any bytes are generated), the bytes that are
+        * to be overwritten by the random bytes, and bytes from the
+        * 'state' (incrementing looping index).  From this digest output
+        * (which is kept in 'md'), the top (up to) 10 bytes are
+        * returned to the caller and the bottom (up to) 10 bytes are xored
+        * into the 'state'.
+        * Finally, after we have finished 'num' random bytes for the
+        * caller, 'count' (which is incremented) and the local and global 'md'
+        * are fed into the hash function and the results are kept in the
+        * global 'md'.
+        */
+
        CRYPTO_w_lock(CRYPTO_LOCK_RAND);
 
        if (init)
@@ -244,17 +347,17 @@ static void ssleay_rand_bytes(unsigned char *buf, int num)
                CRYPTO_w_unlock(CRYPTO_LOCK_RAND);
                /* put in some default random data, we need more than
                 * just this */
-               RAND_seed(&m,sizeof(m));
-#ifndef MSDOS
-               l=getpid();
-               RAND_seed(&l,sizeof(l));
+               RAND_add(&m,sizeof(m),0);
+#ifndef GETPID_IS_MEANINGLESS
+               l=curr_pid;
+               RAND_add(&l,sizeof(l),0);
                l=getuid();
-               RAND_seed(&l,sizeof(l));
+               RAND_add(&l,sizeof(l),0);
 #endif
                l=time(NULL);
-               RAND_seed(&l,sizeof(l));
+               RAND_add(&l,sizeof(l),0);
 
-/* #ifdef DEVRANDOM */
+#ifdef DEVRANDOM
                /* 
                 * Use a random entropy pool device.
                 * Linux 1.3.x and FreeBSD-Current has 
@@ -264,17 +367,15 @@ static void ssleay_rand_bytes(unsigned char *buf, int num)
                 */
                if ((fh = fopen(DEVRANDOM, "r")) != NULL)
                        {
-                       unsigned char tmpbuf[32];
+                       unsigned char tmpbuf[ENTROPY_NEEDED];
+                       int n;
 
-                       fread((unsigned char *)tmpbuf,1,32,fh);
-                       /* we don't care how many bytes we read,
-                        * we will just copy the 'stack' if there is
-                        * nothing else :-) */
+                       n=fread((unsigned char *)tmpbuf,1,ENTROPY_NEEDED,fh);
                        fclose(fh);
-                       RAND_seed(tmpbuf,32);
-                       memset(tmpbuf,0,32);
+                       RAND_add(tmpbuf,sizeof tmpbuf,n);
+                       memset(tmpbuf,0,n);
                        }
-/* #endif */
+#endif
 #ifdef PURIFY
                memset(state,0,STATE_SIZE);
                memset(md,0,MD_DIGEST_LENGTH);
@@ -283,12 +384,22 @@ static void ssleay_rand_bytes(unsigned char *buf, int num)
                init=0;
                }
 
+       ok = (entropy >= ENTROPY_NEEDED);
+
        st_idx=state_index;
        st_num=state_num;
+       md_c[0] = md_count[0];
+       md_c[1] = md_count[1];
+       memcpy(local_md, md, sizeof md);
+
        state_index+=num;
        if (state_index > state_num)
-               state_index=(state_index%state_num);
+               state_index %= state_num;
+
+       /* state[st_idx], ..., state[(st_idx + num - 1) % st_num]
+        * are now ours (but other threads may use them too) */
 
+       md_count[0] += 1;
        CRYPTO_w_unlock(CRYPTO_LOCK_RAND);
 
        while (num > 0)
@@ -296,8 +407,15 @@ static void ssleay_rand_bytes(unsigned char *buf, int num)
                j=(num >= MD_DIGEST_LENGTH/2)?MD_DIGEST_LENGTH/2:num;
                num-=j;
                MD_Init(&m);
-               MD_Update(&m,&(md[MD_DIGEST_LENGTH/2]),MD_DIGEST_LENGTH/2);
-               MD_Update(&m,(unsigned char *)&(md_count[0]),sizeof(md_count));
+#ifndef GETPID_IS_MEANINGLESS
+               if (curr_pid) /* just in the first iteration to save time */
+                       {
+                       MD_Update(&m,(unsigned char*)&curr_pid,sizeof curr_pid);
+                       curr_pid = 0;
+                       }
+#endif
+               MD_Update(&m,&(local_md[MD_DIGEST_LENGTH/2]),MD_DIGEST_LENGTH/2);
+               MD_Update(&m,(unsigned char *)&(md_c[0]),sizeof(md_c));
 #ifndef PURIFY
                MD_Update(&m,buf,j); /* purify complains */
 #endif
@@ -309,28 +427,55 @@ static void ssleay_rand_bytes(unsigned char *buf, int num)
                        }
                else
                        MD_Update(&m,&(state[st_idx]),j);
-               MD_Final(md,&m);
+               MD_Final(local_md,&m);
 
                for (i=0; i<j; i++)
                        {
+                       state[st_idx++]^=local_md[i]; /* may compete with other threads */
+                       *(buf++)=local_md[i+MD_DIGEST_LENGTH/2];
                        if (st_idx >= st_num)
                                st_idx=0;
-                       state[st_idx++]^=md[i];
-                       *(buf++)=md[i+MD_DIGEST_LENGTH/2];
                        }
                }
 
        MD_Init(&m);
-       MD_Update(&m,(unsigned char *)&(md_count[0]),sizeof(md_count));
-       md_count[0]++;
+       MD_Update(&m,(unsigned char *)&(md_c[0]),sizeof(md_c));
+       MD_Update(&m,local_md,MD_DIGEST_LENGTH);
+       CRYPTO_w_lock(CRYPTO_LOCK_RAND);
        MD_Update(&m,md,MD_DIGEST_LENGTH);
        MD_Final(md,&m);
+       CRYPTO_w_unlock(CRYPTO_LOCK_RAND);
+
        memset(&m,0,sizeof(m));
+       if (ok)
+               return(1);
+       else
+               {
+               RANDerr(RAND_F_SSLEAY_RAND_BYTES,RAND_R_PRNG_NOT_SEEDED);
+               return(0);
+               }
+       }
+
+/* pseudo-random bytes that are guaranteed to be unique but not
+   unpredictable */
+static int ssleay_rand_pseudo_bytes(unsigned char *buf, int num) 
+       {
+       int ret, err;
+
+       ret = RAND_bytes(buf, num);
+       if (ret == 0)
+               {
+               err = ERR_peek_error();
+               if (ERR_GET_LIB(err) == ERR_LIB_RAND &&
+                   ERR_GET_REASON(err) == RAND_R_PRNG_NOT_SEEDED)
+                       (void)ERR_get_error();
+               }
+       return (ret);
        }
 
 #ifdef WINDOWS
 #include <windows.h>
-#include <rand.h>
+#include <openssl/rand.h>
 
 /*****************************************************************************
  * Initialisation function for the SSL random generator.  Takes the contents
@@ -352,12 +497,12 @@ static void ssleay_rand_bytes(unsigned char *buf, int num)
  */
 /*
  * I have modified the loading of bytes via RAND_seed() mechanism since
- * the origional would have been very very CPU intensive since RAND_seed()
+ * the original would have been very very CPU intensive since RAND_seed()
  * does an MD5 per 16 bytes of input.  The cost to digest 16 bytes is the same
  * as that to digest 56 bytes.  So under the old system, a screen of
- * 1024*768*256 would have been CPU cost of approximatly 49,000 56 byte MD5
+ * 1024*768*256 would have been CPU cost of approximately 49,000 56 byte MD5
  * digests or digesting 2.7 mbytes.  What I have put in place would
- * be 48 16k MD5 digests, or efectivly 48*16+48 MD5 bytes or 816 kbytes
+ * be 48 16k MD5 digests, or effectively 48*16+48 MD5 bytes or 816 kbytes
  * or about 3.5 times as much.
  * - eric 
  */