1
/* -*- mode: c; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2
/* lib/crypto/krb/prng_fortuna.c - Fortuna PRNG implementation */
4
* Copyright (c) 2005 Marko Kreen
7
* Redistribution and use in source and binary forms, with or without
8
* modification, are permitted provided that the following conditions
10
* 1. Redistributions of source code must retain the above copyright
11
* notice, this list of conditions and the following disclaimer.
12
* 2. Redistributions in binary form must reproduce the above copyright
13
* notice, this list of conditions and the following disclaimer in the
14
* documentation and/or other materials provided with the distribution.
16
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
17
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19
* ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
20
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
22
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
23
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
24
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
25
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29
* Copyright (C) 2010, 2011 by the Massachusetts Institute of Technology.
30
* All rights reserved.
33
* Export of this software from the United States of America may require
34
* a specific license from the United States Government. It is the
35
* responsibility of any person or organization contemplating export to
36
* obtain such a license before exporting.
38
* WITHIN THAT CONSTRAINT, permission to use, copy, modify, and
39
* distribute this software and its documentation for any purpose and
40
* without fee is hereby granted, provided that the above copyright
41
* notice appear in all copies and that both that copyright notice and
42
* this permission notice appear in supporting documentation, and that
43
* the name of M.I.T. not be used in advertising or publicity pertaining
44
* to distribution of the software without specific, written prior
45
* permission. Furthermore if you modify this software you must label
46
* your software as modified software and not distribute it in such a
47
* fashion that it might be confused with the original M.I.T. software.
48
* M.I.T. makes no representations about the suitability of
49
* this software for any purpose. It is provided "as is" without express
50
* or implied warranty.
54
* This file implements the generator and accumulator parts of the Fortuna PRNG
55
* as described in chapter 9 of _Cryptography Engineering_ by Ferguson,
56
* Schneier, and Kohno.
58
* The generator, once seeded with an unguessable value, produces an unlimited
59
* number of pseudo-random outputs which cannot be used to determine the
60
* internal state of the generator (without an unreasonable amount of
61
* computational power). The generator protects against the case where the OS
62
* random number generator is not cryptographically secure, but can produce an
63
* unguessable initial seed. Successive reseeds of the generator will not make
64
* the internal state any more guessable than it was before.
66
* The accumulator is layered on top of the generator, and seeks to eventually
67
* recover from the case where the OS random number generator did not produce
68
* an unguessable initial seed. Unreliable entropy inputs are collected into
69
* 32 pools, which are used to reseed the generator when enough entropy has
70
* been collected. Each pool collects twice as much entropy between reseeds as
71
* the previous one; eventually a reseed will occur involving a pool with
72
* enough entropy that an attacker cannot maintain knowledge of the generator's
73
* internal state. The accumulator is only helpful for a long-running process
74
* such as a KDC which can submit periodic entropy inputs to the PRNG.
77
#include "crypto_int.h"
79
/* The accumulator's number of pools. */
82
/* Minimum reseed interval in microseconds. */
83
#define RESEED_INTERVAL 100000 /* 0.1 sec */
85
/* For one big request, change the key after this many bytes. */
86
#define MAX_BYTES_PER_KEY (1 << 20)
88
/* Reseed if pool 0 has had this many bytes added since last reseed. */
89
#define MIN_POOL_LEN 64
91
/* AES-256 key size in bytes. */
92
#define AES256_KEYSIZE (256/8)
94
/* AES-256 block size in bytes. */
95
#define AES256_BLOCKSIZE (128/8)
97
/* SHA-256 block size in bytes. */
98
#define SHA256_BLOCKSIZE (512/8)
100
/* SHA-256 result size in bytes. */
101
#define SHA256_HASHSIZE (256/8)
103
/* Genarator - block cipher in CTR mode */
106
/* Generator state. */
107
unsigned char counter[AES256_BLOCKSIZE];
108
unsigned char key[AES256_KEYSIZE];
111
/* Accumulator state. */
112
SHA256_CTX pool[NUM_POOLS];
113
unsigned int pool_index;
114
unsigned int reseed_count;
115
struct timeval last_reseed_time;
116
unsigned int pool0_bytes;
120
* SHA[d]-256(m) is defined as SHA-256(SHA-256(0^512||m))--that is, hash a
121
* block full of zeros followed by the input data, then re-hash the result.
122
* These functions implement the SHA[d]-256 function on incremental inputs.
126
shad256_init(SHA256_CTX *ctx)
128
unsigned char zero[SHA256_BLOCKSIZE];
130
/* Initialize the inner SHA-256 context and update it with a zero block. */
131
memset(zero, 0, sizeof(zero));
133
k5_sha256_update(ctx, zero, sizeof(zero));
137
shad256_update(SHA256_CTX *ctx, const unsigned char *data, int len)
139
/* Feed the input to the inner SHA-256 context. */
140
k5_sha256_update(ctx, data, len);
144
shad256_result(SHA256_CTX *ctx, unsigned char *dst)
146
/* Finalize the inner context, then feed the result back through SHA256. */
147
k5_sha256_final(dst, ctx);
149
k5_sha256_update(ctx, dst, SHA256_HASHSIZE);
150
k5_sha256_final(dst, ctx);
153
/* Initialize state. */
155
init_state(struct fortuna_state *st)
159
memset(st, 0, sizeof(*st));
160
for (i = 0; i < NUM_POOLS; i++)
161
shad256_init(&st->pool[i]);
164
/* Increment st->counter using least significant byte first. */
166
inc_counter(struct fortuna_state *st)
170
val = load_64_le(st->counter) + 1;
171
store_64_le(val, st->counter);
173
val = load_64_le(st->counter + 8) + 1;
174
store_64_le(val, st->counter + 8);
178
/* Encrypt and increment st->counter in the current cipher context. */
180
encrypt_counter(struct fortuna_state *st, unsigned char *dst)
182
krb5int_aes_enc_blk(st->counter, dst, &st->ciph);
186
/* Reseed the generator based on hopefully non-guessable input. */
188
generator_reseed(struct fortuna_state *st, const unsigned char *data,
193
/* Calculate SHA[d]-256(key||s) and make that the new key. Depend on the
194
* SHA-256 hash size being the AES-256 key size. */
196
shad256_update(&ctx, st->key, AES256_KEYSIZE);
197
shad256_update(&ctx, data, len);
198
shad256_result(&ctx, st->key);
199
zap(&ctx, sizeof(ctx));
200
krb5int_aes_enc_key(st->key, AES256_KEYSIZE, &st->ciph);
202
/* Increment counter. */
206
/* Generate two blocks in counter mode and replace the key with the result. */
208
change_key(struct fortuna_state *st)
210
encrypt_counter(st, st->key);
211
encrypt_counter(st, st->key + AES256_BLOCKSIZE);
212
krb5int_aes_enc_key(st->key, AES256_KEYSIZE, &st->ciph);
215
/* Output pseudo-random data from the generator. */
217
generator_output(struct fortuna_state *st, unsigned char *dst, size_t len)
219
unsigned char result[AES256_BLOCKSIZE];
223
/* Produce bytes and copy the result into dst. */
224
encrypt_counter(st, result);
225
n = (len < AES256_BLOCKSIZE) ? len : AES256_BLOCKSIZE;
226
memcpy(dst, result, n);
230
/* Each time we reach MAX_BYTES_PER_KEY bytes, change the key. */
231
count += AES256_BLOCKSIZE;
232
if (count >= MAX_BYTES_PER_KEY) {
237
zap(result, sizeof(result));
239
/* Change the key after each request. */
243
/* Reseed the generator using the accumulator pools. */
245
accumulator_reseed(struct fortuna_state *st)
249
unsigned char hash_result[SHA256_HASHSIZE];
251
n = ++st->reseed_count;
254
* Collect entropy from pools. We use the i-th pool only 1/(2^i) of the
255
* time so that each pool collects twice as much entropy between uses as
259
for (i = 0; i < NUM_POOLS; i++) {
260
if (n % (1 << i) != 0)
263
/* Harvest this pool's hash result into ctx, then reset the pool. */
264
shad256_result(&st->pool[i], hash_result);
265
shad256_init(&st->pool[i]);
266
shad256_update(&ctx, hash_result, SHA256_HASHSIZE);
268
shad256_result(&ctx, hash_result);
269
generator_reseed(st, hash_result, SHA256_HASHSIZE);
270
zap(hash_result, SHA256_HASHSIZE);
271
zap(&ctx, sizeof(ctx));
273
/* Reset the count of bytes added to pool 0. */
277
/* Add possibly unguessable data to the next accumulator pool. */
279
accumulator_add_event(struct fortuna_state *st, const unsigned char *data,
282
unsigned char lenbuf[2];
285
/* Track how many bytes have been added to pool 0. */
286
if (st->pool_index == 0 && st->pool0_bytes < MIN_POOL_LEN)
287
st->pool0_bytes += len;
289
/* Hash events into successive accumulator pools. */
290
pool = &st->pool[st->pool_index];
291
st->pool_index = (st->pool_index + 1) % NUM_POOLS;
294
* Fortuna specifies that events are encoded with a source identifier byte,
295
* a length byte, and the event data itself. We do not have source
296
* identifiers and they're not really important, so just encode the
297
* length in two bytes instead.
299
store_16_be(len, lenbuf);
300
shad256_update(pool, lenbuf, 2);
301
shad256_update(pool, data, len);
304
/* Limit dependencies for test program. */
307
/* Return true if RESEED_INTERVAL microseconds have passed since the last
310
enough_time_passed(struct fortuna_state *st)
312
struct timeval tv, *last = &st->last_reseed_time;
313
krb5_boolean ok = FALSE;
315
gettimeofday(&tv, NULL);
317
/* Check how much time has passed. */
318
if (tv.tv_sec > last->tv_sec + 1)
320
else if (tv.tv_sec == last->tv_sec + 1) {
321
if (1000000 + tv.tv_usec - last->tv_usec >= RESEED_INTERVAL)
323
} else if (tv.tv_usec - last->tv_usec >= RESEED_INTERVAL)
326
/* Update last_reseed_time if we're returning success. */
328
memcpy(last, &tv, sizeof(tv));
334
accumulator_output(struct fortuna_state *st, unsigned char *dst, size_t len)
336
/* Reseed the generator with data from pools if we have accumulated enough
337
* data and enough time has passed since the last accumulator reseed. */
338
if (st->pool0_bytes >= MIN_POOL_LEN && enough_time_passed(st))
339
accumulator_reseed(st);
341
generator_output(st, dst, len);
344
static k5_mutex_t fortuna_lock = K5_MUTEX_PARTIAL_INITIALIZER;
345
static struct fortuna_state main_state;
347
static DWORD last_pid;
349
static pid_t last_pid;
351
static krb5_boolean have_entropy = FALSE;
356
krb5_error_code ret = 0;
357
unsigned char osbuf[64];
359
ret = k5_mutex_finish_init(&fortuna_lock);
363
init_state(&main_state);
365
last_pid = GetCurrentProcessId();
369
if (k5_get_os_entropy(osbuf, sizeof(osbuf))) {
370
generator_reseed(&main_state, osbuf, sizeof(osbuf));
378
k5_prng_cleanup(void)
380
have_entropy = FALSE;
381
zap(&main_state, sizeof(main_state));
382
k5_mutex_destroy(&fortuna_lock);
385
krb5_error_code KRB5_CALLCONV
386
krb5_c_random_add_entropy(krb5_context context, unsigned int randsource,
387
const krb5_data *indata)
391
ret = krb5int_crypto_init();
394
ret = k5_mutex_lock(&fortuna_lock);
397
if (randsource == KRB5_C_RANDSOURCE_OSRAND ||
398
randsource == KRB5_C_RANDSOURCE_TRUSTEDPARTY) {
399
/* These sources contain enough entropy that we should use them
400
* immediately, so that they benefit the next request. */
401
generator_reseed(&main_state, (unsigned char *)indata->data,
405
/* Other sources should just go into the pools and be used according to
406
* the accumulator logic. */
407
accumulator_add_event(&main_state, (unsigned char *)indata->data,
410
k5_mutex_unlock(&fortuna_lock);
414
krb5_error_code KRB5_CALLCONV
415
krb5_c_random_make_octets(krb5_context context, krb5_data *outdata)
419
DWORD pid = GetCurrentProcessId();
421
pid_t pid = getpid();
423
unsigned char pidbuf[4];
425
ret = k5_mutex_lock(&fortuna_lock);
430
k5_mutex_unlock(&fortuna_lock);
431
return KRB5_CRYPTO_INTERNAL;
434
if (pid != last_pid) {
435
/* We forked; make sure child's PRNG stream differs from parent's. */
436
store_32_be(pid, pidbuf);
437
generator_reseed(&main_state, pidbuf, 4);
441
accumulator_output(&main_state, (unsigned char *)outdata->data,
443
k5_mutex_unlock(&fortuna_lock);
447
#endif /* not TEST */
added
removed
src/lib/crypto/krb/prng_fortuna.c
