Get the basic random number generator functions to compile
[akaros.git] / kern / lib / random / fortuna.c
1 /*
2  * fortuna.c
3  *              Fortuna-like PRNG.
4  *
5  * Copyright (c) 2005 Marko Kreen
6  * All rights reserved.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions
10  * are met:
11  * 1. Redistributions of source code must retain the above copyright
12  *        notice, this list of conditions and the following disclaimer.
13  * 2. Redistributions in binary form must reproduce the above copyright
14  *        notice, this list of conditions and the following disclaimer in the
15  *        documentation and/or other materials provided with the distribution.
16  *
17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20  * ARE DISCLAIMED.      IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27  * SUCH DAMAGE.
28  *
29  * contrib/pgcrypto/fortuna.c
30  */
31
32 #include <arch/arch.h>
33 #include <time.h>
34
35 #include <random/fortuna.h>
36 #include <random/rijndael.h>
37 #include <random/sha2.h>
38
39
40 /*
41  * Why Fortuna-like: There does not seem to be any definitive reference
42  * on Fortuna in the net.  Instead this implementation is based on
43  * following references:
44  *
45  * http://en.wikipedia.org/wiki/Fortuna_(PRNG)
46  *       - Wikipedia article
47  * http://jlcooke.ca/random/
48  *       - Jean-Luc Cooke Fortuna-based /dev/random driver for Linux.
49  */
50
51 /*
52  * There is some confusion about whether and how to carry forward
53  * the state of the pools.      Seems like original Fortuna does not
54  * do it, resetting hash after each request.  I guess expecting
55  * feeding to happen more often that requesting.   This is absolutely
56  * unsuitable for pgcrypto, as nothing asynchronous happens here.
57  *
58  * J.L. Cooke fixed this by feeding previous hash to new re-initialized
59  * hash context.
60  *
61  * Fortuna predecessor Yarrow requires ability to query intermediate
62  * 'final result' from hash, without affecting it.
63  *
64  * This implementation uses the Yarrow method - asking intermediate
65  * results, but continuing with old state.
66  */
67
68 /*
69  * Algorithm parameters
70  */
71
72 /*
73  * How many pools.
74  *
75  * Original Fortuna uses 32 pools, that means 32'th pool is
76  * used not earlier than in 13th year.  This is a waste in
77  * pgcrypto, as we have very low-frequancy seeding.  Here
78  * is preferable to have all entropy usable in reasonable time.
79  *
80  * With 23 pools, 23th pool is used after 9 days which seems
81  * more sane.
82  *
83  * In our case the minimal cycle time would be bit longer
84  * than the system-randomness feeding frequency.
85  */
86 enum {
87         numPools = 23,
88
89         /* in microseconds */
90         reseedInterval = 100000, /* 0.1 sec */
91
92         /* for one big request, reseed after this many bytes */
93         reseedBytes = (1024 * 1024),
94
95         /*
96         * Skip reseed if pool 0 has less than this many
97         * bytes added since last reseed.
98         */
99         pool0Fill = (256 / 8),
100
101         /*
102         * Algorithm constants
103         */
104
105         /* Both cipher key size and hash result size */
106         block = 32,
107
108         /* cipher block size */
109         ciphBlock = 16
110 };
111
112 /* for internal wrappers */
113 typedef SHA256Ctx mdCtx;
114 typedef rijndaelCtx ciphCtx;
115
116 struct FState {
117         uint8_t counter[ciphBlock];
118         uint8_t result[ciphBlock];
119         uint8_t key[block];
120         mdCtx pool[numPools];
121         ciphCtx ciph;
122         unsigned reseedCount;
123         int32_t lastReseedTime;
124         unsigned pool0Bytes;
125         unsigned rndPos;
126         int tricksDone;
127 };
128 typedef struct FState FState;
129
130 /*
131  * Use our own wrappers here.
132  * - Need to get intermediate result from digest, without affecting it.
133  * - Need re-set key on a cipher context.
134  * - Algorithms are guaranteed to exist.
135  * - No memory allocations.
136  */
137
138 static void ciph_init(ciphCtx *ctx, const uint8_t *key, int klen)
139 {
140         rijndael_set_key(ctx, (const uint32_t *)key, klen, 1);
141 }
142
143 static void ciph_encrypt(ciphCtx *ctx, const uint8_t *in, uint8_t *out)
144 {
145         rijndael_encrypt(ctx, (const uint32_t *)in, (uint32_t *)out);
146 }
147
148 static void md_init(mdCtx *ctx) { SHA256_Init(ctx); }
149
150 static void md_update(mdCtx *ctx, const uint8_t *data, int len)
151 {
152         SHA256_Update(ctx, data, len);
153 }
154
155 static void md_result(mdCtx *ctx, uint8_t *dst)
156 {
157         SHA256Ctx tmp;
158
159         memmove(&tmp, ctx, sizeof(*ctx));
160         SHA256_Final(dst, &tmp);
161         memset(&tmp, 0, sizeof(tmp));
162 }
163
164 /*
165  * initialize state
166  */
167 static void init_state(FState *st)
168 {
169         int i;
170
171         memset(st, 0, sizeof(*st));
172         for (i = 0; i < numPools; i++)
173                 md_init(&st->pool[i]);
174 }
175
176 /*
177  * Endianess does not matter.
178  * It just needs to change without repeating.
179  */
180 static void inc_counter(FState *st)
181 {
182         uint32_t *val = (uint32_t *)st->counter;
183
184         if (++val[0])
185                 return;
186         if (++val[1])
187                 return;
188         if (++val[2])
189                 return;
190         ++val[3];
191 }
192
193 /*
194  * This is called 'cipher in counter mode'.
195  */
196 static void encrypt_counter(FState *st, uint8_t *dst)
197 {
198         ciph_encrypt(&st->ciph, st->counter, dst);
199         inc_counter(st);
200 }
201
202 /*
203  * The time between reseed must be at least reseedInterval
204  * microseconds.
205  */
206 static int enough_time_passed(FState *st)
207 {
208         int ok;
209         int32_t now;
210         int32_t last = st->lastReseedTime;
211
212         now = tsc2sec(read_tsc());
213
214         /* check how much time has passed */
215         ok = 0;
216         if (now - last >= reseedInterval)
217                 ok = 1;
218
219         /* reseed will happen, update lastReseedTime */
220         if (ok)
221                 st->lastReseedTime = now;
222
223         return ok;
224 }
225
226 /*
227  * generate new key from all the pools
228  */
229 static void reseed(FState *st)
230 {
231         unsigned k;
232         unsigned n;
233         mdCtx key_md;
234         uint8_t buf[block];
235
236         /* set pool as empty */
237         st->pool0Bytes = 0;
238
239         /*
240          * Both #0 and #1 reseed would use only pool 0. Just skip #0 then.
241          */
242         n = ++st->reseedCount;
243
244         /*
245          * The goal: use k-th pool only 1/(2^k) of the time.
246          */
247         md_init(&key_md);
248         for (k = 0; k < numPools; k++) {
249                 md_result(&st->pool[k], buf);
250                 md_update(&key_md, buf, block);
251
252                 if (n & 1 || !n)
253                         break;
254                 n >>= 1;
255         }
256
257         /* add old key into mix too */
258         md_update(&key_md, st->key, block);
259
260         /* now we have new key */
261         md_result(&key_md, st->key);
262
263         /* use new key */
264         ciph_init(&st->ciph, st->key, block);
265
266         memset(&key_md, 0, sizeof(key_md));
267         memset(buf, 0, block);
268 }
269
270 /*
271  * Pick a random pool.  This uses key bytes as random source.
272  */
273 static unsigned get_rand_pool(FState *st)
274 {
275         unsigned rnd;
276
277         /*
278          * This slightly prefers lower pools - thats OK.
279          */
280         rnd = st->key[st->rndPos] % numPools;
281
282         st->rndPos++;
283         if (st->rndPos >= block)
284                 st->rndPos = 0;
285
286         return rnd;
287 }
288
289 /*
290  * update pools
291  */
292 static void add_entropy(FState *st, const uint8_t *data, unsigned len)
293 {
294         unsigned pos;
295         uint8_t hash[block];
296         mdCtx md;
297
298         /* hash given data */
299         md_init(&md);
300         md_update(&md, data, len);
301         md_result(&md, hash);
302
303         /*
304          * Make sure the pool 0 is initialized, then update randomly.
305          */
306         if (st->reseedCount == 0)
307                 pos = 0;
308         else
309                 pos = get_rand_pool(st);
310         md_update(&st->pool[pos], hash, block);
311
312         if (pos == 0)
313                 st->pool0Bytes += len;
314
315         memset(hash, 0, block);
316         memset(&md, 0, sizeof(md));
317 }
318
319 /*
320  * Just take 2 next blocks as new key
321  */
322 static void rekey(FState *st)
323 {
324         encrypt_counter(st, st->key);
325         encrypt_counter(st, st->key + ciphBlock);
326         ciph_init(&st->ciph, st->key, block);
327 }
328
329 /*
330  * Hide public constants. (counter, pools > 0)
331  *
332  * This can also be viewed as spreading the startup
333  * entropy over all of the components.
334  */
335 static void startup_tricks(FState *st)
336 {
337         int i;
338         uint8_t buf[block];
339
340         /* Use next block as counter. */
341         encrypt_counter(st, st->counter);
342
343         /* Now shuffle pools, excluding #0 */
344         for (i = 1; i < numPools; i++) {
345                 encrypt_counter(st, buf);
346                 encrypt_counter(st, buf + ciphBlock);
347                 md_update(&st->pool[i], buf, block);
348         }
349         memset(buf, 0, block);
350
351         /* Hide the key. */
352         rekey(st);
353
354         /* This can be done only once. */
355         st->tricksDone = 1;
356 }
357
358 static void extract_data(FState *st, unsigned count, uint8_t *dst)
359 {
360         unsigned n;
361         unsigned block_nr = 0;
362
363         /* Should we reseed? */
364         if (st->pool0Bytes >= pool0Fill || st->reseedCount == 0)
365                 if (enough_time_passed(st))
366                         reseed(st);
367
368         /* Do some randomization on first call */
369         if (!st->tricksDone)
370                 startup_tricks(st);
371
372         while (count > 0) {
373                 /* produce bytes */
374                 encrypt_counter(st, st->result);
375
376                 /* copy result */
377                 if (count > ciphBlock)
378                         n = ciphBlock;
379                 else
380                         n = count;
381                 memmove(dst, st->result, n);
382                 dst += n;
383                 count -= n;
384
385                 /* must not give out too many bytes with one key */
386                 block_nr++;
387                 if (block_nr > (reseedBytes / ciphBlock)) {
388                         rekey(st);
389                         block_nr = 0;
390                 }
391         }
392         /* Set new key for next request. */
393         rekey(st);
394 }
395
396 static FState mainState;
397 static int initDone;
398
399 static void init()
400 {
401         init_state(&mainState);
402         initDone = 1;
403 }
404
405 /*
406  * public interface
407  */
408
409 void fortuna_add_entropy(const uint8_t *data, unsigned len)
410 {
411         if (!initDone)
412                 init();
413
414         if (!data || !len)
415                 return;
416         add_entropy(&mainState, data, len);
417 }
418
419 void fortuna_get_bytes(unsigned len, uint8_t *dst)
420 {
421         if (!initDone)
422                 init();
423
424         if (!dst || !len)
425                 return;
426         extract_data(&mainState, len, dst);
427 }