drivers/random/random.c

   1 /*
   2 random.c
   3
   4 Random number generator.
   5
   6 The random number generator collects data from the kernel and compressed
   7 that data into a seed for a psuedo random number generator.
   8 */
   9
  10 #include <minix/drivers.h>
  11 #include "kernel/const.h"
  12 #include "assert.h"
  13
  14 #include "random.h"
  15 #ifdef __NBSD_LIBC
  16 #include <sys/sha2.h>
  17 #else
  18 #include <minix/sha2.h>
  19 #endif
  20 #include "aes/rijndael.h"
  21
  22 #define N_DERIV 16
  23 #define NR_POOLS 32
  24 #define MIN_SAMPLES     256     /* Number of samples needed in pool 0 for a
  25                                  * re-seed.
  26                                  */
  27
  28 static unsigned long deriv[TOTAL_SOURCES][N_DERIV];
  29 static int pool_ind[TOTAL_SOURCES];
  30 static SHA256_CTX pool_ctx[NR_POOLS];
  31 static unsigned samples= 0;
  32 static int got_seeded= 0;
  33 static u8_t random_key[2*AES_BLOCKSIZE];
  34 static u32_t count_lo, count_hi;
  35 static u32_t reseed_count;
  36
  37 static void add_sample(int source, unsigned long sample);
  38 static void data_block(rd_keyinstance *keyp, void *data);
  39 static void reseed(void);
  40
  41 void random_init()
  42 {
  43         int i, j;
  44
  45         assert(&deriv[TOTAL_SOURCES-1][N_DERIV-1] ==
  46                 &deriv[0][0] + TOTAL_SOURCES*N_DERIV -1);
  47
  48         for (i= 0; i<TOTAL_SOURCES; i++)
  49         {
  50                 for (j= 0; j<N_DERIV; j++)
  51                         deriv[i][j]= 0;
  52                 pool_ind[i]= 0;
  53         }
  54         for (i= 0; i<NR_POOLS; i++)
  55                 SHA256_Init(&pool_ctx[i]);
  56         count_lo= 0;
  57         count_hi= 0;
  58         reseed_count= 0;
  59 }
  60
  61 int random_isseeded()
  62 {
  63         if (got_seeded)
  64                 return 1;
  65         return 0;
  66 }
  67
  68 void random_update(source, buf, count)
  69 int source;
  70 rand_t *buf;
  71 int count;
  72 {
  73         int i;
  74
  75 #if 0
  76         printf("random_update: got %d samples for source %d\n", count, source);
  77 #endif
  78         if (source < 0 || source >= TOTAL_SOURCES)
  79                 panic("random_update: bad source: %d", source);
  80         for (i= 0; i<count; i++)
  81                 add_sample(source, buf[i]);
  82         reseed();
  83 }
  84
  85 void random_getbytes(buf, size)
  86 void *buf;
  87 size_t size;
  88 {
  89         int n, r;
  90         u8_t *cp;
  91         rd_keyinstance key;
  92         u8_t output[AES_BLOCKSIZE];
  93
  94         r= rijndael_makekey(&key, sizeof(random_key), random_key);
  95         assert(r == 0);
  96
  97         cp= buf;
  98         while (size > 0)
  99         {
 100                 n= AES_BLOCKSIZE;
 101                 if (n > size)
 102                 {
 103                         n= size;
 104                         data_block(&key, output);
 105                         memcpy(cp, output, n);
 106                 }
 107                 else
 108                         data_block(&key, cp);
 109                 cp += n;
 110                 size -= n;
 111         }
 112
 113         /* Generate new key */
 114         assert(sizeof(random_key) == 2*AES_BLOCKSIZE);
 115         data_block(&key, random_key);
 116         data_block(&key, random_key+AES_BLOCKSIZE);
 117 }
 118
 119 void random_putbytes(buf, size)
 120 void *buf;
 121 size_t size;
 122 {
 123         /* Add bits to pool zero */
 124         SHA256_Update(&pool_ctx[0], buf, size);
 125
 126         /* Assume that these bits are truely random. Increment samples
 127          * with the number of bits.
 128          */
 129         samples += size*8;
 130
 131         reseed();
 132 }
 133
 134 static void add_sample(source, sample)
 135 int source;
 136 unsigned long sample;
 137 {
 138         int i, pool_nr;
 139         unsigned long d, v, di, min;
 140
 141         /* Delete bad sample. Compute the Nth derivative. Delete the sample
 142          * if any derivative is too small.
 143          */
 144         min= (unsigned long)-1;
 145         v= sample;
 146         for (i= 0; i<N_DERIV; i++)
 147         {
 148                 di= deriv[source][i];
 149
 150                 /* Compute the difference */
 151                 if (v >= di)
 152                         d= v-di;
 153                 else
 154                         d= di-v;
 155                 deriv[source][i]= v;
 156                 v= d;
 157                 if (v <min)
 158                         min= v;
 159         }
 160         if (min < 2)
 161         {
 162 #if 0
 163                 printf("ignoring sample '%u' from source %d\n",
 164                         sample, source);
 165 #endif
 166                 return;
 167         }
 168 #if 0
 169         printf("accepting sample '%u' from source %d\n", sample, source);
 170 #endif
 171
 172         pool_nr= pool_ind[source];
 173         assert(pool_nr >= 0 && pool_nr < NR_POOLS);
 174
 175         SHA256_Update(&pool_ctx[pool_nr], (unsigned char *)&sample,
 176                 sizeof(sample));
 177         if (pool_nr == 0)
 178                 samples++;
 179         pool_nr++;
 180         if (pool_nr >= NR_POOLS)
 181                 pool_nr= 0;
 182         pool_ind[source]= pool_nr;
 183 }
 184
 185 static void data_block(keyp, data)
 186 rd_keyinstance *keyp;
 187 void *data;
 188 {
 189         int r;
 190         u8_t input[AES_BLOCKSIZE];
 191
 192         memset(input, '\0', sizeof(input));
 193
 194         /* Do we want the output of the random numbers to be portable
 195          * across platforms (for example for RSA signatures)? At the moment
 196          * we don't do anything special. Encrypt the counter with the AES
 197          * key.
 198          */
 199         assert(sizeof(count_lo)+sizeof(count_hi) <= AES_BLOCKSIZE);
 200         memcpy(input, &count_lo, sizeof(count_lo));
 201         memcpy(input+sizeof(count_lo), &count_hi, sizeof(count_hi));
 202         r= rijndael_ecb_encrypt(keyp, input, data, AES_BLOCKSIZE, NULL);
 203         assert(r == AES_BLOCKSIZE);
 204
 205         count_lo++;
 206         if (count_lo == 0)
 207                 count_hi++;
 208 }
 209
 210 static void reseed()
 211 {
 212         int i;
 213         SHA256_CTX ctx;
 214         u8_t digest[SHA256_DIGEST_LENGTH];
 215
 216         if (samples < MIN_SAMPLES)
 217                 return;
 218
 219         reseed_count++;
 220         SHA256_Init(&ctx);
 221         if (got_seeded)
 222                 SHA256_Update(&ctx, random_key, sizeof(random_key));
 223         SHA256_Final(digest, &pool_ctx[0]);
 224         SHA256_Update(&ctx, digest, sizeof(digest));
 225         SHA256_Init(&pool_ctx[0]);
 226         for (i= 1; i<NR_POOLS; i++)
 227         {
 228                 if ((reseed_count & (1UL << (i-1))) != 0)
 229                         break;
 230                 SHA256_Final(digest, &pool_ctx[i]);
 231                 SHA256_Update(&ctx, digest, sizeof(digest));
 232                 SHA256_Init(&pool_ctx[i]);
 233         }
 234         SHA256_Final(digest, &ctx);
 235         assert(sizeof(random_key) == sizeof(digest));
 236         memcpy(random_key, &digest, sizeof(random_key));
 237         samples= 0;
 238
 239         got_seeded= 1;
 240 }
 241