1 /* $NetBSD: rand-fortuna.c,v 1.1.1.1 2011/04/13 18:14:50 elric Exp $ */
2
3 /*
4 * fortuna.c
5 * Fortuna-like PRNG.
6 *
7 * Copyright (c) 2005 Marko Kreen
8 * All rights reserved.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
23 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29 * SUCH DAMAGE.
30 *
31 * $PostgreSQL: pgsql/contrib/pgcrypto/fortuna.c,v 1.8 2006/10/04 00:29:46 momjian Exp $
32 */
33
34 #include <config.h>
35
36 #include <stdio.h>
37 #include <stdlib.h>
38 #include <rand.h>
39 #include <heim_threads.h>
40
41 #ifdef KRB5
42 #include <krb5/krb5-types.h>
43 #endif
44 #include <krb5/roken.h>
45
46 #include "randi.h"
47 #include "aes.h"
48 #include "sha.h"
49
50 /*
51 * Why Fortuna-like: There does not seem to be any definitive reference
52 * on Fortuna in the net. Instead this implementation is based on
53 * following references:
54 *
55 * http://en.wikipedia.org/wiki/Fortuna_(PRNG)
56 * - Wikipedia article
57 * http://jlcooke.ca/random/
58 * - Jean-Luc Cooke Fortuna-based /dev/random driver for Linux.
59 */
60
61 /*
62 * There is some confusion about whether and how to carry forward
63 * the state of the pools. Seems like original Fortuna does not
64 * do it, resetting hash after each request. I guess expecting
65 * feeding to happen more often that requesting. This is absolutely
66 * unsuitable for pgcrypto, as nothing asynchronous happens here.
67 *
68 * J.L. Cooke fixed this by feeding previous hash to new re-initialized
69 * hash context.
70 *
71 * Fortuna predecessor Yarrow requires ability to query intermediate
72 * 'final result' from hash, without affecting it.
73 *
74 * This implementation uses the Yarrow method - asking intermediate
75 * results, but continuing with old state.
76 */
77
78
79 /*
80 * Algorithm parameters
81 */
82
83 #define NUM_POOLS 32
84
85 /* in microseconds */
86 #define RESEED_INTERVAL 100000 /* 0.1 sec */
87
88 /* for one big request, reseed after this many bytes */
89 #define RESEED_BYTES (1024*1024)
90
91 /*
92 * Skip reseed if pool 0 has less than this many
93 * bytes added since last reseed.
94 */
95 #define POOL0_FILL (256/8)
96
97 /*
98 * Algorithm constants
99 */
100
101 /* Both cipher key size and hash result size */
102 #define BLOCK 32
103
104 /* cipher block size */
105 #define CIPH_BLOCK 16
106
107 /* for internal wrappers */
108 #define MD_CTX SHA256_CTX
109 #define CIPH_CTX AES_KEY
110
111 struct fortuna_state
112 {
113 unsigned char counter[CIPH_BLOCK];
114 unsigned char result[CIPH_BLOCK];
115 unsigned char key[BLOCK];
116 MD_CTX pool[NUM_POOLS];
117 CIPH_CTX ciph;
118 unsigned reseed_count;
119 struct timeval last_reseed_time;
120 unsigned pool0_bytes;
121 unsigned rnd_pos;
122 int tricks_done;
123 pid_t pid;
124 };
125 typedef struct fortuna_state FState;
126
127
128 /*
129 * Use our own wrappers here.
130 * - Need to get intermediate result from digest, without affecting it.
131 * - Need re-set key on a cipher context.
132 * - Algorithms are guaranteed to exist.
133 * - No memory allocations.
134 */
135
136 static void
ciph_init(CIPH_CTX * ctx,const unsigned char * key,int klen)137 ciph_init(CIPH_CTX * ctx, const unsigned char *key, int klen)
138 {
139 AES_set_encrypt_key(key, klen * 8, ctx);
140 }
141
142 static void
ciph_encrypt(CIPH_CTX * ctx,const unsigned char * in,unsigned char * out)143 ciph_encrypt(CIPH_CTX * ctx, const unsigned char *in, unsigned char *out)
144 {
145 AES_encrypt(in, out, ctx);
146 }
147
148 static void
md_init(MD_CTX * ctx)149 md_init(MD_CTX * ctx)
150 {
151 SHA256_Init(ctx);
152 }
153
154 static void
md_update(MD_CTX * ctx,const unsigned char * data,int len)155 md_update(MD_CTX * ctx, const unsigned char *data, int len)
156 {
157 SHA256_Update(ctx, data, len);
158 }
159
160 static void
md_result(MD_CTX * ctx,unsigned char * dst)161 md_result(MD_CTX * ctx, unsigned char *dst)
162 {
163 SHA256_CTX tmp;
164
165 memcpy(&tmp, ctx, sizeof(*ctx));
166 SHA256_Final(dst, &tmp);
167 memset(&tmp, 0, sizeof(tmp));
168 }
169
170 /*
171 * initialize state
172 */
173 static void
init_state(FState * st)174 init_state(FState * st)
175 {
176 int i;
177
178 memset(st, 0, sizeof(*st));
179 for (i = 0; i < NUM_POOLS; i++)
180 md_init(&st->pool[i]);
181 st->pid = getpid();
182 }
183
184 /*
185 * Endianess does not matter.
186 * It just needs to change without repeating.
187 */
188 static void
inc_counter(FState * st)189 inc_counter(FState * st)
190 {
191 uint32_t *val = (uint32_t *) st->counter;
192
193 if (++val[0])
194 return;
195 if (++val[1])
196 return;
197 if (++val[2])
198 return;
199 ++val[3];
200 }
201
202 /*
203 * This is called 'cipher in counter mode'.
204 */
205 static void
encrypt_counter(FState * st,unsigned char * dst)206 encrypt_counter(FState * st, unsigned char *dst)
207 {
208 ciph_encrypt(&st->ciph, st->counter, dst);
209 inc_counter(st);
210 }
211
212
213 /*
214 * The time between reseed must be at least RESEED_INTERVAL
215 * microseconds.
216 */
217 static int
enough_time_passed(FState * st)218 enough_time_passed(FState * st)
219 {
220 int ok;
221 struct timeval tv;
222 struct timeval *last = &st->last_reseed_time;
223
224 gettimeofday(&tv, NULL);
225
226 /* check how much time has passed */
227 ok = 0;
228 if (tv.tv_sec > last->tv_sec + 1)
229 ok = 1;
230 else if (tv.tv_sec == last->tv_sec + 1)
231 {
232 if (1000000 + tv.tv_usec - last->tv_usec >= RESEED_INTERVAL)
233 ok = 1;
234 }
235 else if (tv.tv_usec - last->tv_usec >= RESEED_INTERVAL)
236 ok = 1;
237
238 /* reseed will happen, update last_reseed_time */
239 if (ok)
240 memcpy(last, &tv, sizeof(tv));
241
242 memset(&tv, 0, sizeof(tv));
243
244 return ok;
245 }
246
247 /*
248 * generate new key from all the pools
249 */
250 static void
reseed(FState * st)251 reseed(FState * st)
252 {
253 unsigned k;
254 unsigned n;
255 MD_CTX key_md;
256 unsigned char buf[BLOCK];
257
258 /* set pool as empty */
259 st->pool0_bytes = 0;
260
261 /*
262 * Both #0 and #1 reseed would use only pool 0. Just skip #0 then.
263 */
264 n = ++st->reseed_count;
265
266 /*
267 * The goal: use k-th pool only 1/(2^k) of the time.
268 */
269 md_init(&key_md);
270 for (k = 0; k < NUM_POOLS; k++)
271 {
272 md_result(&st->pool[k], buf);
273 md_update(&key_md, buf, BLOCK);
274
275 if (n & 1 || !n)
276 break;
277 n >>= 1;
278 }
279
280 /* add old key into mix too */
281 md_update(&key_md, st->key, BLOCK);
282
283 /* add pid to make output diverse after fork() */
284 md_update(&key_md, (const unsigned char *)&st->pid, sizeof(st->pid));
285
286 /* now we have new key */
287 md_result(&key_md, st->key);
288
289 /* use new key */
290 ciph_init(&st->ciph, st->key, BLOCK);
291
292 memset(&key_md, 0, sizeof(key_md));
293 memset(buf, 0, BLOCK);
294 }
295
296 /*
297 * Pick a random pool. This uses key bytes as random source.
298 */
299 static unsigned
get_rand_pool(FState * st)300 get_rand_pool(FState * st)
301 {
302 unsigned rnd;
303
304 /*
305 * This slightly prefers lower pools - thats OK.
306 */
307 rnd = st->key[st->rnd_pos] % NUM_POOLS;
308
309 st->rnd_pos++;
310 if (st->rnd_pos >= BLOCK)
311 st->rnd_pos = 0;
312
313 return rnd;
314 }
315
316 /*
317 * update pools
318 */
319 static void
add_entropy(FState * st,const unsigned char * data,unsigned len)320 add_entropy(FState * st, const unsigned char *data, unsigned len)
321 {
322 unsigned pos;
323 unsigned char hash[BLOCK];
324 MD_CTX md;
325
326 /* hash given data */
327 md_init(&md);
328 md_update(&md, data, len);
329 md_result(&md, hash);
330
331 /*
332 * Make sure the pool 0 is initialized, then update randomly.
333 */
334 if (st->reseed_count == 0)
335 pos = 0;
336 else
337 pos = get_rand_pool(st);
338 md_update(&st->pool[pos], hash, BLOCK);
339
340 if (pos == 0)
341 st->pool0_bytes += len;
342
343 memset(hash, 0, BLOCK);
344 memset(&md, 0, sizeof(md));
345 }
346
347 /*
348 * Just take 2 next blocks as new key
349 */
350 static void
rekey(FState * st)351 rekey(FState * st)
352 {
353 encrypt_counter(st, st->key);
354 encrypt_counter(st, st->key + CIPH_BLOCK);
355 ciph_init(&st->ciph, st->key, BLOCK);
356 }
357
358 /*
359 * Hide public constants. (counter, pools > 0)
360 *
361 * This can also be viewed as spreading the startup
362 * entropy over all of the components.
363 */
364 static void
startup_tricks(FState * st)365 startup_tricks(FState * st)
366 {
367 int i;
368 unsigned char buf[BLOCK];
369
370 /* Use next block as counter. */
371 encrypt_counter(st, st->counter);
372
373 /* Now shuffle pools, excluding #0 */
374 for (i = 1; i < NUM_POOLS; i++)
375 {
376 encrypt_counter(st, buf);
377 encrypt_counter(st, buf + CIPH_BLOCK);
378 md_update(&st->pool[i], buf, BLOCK);
379 }
380 memset(buf, 0, BLOCK);
381
382 /* Hide the key. */
383 rekey(st);
384
385 /* This can be done only once. */
386 st->tricks_done = 1;
387 }
388
389 static void
extract_data(FState * st,unsigned count,unsigned char * dst)390 extract_data(FState * st, unsigned count, unsigned char *dst)
391 {
392 unsigned n;
393 unsigned block_nr = 0;
394 pid_t pid = getpid();
395
396 /* Should we reseed? */
397 if (st->pool0_bytes >= POOL0_FILL || st->reseed_count == 0)
398 if (enough_time_passed(st))
399 reseed(st);
400
401 /* Do some randomization on first call */
402 if (!st->tricks_done)
403 startup_tricks(st);
404
405 /* If we forked, force a reseed again */
406 if (pid != st->pid) {
407 st->pid = pid;
408 reseed(st);
409 }
410
411 while (count > 0)
412 {
413 /* produce bytes */
414 encrypt_counter(st, st->result);
415
416 /* copy result */
417 if (count > CIPH_BLOCK)
418 n = CIPH_BLOCK;
419 else
420 n = count;
421 memcpy(dst, st->result, n);
422 dst += n;
423 count -= n;
424
425 /* must not give out too many bytes with one key */
426 block_nr++;
427 if (block_nr > (RESEED_BYTES / CIPH_BLOCK))
428 {
429 rekey(st);
430 block_nr = 0;
431 }
432 }
433 /* Set new key for next request. */
434 rekey(st);
435 }
436
437 /*
438 * public interface
439 */
440
441 static FState main_state;
442 static int init_done;
443 static int have_entropy;
444 #define FORTUNA_RESEED_BYTE 10000
445 static unsigned resend_bytes;
446
447 /*
448 * This mutex protects all of the above static elements from concurrent
449 * access by multiple threads
450 */
451 static HEIMDAL_MUTEX fortuna_mutex = HEIMDAL_MUTEX_INITIALIZER;
452
453 /*
454 * Try our best to do an inital seed
455 */
456 #define INIT_BYTES 128
457
458 /*
459 * fortuna_mutex must be held across calls to this function
460 */
461
462 static int
fortuna_reseed(void)463 fortuna_reseed(void)
464 {
465 int entropy_p = 0;
466
467 if (!init_done)
468 abort();
469
470 #ifndef NO_RAND_UNIX_METHOD
471 {
472 unsigned char buf[INIT_BYTES];
473 if ((*hc_rand_unix_method.bytes)(buf, sizeof(buf)) == 1) {
474 add_entropy(&main_state, buf, sizeof(buf));
475 entropy_p = 1;
476 memset(buf, 0, sizeof(buf));
477 }
478 }
479 #endif
480 #ifdef HAVE_ARC4RANDOM
481 {
482 uint32_t buf[INIT_BYTES / sizeof(uint32_t)];
483 int i;
484
485 for (i = 0; i < sizeof(buf)/sizeof(buf[0]); i++)
486 buf[i] = arc4random();
487 add_entropy(&main_state, (void *)buf, sizeof(buf));
488 entropy_p = 1;
489 }
490 #endif
491 #ifndef NO_RAND_EGD_METHOD
492 /*
493 * Only to get egd entropy if /dev/random or arc4rand failed since
494 * it can be horribly slow to generate new bits.
495 */
496 if (!entropy_p) {
497 unsigned char buf[INIT_BYTES];
498 if ((*hc_rand_egd_method.bytes)(buf, sizeof(buf)) == 1) {
499 add_entropy(&main_state, buf, sizeof(buf));
500 entropy_p = 1;
501 memset(buf, 0, sizeof(buf));
502 }
503 }
504 #endif
505 /*
506 * Fall back to gattering data from timer and secret files, this
507 * is really the last resort.
508 */
509 if (!entropy_p) {
510 /* to save stackspace */
511 union {
512 unsigned char buf[INIT_BYTES];
513 unsigned char shad[1001];
514 } u;
515 int fd;
516
517 /* add timer info */
518 if ((*hc_rand_timer_method.bytes)(u.buf, sizeof(u.buf)) == 1)
519 add_entropy(&main_state, u.buf, sizeof(u.buf));
520 /* add /etc/shadow */
521 fd = open("/etc/shadow", O_RDONLY, 0);
522 if (fd >= 0) {
523 ssize_t n;
524 rk_cloexec(fd);
525 /* add_entropy will hash the buf */
526 while ((n = read(fd, (char *)u.shad, sizeof(u.shad))) > 0)
527 add_entropy(&main_state, u.shad, sizeof(u.shad));
528 close(fd);
529 }
530
531 memset(&u, 0, sizeof(u));
532
533 entropy_p = 1; /* sure about this ? */
534 }
535 {
536 pid_t pid = getpid();
537 add_entropy(&main_state, (void *)&pid, sizeof(pid));
538 }
539 {
540 struct timeval tv;
541 gettimeofday(&tv, NULL);
542 add_entropy(&main_state, (void *)&tv, sizeof(tv));
543 }
544 #ifdef HAVE_GETUID
545 {
546 uid_t u = getuid();
547 add_entropy(&main_state, (void *)&u, sizeof(u));
548 }
549 #endif
550 return entropy_p;
551 }
552
553 /*
554 * fortuna_mutex must be held by callers of this function
555 */
556 static int
fortuna_init(void)557 fortuna_init(void)
558 {
559 if (!init_done)
560 {
561 init_state(&main_state);
562 init_done = 1;
563 }
564 if (!have_entropy)
565 have_entropy = fortuna_reseed();
566 return (init_done && have_entropy);
567 }
568
569
570
571 static void
fortuna_seed(const void * indata,int size)572 fortuna_seed(const void *indata, int size)
573 {
574 HEIMDAL_MUTEX_lock(&fortuna_mutex);
575
576 fortuna_init();
577 add_entropy(&main_state, indata, size);
578 if (size >= INIT_BYTES)
579 have_entropy = 1;
580
581 HEIMDAL_MUTEX_unlock(&fortuna_mutex);
582 }
583
584 static int
fortuna_bytes(unsigned char * outdata,int size)585 fortuna_bytes(unsigned char *outdata, int size)
586 {
587 int ret = 0;
588
589 HEIMDAL_MUTEX_lock(&fortuna_mutex);
590
591 if (!fortuna_init())
592 goto out;
593
594 resend_bytes += size;
595 if (resend_bytes > FORTUNA_RESEED_BYTE || resend_bytes < size) {
596 resend_bytes = 0;
597 fortuna_reseed();
598 }
599 extract_data(&main_state, size, outdata);
600 ret = 1;
601
602 out:
603 HEIMDAL_MUTEX_unlock(&fortuna_mutex);
604
605 return ret;
606 }
607
608 static void
fortuna_cleanup(void)609 fortuna_cleanup(void)
610 {
611 HEIMDAL_MUTEX_lock(&fortuna_mutex);
612
613 init_done = 0;
614 have_entropy = 0;
615 memset(&main_state, 0, sizeof(main_state));
616
617 HEIMDAL_MUTEX_unlock(&fortuna_mutex);
618 }
619
620 static void
fortuna_add(const void * indata,int size,double entropi)621 fortuna_add(const void *indata, int size, double entropi)
622 {
623 fortuna_seed(indata, size);
624 }
625
626 static int
fortuna_pseudorand(unsigned char * outdata,int size)627 fortuna_pseudorand(unsigned char *outdata, int size)
628 {
629 return fortuna_bytes(outdata, size);
630 }
631
632 static int
fortuna_status(void)633 fortuna_status(void)
634 {
635 int result;
636
637 HEIMDAL_MUTEX_lock(&fortuna_mutex);
638 result = fortuna_init();
639 HEIMDAL_MUTEX_unlock(&fortuna_mutex);
640
641 return result ? 1 : 0;
642 }
643
644 const RAND_METHOD hc_rand_fortuna_method = {
645 fortuna_seed,
646 fortuna_bytes,
647 fortuna_cleanup,
648 fortuna_add,
649 fortuna_pseudorand,
650 fortuna_status
651 };
652
653 const RAND_METHOD *
RAND_fortuna_method(void)654 RAND_fortuna_method(void)
655 {
656 return &hc_rand_fortuna_method;
657 }
658