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
111struct 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};
125typedef 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
136static void
137ciph_init(CIPH_CTX * ctx, const unsigned char *key, int klen)
138{
139    AES_set_encrypt_key(key, klen * 8, ctx);
140}
141
142static void
143ciph_encrypt(CIPH_CTX * ctx, const unsigned char *in, unsigned char *out)
144{
145    AES_encrypt(in, out, ctx);
146}
147
148static void
149md_init(MD_CTX * ctx)
150{
151    SHA256_Init(ctx);
152}
153
154static void
155md_update(MD_CTX * ctx, const unsigned char *data, int len)
156{
157    SHA256_Update(ctx, data, len);
158}
159
160static void
161md_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 */
173static void
174init_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 */
188static void
189inc_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 */
205static void
206encrypt_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 */
217static int
218enough_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 */
250static void
251reseed(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 */
299static unsigned
300get_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 */
319static void
320add_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 */
350static void
351rekey(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 */
364static void
365startup_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
389static void
390extract_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
441static FState	main_state;
442static int	init_done;
443static int	have_entropy;
444#define FORTUNA_RESEED_BYTE	10000
445static unsigned	resend_bytes;
446
447/*
448 * This mutex protects all of the above static elements from concurrent
449 * access by multiple threads
450 */
451static 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
462static int
463fortuna_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 */
556static int
557fortuna_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
571static void
572fortuna_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
584static int
585fortuna_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
602out:
603    HEIMDAL_MUTEX_unlock(&fortuna_mutex);
604
605    return ret;
606}
607
608static void
609fortuna_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
620static void
621fortuna_add(const void *indata, int size, double entropi)
622{
623    fortuna_seed(indata, size);
624}
625
626static int
627fortuna_pseudorand(unsigned char *outdata, int size)
628{
629    return fortuna_bytes(outdata, size);
630}
631
632static int
633fortuna_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
644const 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
653const RAND_METHOD *
654RAND_fortuna_method(void)
655{
656    return &hc_rand_fortuna_method;
657}
658