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