5 * Copyright (c) 2005 Marko Kreen
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
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.
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
29 * $PostgreSQL: pgsql/contrib/pgcrypto/fortuna.c,v 1.8 2006/10/04 00:29:46 momjian Exp $
35 #include <heim_threads.h>
38 #include <krb5-types.h>
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:
50 * http://en.wikipedia.org/wiki/Fortuna_(PRNG)
52 * http://jlcooke.ca/random/
53 * - Jean-Luc Cooke Fortuna-based /dev/random driver for Linux.
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.
63 * J.L. Cooke fixed this by feeding previous hash to new re-initialized
66 * Fortuna predecessor Yarrow requires ability to query intermediate
67 * 'final result' from hash, without affecting it.
69 * This implementation uses the Yarrow method - asking intermediate
70 * results, but continuing with old state.
75 * Algorithm parameters
81 #define RESEED_INTERVAL 100000 /* 0.1 sec */
83 /* for one big request, reseed after this many bytes */
84 #define RESEED_BYTES (1024*1024)
87 * Skip reseed if pool 0 has less than this many
88 * bytes added since last reseed.
90 #define POOL0_FILL (256/8)
96 /* Both cipher key size and hash result size */
99 /* cipher block size */
100 #define CIPH_BLOCK 16
102 /* for internal wrappers */
103 #define MD_CTX SHA256_CTX
104 #define CIPH_CTX AES_KEY
108 unsigned char counter
[CIPH_BLOCK
];
109 unsigned char result
[CIPH_BLOCK
];
110 unsigned char key
[BLOCK
];
111 MD_CTX pool
[NUM_POOLS
];
113 unsigned reseed_count
;
114 struct timeval last_reseed_time
;
115 unsigned pool0_bytes
;
120 typedef struct fortuna_state FState
;
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.
132 ciph_init(CIPH_CTX
* ctx
, const unsigned char *key
, int klen
)
134 AES_set_encrypt_key(key
, klen
* 8, ctx
);
138 ciph_encrypt(CIPH_CTX
* ctx
, const unsigned char *in
, unsigned char *out
)
140 AES_encrypt(in
, out
, ctx
);
144 md_init(MD_CTX
* ctx
)
150 md_update(MD_CTX
* ctx
, const unsigned char *data
, int len
)
152 SHA256_Update(ctx
, data
, len
);
156 md_result(MD_CTX
* ctx
, unsigned char *dst
)
160 memcpy(&tmp
, ctx
, sizeof(*ctx
));
161 SHA256_Final(dst
, &tmp
);
162 memset_s(&tmp
, sizeof(tmp
), 0, sizeof(tmp
));
169 init_state(FState
* st
)
173 memset(st
, 0, sizeof(*st
));
174 for (i
= 0; i
< NUM_POOLS
; i
++)
175 md_init(&st
->pool
[i
]);
180 * Endianess does not matter.
181 * It just needs to change without repeating.
184 inc_counter(FState
* st
)
186 uint32_t *val
= (uint32_t *) st
->counter
;
198 * This is called 'cipher in counter mode'.
201 encrypt_counter(FState
* st
, unsigned char *dst
)
203 ciph_encrypt(&st
->ciph
, st
->counter
, dst
);
209 * The time between reseed must be at least RESEED_INTERVAL
213 enough_time_passed(FState
* st
)
217 struct timeval
*last
= &st
->last_reseed_time
;
219 gettimeofday(&tv
, NULL
);
221 /* check how much time has passed */
223 if (tv
.tv_sec
> last
->tv_sec
+ 1)
225 else if (tv
.tv_sec
== last
->tv_sec
+ 1)
227 if (1000000 + tv
.tv_usec
- last
->tv_usec
>= RESEED_INTERVAL
)
230 else if (tv
.tv_usec
- last
->tv_usec
>= RESEED_INTERVAL
)
233 /* reseed will happen, update last_reseed_time */
235 memcpy(last
, &tv
, sizeof(tv
));
237 memset_s(&tv
, sizeof(tv
), 0, sizeof(tv
));
243 * generate new key from all the pools
251 unsigned char buf
[BLOCK
];
253 /* set pool as empty */
257 * Both #0 and #1 reseed would use only pool 0. Just skip #0 then.
259 n
= ++st
->reseed_count
;
262 * The goal: use k-th pool only 1/(2^k) of the time.
265 for (k
= 0; k
< NUM_POOLS
; k
++)
267 md_result(&st
->pool
[k
], buf
);
268 md_update(&key_md
, buf
, BLOCK
);
275 /* add old key into mix too */
276 md_update(&key_md
, st
->key
, BLOCK
);
278 /* add pid to make output diverse after fork() */
279 md_update(&key_md
, (const unsigned char *)&st
->pid
, sizeof(st
->pid
));
281 /* now we have new key */
282 md_result(&key_md
, st
->key
);
285 ciph_init(&st
->ciph
, st
->key
, BLOCK
);
287 memset_s(&key_md
, sizeof(key_md
), 0, sizeof(key_md
));
288 memset_s(buf
, sizeof(buf
), 0, sizeof(buf
));
292 * Pick a random pool. This uses key bytes as random source.
295 get_rand_pool(FState
* st
)
300 * This slightly prefers lower pools - thats OK.
302 rnd
= st
->key
[st
->rnd_pos
] % NUM_POOLS
;
305 if (st
->rnd_pos
>= BLOCK
)
315 add_entropy(FState
* st
, const unsigned char *data
, unsigned len
)
318 unsigned char hash
[BLOCK
];
321 /* hash given data */
323 md_update(&md
, data
, len
);
324 md_result(&md
, hash
);
327 * Make sure the pool 0 is initialized, then update randomly.
329 if (st
->reseed_count
== 0)
332 pos
= get_rand_pool(st
);
333 md_update(&st
->pool
[pos
], hash
, BLOCK
);
336 st
->pool0_bytes
+= len
;
338 memset_s(hash
, sizeof(hash
), 0, sizeof(hash
));
339 memset_s(&md
, sizeof(md
), 0, sizeof(md
));
343 * Just take 2 next blocks as new key
348 encrypt_counter(st
, st
->key
);
349 encrypt_counter(st
, st
->key
+ CIPH_BLOCK
);
350 ciph_init(&st
->ciph
, st
->key
, BLOCK
);
354 * Hide public constants. (counter, pools > 0)
356 * This can also be viewed as spreading the startup
357 * entropy over all of the components.
360 startup_tricks(FState
* st
)
363 unsigned char buf
[BLOCK
];
365 /* Use next block as counter. */
366 encrypt_counter(st
, st
->counter
);
368 /* Now shuffle pools, excluding #0 */
369 for (i
= 1; i
< NUM_POOLS
; i
++)
371 encrypt_counter(st
, buf
);
372 encrypt_counter(st
, buf
+ CIPH_BLOCK
);
373 md_update(&st
->pool
[i
], buf
, BLOCK
);
375 memset_s(buf
, sizeof(buf
), 0, sizeof(buf
));
380 /* This can be done only once. */
385 extract_data(FState
* st
, unsigned count
, unsigned char *dst
)
388 unsigned block_nr
= 0;
389 pid_t pid
= getpid();
391 /* Should we reseed? */
392 if (st
->pool0_bytes
>= POOL0_FILL
|| st
->reseed_count
== 0)
393 if (enough_time_passed(st
))
396 /* Do some randomization on first call */
397 if (!st
->tricks_done
)
400 /* If we forked, force a reseed again */
401 if (pid
!= st
->pid
) {
409 encrypt_counter(st
, st
->result
);
412 if (count
> CIPH_BLOCK
)
416 memcpy(dst
, st
->result
, n
);
420 /* must not give out too many bytes with one key */
422 if (block_nr
> (RESEED_BYTES
/ CIPH_BLOCK
))
428 /* Set new key for next request. */
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
;
443 * This mutex protects all of the above static elements from concurrent
444 * access by multiple threads
446 static HEIMDAL_MUTEX fortuna_mutex
= HEIMDAL_MUTEX_INITIALIZER
;
449 * Try our best to do an initial seed
451 #define INIT_BYTES 128
454 * fortuna_mutex must be held across calls to this function
465 #ifndef NO_RAND_UNIX_METHOD
467 unsigned char buf
[INIT_BYTES
];
468 if ((*hc_rand_unix_method
.bytes
)(buf
, sizeof(buf
)) == 1) {
469 add_entropy(&main_state
, buf
, sizeof(buf
));
471 memset_s(buf
, sizeof(buf
), 0, sizeof(buf
));
475 #ifdef HAVE_ARC4RANDOM
477 uint32_t buf
[INIT_BYTES
/ sizeof(uint32_t)];
480 for (i
= 0; i
< sizeof(buf
)/sizeof(buf
[0]); i
++)
481 buf
[i
] = arc4random();
482 add_entropy(&main_state
, (void *)buf
, sizeof(buf
));
487 * Fall back to gattering data from timer and secret files, this
488 * is really the last resort.
491 /* to save stackspace */
493 unsigned char buf
[INIT_BYTES
];
494 unsigned char shad
[1001];
499 if ((*hc_rand_timer_method
.bytes
)(u
.buf
, sizeof(u
.buf
)) == 1)
500 add_entropy(&main_state
, u
.buf
, sizeof(u
.buf
));
501 /* add /etc/shadow */
502 fd
= open("/etc/shadow", O_RDONLY
, 0);
505 /* add_entropy will hash the buf */
506 while (read(fd
, (char *)u
.shad
, sizeof(u
.shad
)) > 0)
507 add_entropy(&main_state
, u
.shad
, sizeof(u
.shad
));
511 memset_s(&u
, sizeof(u
), 0, sizeof(u
));
513 entropy_p
= 1; /* sure about this ? */
516 pid_t pid
= getpid();
517 add_entropy(&main_state
, (void *)&pid
, sizeof(pid
));
521 gettimeofday(&tv
, NULL
);
522 add_entropy(&main_state
, (void *)&tv
, sizeof(tv
));
527 add_entropy(&main_state
, (void *)&u
, sizeof(u
));
534 * fortuna_mutex must be held by callers of this function
541 init_state(&main_state
);
545 have_entropy
= fortuna_reseed();
546 return (init_done
&& have_entropy
);
552 fortuna_seed(const void *indata
, int size
)
554 HEIMDAL_MUTEX_lock(&fortuna_mutex
);
557 add_entropy(&main_state
, indata
, size
);
558 if (size
>= INIT_BYTES
)
561 HEIMDAL_MUTEX_unlock(&fortuna_mutex
);
565 fortuna_bytes(unsigned char *outdata
, int size
)
569 HEIMDAL_MUTEX_lock(&fortuna_mutex
);
574 resend_bytes
+= size
;
575 if (resend_bytes
> FORTUNA_RESEED_BYTE
|| resend_bytes
< size
) {
579 extract_data(&main_state
, size
, outdata
);
583 HEIMDAL_MUTEX_unlock(&fortuna_mutex
);
589 fortuna_cleanup(void)
591 HEIMDAL_MUTEX_lock(&fortuna_mutex
);
595 memset_s(&main_state
, sizeof(main_state
), 0, sizeof(main_state
));
597 HEIMDAL_MUTEX_unlock(&fortuna_mutex
);
601 fortuna_add(const void *indata
, int size
, double entropi
)
603 fortuna_seed(indata
, size
);
607 fortuna_pseudorand(unsigned char *outdata
, int size
)
609 return fortuna_bytes(outdata
, size
);
617 HEIMDAL_MUTEX_lock(&fortuna_mutex
);
618 result
= fortuna_init();
619 HEIMDAL_MUTEX_unlock(&fortuna_mutex
);
621 return result
? 1 : 0;
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
,
630 .pseudorand
= fortuna_pseudorand
,
631 .status
= fortuna_status
634 const RAND_METHOD hc_rand_fortuna_method
= {
645 RAND_fortuna_method(void)
647 return &hc_rand_fortuna_method
;