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
random_init()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
random_isseeded()57 int random_isseeded()
58 {
59 if (got_seeded)
60 return 1;
61 return 0;
62 }
63
random_update(source,buf,count)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
random_getbytes(buf,size)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
random_putbytes(buf,size)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
add_sample(source,sample)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
data_block(keyp,data)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
reseed()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