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