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