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