/* -*- mode: c; c-basic-offset: 4; indent-tabs-mode: nil -*- */
/* lib/crypto/krb/prng_fortuna.c - Fortuna PRNG implementation */
/*
* Copyright (c) 2005 Marko Kreen
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*/
/*
* Copyright (C) 2010, 2011 by the Massachusetts Institute of Technology.
* All rights reserved.
*
*
* Export of this software from the United States of America may require
* a specific license from the United States Government. It is the
* responsibility of any person or organization contemplating export to
* obtain such a license before exporting.
*
* WITHIN THAT CONSTRAINT, permission to use, copy, modify, and
* distribute this software and its documentation for any purpose and
* without fee is hereby granted, provided that the above copyright
* notice appear in all copies and that both that copyright notice and
* this permission notice appear in supporting documentation, and that
* the name of M.I.T. not be used in advertising or publicity pertaining
* to distribution of the software without specific, written prior
* permission. Furthermore if you modify this software you must label
* your software as modified software and not distribute it in such a
* fashion that it might be confused with the original M.I.T. software.
* M.I.T. makes no representations about the suitability of
* this software for any purpose. It is provided "as is" without express
* or implied warranty.
*/
/*
* This file implements the generator and accumulator parts of the Fortuna PRNG
* as described in chapter 9 of _Cryptography Engineering_ by Ferguson,
* Schneier, and Kohno.
*
* The generator, once seeded with an unguessable value, produces an unlimited
* number of pseudo-random outputs which cannot be used to determine the
* internal state of the generator (without an unreasonable amount of
* computational power). The generator protects against the case where the OS
* random number generator is not cryptographically secure, but can produce an
* unguessable initial seed. Successive reseeds of the generator will not make
* the internal state any more guessable than it was before.
*
* The accumulator is layered on top of the generator, and seeks to eventually
* recover from the case where the OS random number generator did not produce
* an unguessable initial seed. Unreliable entropy inputs are collected into
* 32 pools, which are used to reseed the generator when enough entropy has
* been collected. Each pool collects twice as much entropy between reseeds as
* the previous one; eventually a reseed will occur involving a pool with
* enough entropy that an attacker cannot maintain knowledge of the generator's
* internal state. The accumulator is only helpful for a long-running process
* such as a KDC which can submit periodic entropy inputs to the PRNG.
*/
#include "crypto_int.h"
/* The accumulator's number of pools. */
#define NUM_POOLS 32
/* Minimum reseed interval in microseconds. */
#define RESEED_INTERVAL 100000 /* 0.1 sec */
/* For one big request, change the key after this many bytes. */
#define MAX_BYTES_PER_KEY (1 << 20)
/* Reseed if pool 0 has had this many bytes added since last reseed. */
#define MIN_POOL_LEN 64
/* AES-256 key size in bytes. */
#define AES256_KEYSIZE (256/8)
/* AES-256 block size in bytes. */
#define AES256_BLOCKSIZE (128/8)
/* SHA-256 block size in bytes. */
#define SHA256_BLOCKSIZE (512/8)
/* SHA-256 result size in bytes. */
#define SHA256_HASHSIZE (256/8)
/* Genarator - block cipher in CTR mode */
struct fortuna_state
{
/* Generator state. */
unsigned char counter[AES256_BLOCKSIZE];
unsigned char key[AES256_KEYSIZE];
aes_ctx ciph;
/* Accumulator state. */
SHA256_CTX pool[NUM_POOLS];
unsigned int pool_index;
unsigned int reseed_count;
struct timeval last_reseed_time;
unsigned int pool0_bytes;
};
/*
* SHA[d]-256(m) is defined as SHA-256(SHA-256(0^512||m))--that is, hash a
* block full of zeros followed by the input data, then re-hash the result.
* These functions implement the SHA[d]-256 function on incremental inputs.
*/
static void
shad256_init(SHA256_CTX *ctx)
{
unsigned char zero[SHA256_BLOCKSIZE];
/* Initialize the inner SHA-256 context and update it with a zero block. */
memset(zero, 0, sizeof(zero));
k5_sha256_init(ctx);
k5_sha256_update(ctx, zero, sizeof(zero));
}
static void
shad256_update(SHA256_CTX *ctx, const unsigned char *data, int len)
{
/* Feed the input to the inner SHA-256 context. */
k5_sha256_update(ctx, data, len);
}
static void
shad256_result(SHA256_CTX *ctx, unsigned char *dst)
{
/* Finalize the inner context, then feed the result back through SHA256. */
k5_sha256_final(dst, ctx);
k5_sha256_init(ctx);
k5_sha256_update(ctx, dst, SHA256_HASHSIZE);
k5_sha256_final(dst, ctx);
}
/* Initialize state. */
static void
init_state(struct fortuna_state *st)
{
unsigned int i;
memset(st, 0, sizeof(*st));
for (i = 0; i < NUM_POOLS; i++)
shad256_init(&st->pool[i]);
}
/* Increment st->counter using least significant byte first. */
static void
inc_counter(struct fortuna_state *st)
{
uint64_t val;
val = load_64_le(st->counter) + 1;
store_64_le(val, st->counter);
if (val == 0) {
val = load_64_le(st->counter + 8) + 1;
store_64_le(val, st->counter + 8);
}
}
/* Encrypt and increment st->counter in the current cipher context. */
static void
encrypt_counter(struct fortuna_state *st, unsigned char *dst)
{
krb5int_aes_enc_blk(st->counter, dst, &st->ciph);
inc_counter(st);
}
/* Reseed the generator based on hopefully non-guessable input. */
static void
generator_reseed(struct fortuna_state *st, const unsigned char *data,
size_t len)
{
SHA256_CTX ctx;
/* Calculate SHA[d]-256(key||s) and make that the new key. Depend on the
* SHA-256 hash size being the AES-256 key size. */
shad256_init(&ctx);
shad256_update(&ctx, st->key, AES256_KEYSIZE);
shad256_update(&ctx, data, len);
shad256_result(&ctx, st->key);
zap(&ctx, sizeof(ctx));
krb5int_aes_enc_key(st->key, AES256_KEYSIZE, &st->ciph);
/* Increment counter. */
inc_counter(st);
}
/* Generate two blocks in counter mode and replace the key with the result. */
static void
change_key(struct fortuna_state *st)
{
encrypt_counter(st, st->key);
encrypt_counter(st, st->key + AES256_BLOCKSIZE);
krb5int_aes_enc_key(st->key, AES256_KEYSIZE, &st->ciph);
}
/* Output pseudo-random data from the generator. */
static void
generator_output(struct fortuna_state *st, unsigned char *dst, size_t len)
{
unsigned char result[AES256_BLOCKSIZE];
size_t n, count = 0;
while (len > 0) {
/* Produce bytes and copy the result into dst. */
encrypt_counter(st, result);
n = (len < AES256_BLOCKSIZE) ? len : AES256_BLOCKSIZE;
memcpy(dst, result, n);
dst += n;
len -= n;
/* Each time we reach MAX_BYTES_PER_KEY bytes, change the key. */
count += AES256_BLOCKSIZE;
if (count >= MAX_BYTES_PER_KEY) {
change_key(st);
count = 0;
}
}
zap(result, sizeof(result));
/* Change the key after each request. */
change_key(st);
}
/* Reseed the generator using the accumulator pools. */
static void
accumulator_reseed(struct fortuna_state *st)
{
unsigned int i, n;
SHA256_CTX ctx;
unsigned char hash_result[SHA256_HASHSIZE];
n = ++st->reseed_count;
/*
* Collect entropy from pools. We use the i-th pool only 1/(2^i) of the
* time so that each pool collects twice as much entropy between uses as
* the last.
*/
shad256_init(&ctx);
for (i = 0; i < NUM_POOLS; i++) {
if (n % (1 << i) != 0)
break;
/* Harvest this pool's hash result into ctx, then reset the pool. */
shad256_result(&st->pool[i], hash_result);
shad256_init(&st->pool[i]);
shad256_update(&ctx, hash_result, SHA256_HASHSIZE);
}
shad256_result(&ctx, hash_result);
generator_reseed(st, hash_result, SHA256_HASHSIZE);
zap(hash_result, SHA256_HASHSIZE);
zap(&ctx, sizeof(ctx));
/* Reset the count of bytes added to pool 0. */
st->pool0_bytes = 0;
}
/* Add possibly unguessable data to the next accumulator pool. */
static void
accumulator_add_event(struct fortuna_state *st, const unsigned char *data,
size_t len)
{
unsigned char lenbuf[2];
SHA256_CTX *pool;
/* Track how many bytes have been added to pool 0. */
if (st->pool_index == 0 && st->pool0_bytes < MIN_POOL_LEN)
st->pool0_bytes += len;
/* Hash events into successive accumulator pools. */
pool = &st->pool[st->pool_index];
st->pool_index = (st->pool_index + 1) % NUM_POOLS;
/*
* Fortuna specifies that events are encoded with a source identifier byte,
* a length byte, and the event data itself. We do not have source
* identifiers and they're not really important, so just encode the
* length in two bytes instead.
*/
store_16_be(len, lenbuf);
shad256_update(pool, lenbuf, 2);
shad256_update(pool, data, len);
}
/* Limit dependencies for test program. */
#ifndef TEST
/* Return true if RESEED_INTERVAL microseconds have passed since the last
* reseed. */
static krb5_boolean
enough_time_passed(struct fortuna_state *st)
{
struct timeval tv, *last = &st->last_reseed_time;
krb5_boolean ok = FALSE;
gettimeofday(&tv, NULL);
/* Check how much time has passed. */
if (tv.tv_sec > last->tv_sec + 1)
ok = TRUE;
else if (tv.tv_sec == last->tv_sec + 1) {
if (1000000 + tv.tv_usec - last->tv_usec >= RESEED_INTERVAL)
ok = TRUE;
} else if (tv.tv_usec - last->tv_usec >= RESEED_INTERVAL)
ok = TRUE;
/* Update last_reseed_time if we're returning success. */
if (ok)
memcpy(last, &tv, sizeof(tv));
return ok;
}
static void
accumulator_output(struct fortuna_state *st, unsigned char *dst, size_t len)
{
/* Reseed the generator with data from pools if we have accumulated enough
* data and enough time has passed since the last accumulator reseed. */
if (st->pool0_bytes >= MIN_POOL_LEN && enough_time_passed(st))
accumulator_reseed(st);
generator_output(st, dst, len);
}
static k5_mutex_t fortuna_lock = K5_MUTEX_PARTIAL_INITIALIZER;
static struct fortuna_state main_state;
#ifdef _WIN32
static DWORD last_pid;
#else
static pid_t last_pid;
#endif
static krb5_boolean have_entropy = FALSE;
int
k5_prng_init(void)
{
krb5_error_code ret = 0;
unsigned char osbuf[64];
ret = k5_mutex_finish_init(&fortuna_lock);
if (ret)
return ret;
init_state(&main_state);
#ifdef _WIN32
last_pid = GetCurrentProcessId();
#else
last_pid = getpid();
#endif
if (k5_get_os_entropy(osbuf, sizeof(osbuf), 0)) {
generator_reseed(&main_state, osbuf, sizeof(osbuf));
have_entropy = TRUE;
}
return 0;
}
void
k5_prng_cleanup(void)
{
have_entropy = FALSE;
zap(&main_state, sizeof(main_state));
k5_mutex_destroy(&fortuna_lock);
}
krb5_error_code KRB5_CALLCONV
krb5_c_random_add_entropy(krb5_context context, unsigned int randsource,
const krb5_data *indata)
{
krb5_error_code ret;
ret = krb5int_crypto_init();
if (ret)
return ret;
k5_mutex_lock(&fortuna_lock);
if (randsource == KRB5_C_RANDSOURCE_OSRAND ||
randsource == KRB5_C_RANDSOURCE_TRUSTEDPARTY) {
/* These sources contain enough entropy that we should use them
* immediately, so that they benefit the next request. */
generator_reseed(&main_state, (unsigned char *)indata->data,
indata->length);
have_entropy = TRUE;
} else {
/* Other sources should just go into the pools and be used according to
* the accumulator logic. */
accumulator_add_event(&main_state, (unsigned char *)indata->data,
indata->length);
}
k5_mutex_unlock(&fortuna_lock);
return 0;
}
krb5_error_code KRB5_CALLCONV
krb5_c_random_make_octets(krb5_context context, krb5_data *outdata)
{
#ifdef _WIN32
DWORD pid = GetCurrentProcessId();
#else
pid_t pid = getpid();
#endif
unsigned char pidbuf[4];
k5_mutex_lock(&fortuna_lock);
if (!have_entropy) {
k5_mutex_unlock(&fortuna_lock);
if (context != NULL) {
k5_set_error(&context->err, KRB5_CRYPTO_INTERNAL,
_("Random number generator could not be seeded"));
}
return KRB5_CRYPTO_INTERNAL;
}
if (pid != last_pid) {
/* We forked; make sure child's PRNG stream differs from parent's. */
store_32_be(pid, pidbuf);
generator_reseed(&main_state, pidbuf, 4);
last_pid = pid;
}
accumulator_output(&main_state, (unsigned char *)outdata->data,
outdata->length);
k5_mutex_unlock(&fortuna_lock);
return 0;
}
krb5_error_code KRB5_CALLCONV
krb5_c_random_os_entropy(krb5_context context, int strong, int *success)
{
krb5_error_code ret;
krb5_data data;
uint8_t buf[64];
int status = 0;
if (!k5_get_os_entropy(buf, sizeof(buf), strong))
goto done;
data = make_data(buf, sizeof(buf));
ret = krb5_c_random_add_entropy(context, KRB5_C_RANDSOURCE_OSRAND, &data);
if (ret)
goto done;
status = 1;
done:
if (success != NULL)
*success = status;
return 0;
}
#endif /* not TEST */