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 238