core/crypto/rng_fortuna.c

// SPDX-License-Identifier: BSD-2-Clause
/* Copyright (c) 2018, Linaro Limited */

/*
 * This is an implementation of the Fortuna cryptographic PRNG as defined in
 * https://www.schneier.com/academic/paperfiles/fortuna.pdf
 * There's one small exception, see comment in restart_pool() below.
 */

#include <assert.h>
#include <crypto/crypto.h>
#include <kernel/mutex.h>
#include <kernel/refcount.h>
#include <kernel/spinlock.h>
#include <kernel/tee_time.h>
#include <string.h>
#include <types_ext.h>
#include <utee_defines.h>
#include <util.h>

#define NUM_POOLS		32
#define BLOCK_SIZE		16
#define KEY_SIZE		32
#define CIPHER_ALGO		TEE_ALG_AES_ECB_NOPAD
#define HASH_ALGO		TEE_ALG_SHA256
#define MIN_POOL_SIZE		64
#define MAX_EVENT_DATA_LEN	32U
#define RING_BUF_DATA_SIZE	4U

/*
 * struct fortuna_state - state of the Fortuna PRNG
 * @ctx:		Cipher context used to produce the random numbers
 * @counter:		Counter which is encrypted to produce the random numbers
 * @pool0_length:	Amount of data added to pool0
 * @pool_ctx:		One hash context for each pool
 * @reseed_ctx:		Hash context used while reseeding
 * @reseed_count:	Number of time we've reseeded the PRNG, used to tell
 *			which pools should be used in the reseed process
 * @next_reseed_time:	If we have a secure time, the earliest next time we
 *			may reseed
 *
 * To minimize the delay in crypto_rng_add_event() there's @pool_spin_lock
 * which protects everything needed by this function.
 *
 * @next_reseed_time is used as a rate limiter for reseeding.
 */
static struct fortuna_state {
	void *ctx;
	uint64_t counter[2];
	unsigned int pool0_length;
	void *pool_ctx[NUM_POOLS];
	void *reseed_ctx;
	uint32_t reseed_count;
#ifndef CFG_SECURE_TIME_SOURCE_REE
	TEE_Time next_reseed_time;
#endif
} state;

static struct mutex state_mu = MUTEX_INITIALIZER;

static struct {
	struct {
		uint8_t snum;
		uint8_t pnum;
		uint8_t dlen;
		uint8_t data[RING_BUF_DATA_SIZE];
	} elem[8];
	unsigned int begin;
	unsigned int end;
} ring_buffer;

unsigned int ring_buffer_spin_lock;

static void inc_counter(uint64_t counter[2])
{
	counter[0]++;
	if (!counter[0])
		counter[1]++;
}

static TEE_Result hash_init(void *ctx)
{
	return crypto_hash_init(ctx);
}

static TEE_Result hash_update(void *ctx, const void *data, size_t dlen)
{
	return crypto_hash_update(ctx, data, dlen);
}

static TEE_Result hash_final(void *ctx, uint8_t digest[KEY_SIZE])
{
	return crypto_hash_final(ctx, digest, KEY_SIZE);
}

static TEE_Result key_from_data(void *ctx, const void *data, size_t dlen,
				uint8_t key[KEY_SIZE])
{
	TEE_Result res;

	res = hash_init(ctx);
	if (res)
		return res;
	res = hash_update(ctx, data, dlen);
	if (res)
		return res;
	return hash_final(ctx, key);
}

static TEE_Result cipher_init(void *ctx, uint8_t key[KEY_SIZE])
{
	return crypto_cipher_init(ctx, TEE_MODE_ENCRYPT,
				  key, KEY_SIZE, NULL, 0, NULL, 0);
}

static void fortuna_done(void)
{
	size_t n;

	for (n = 0; n < NUM_POOLS; n++) {
		crypto_hash_free_ctx(state.pool_ctx[n]);
		state.pool_ctx[n] = NULL;
	}
	crypto_hash_free_ctx(state.reseed_ctx);
	state.reseed_ctx = NULL;
	crypto_cipher_free_ctx(state.ctx);
	state.ctx = NULL;
}

TEE_Result crypto_rng_init(const void *data, size_t dlen)
{
	TEE_Result res;
	uint8_t key[KEY_SIZE];
	void *ctx;
	size_t n;

	COMPILE_TIME_ASSERT(sizeof(state.counter) == BLOCK_SIZE);

	if (state.ctx)
		return TEE_ERROR_BAD_STATE;

	memset(&state, 0, sizeof(state));

	for (n = 0; n < NUM_POOLS; n++) {
		res = crypto_hash_alloc_ctx(&state.pool_ctx[n], HASH_ALGO);
		if (res)
			goto err;
		res = crypto_hash_init(state.pool_ctx[n]);
		if (res)
			goto err;
	}

	res = crypto_hash_alloc_ctx(&state.reseed_ctx, HASH_ALGO);
	if (res)
		goto err;

	res = key_from_data(state.reseed_ctx, data, dlen, key);
	if (res)
		return res;

	res = crypto_cipher_alloc_ctx(&ctx, CIPHER_ALGO);
	if (res)
		return res;
	res = cipher_init(ctx, key);
	if (res)
		return res;
	inc_counter(state.counter);
	state.ctx = ctx;
	return TEE_SUCCESS;
err:
	fortuna_done();
	return res;
}

static void push_ring_buffer(uint8_t snum, uint8_t pnum, const void *data,
			     size_t dlen)
{
	uint8_t dl = MIN(RING_BUF_DATA_SIZE, dlen);
	unsigned int next_begin;
	uint32_t old_itr_status;

	/* Spinlock to serialize writers */
	old_itr_status = cpu_spin_lock_xsave(&ring_buffer_spin_lock);

	next_begin = (ring_buffer.begin + 1) % ARRAY_SIZE(ring_buffer.elem);
	if (next_begin == atomic_load_uint(&ring_buffer.end))
		goto out; /* buffer is full */

	ring_buffer.elem[next_begin].snum = snum;
	ring_buffer.elem[next_begin].pnum = pnum;
	ring_buffer.elem[next_begin].dlen = dl;
	memcpy(ring_buffer.elem[next_begin].data, data, dl);

	atomic_store_uint(&ring_buffer.begin, next_begin);

out:
	cpu_spin_unlock_xrestore(&ring_buffer_spin_lock, old_itr_status);
}

static size_t pop_ring_buffer(uint8_t *snum, uint8_t *pnum,
			      uint8_t data[RING_BUF_DATA_SIZE])
{
	unsigned int next_end;
	size_t dlen;

	if (atomic_load_uint(&ring_buffer.begin) == ring_buffer.end)
		return 0;

	next_end = (ring_buffer.end + 1) % ARRAY_SIZE(ring_buffer.elem);

	*snum = ring_buffer.elem[ring_buffer.end].snum;
	*pnum = ring_buffer.elem[ring_buffer.end].pnum;
	dlen = MIN(ring_buffer.elem[ring_buffer.end].dlen, RING_BUF_DATA_SIZE);
	assert(ring_buffer.elem[ring_buffer.end].dlen == dlen);
	memcpy(data, ring_buffer.elem[ring_buffer.end].data, dlen);

	atomic_store_uint(&ring_buffer.end, next_end);

	return dlen;
}

static TEE_Result add_event(uint8_t snum, uint8_t pnum,
			    const void *data, size_t dlen)
{
	TEE_Result res;
	size_t dl = MIN(MAX_EVENT_DATA_LEN, dlen);
	uint8_t v[] = { snum, dl };

	if (pnum >= NUM_POOLS)
		return TEE_ERROR_BAD_PARAMETERS;

	res = hash_update(state.pool_ctx[pnum], v, sizeof(v));
	if (res)
		return res;
	res = hash_update(state.pool_ctx[pnum], data, dl);
	if (res)
		return res;
	if (!pnum) {
		unsigned int l;

		if (!ADD_OVERFLOW(state.pool0_length, dl, &l))
			state.pool0_length = l;
	}

	return TEE_SUCCESS;
}

static TEE_Result drain_ring_buffer(void)
{
	while (true) {
		TEE_Result res;
		uint8_t snum;
		uint8_t pnum;
		uint8_t data[RING_BUF_DATA_SIZE];
		size_t dlen;

		dlen = pop_ring_buffer(&snum, &pnum, data);
		if (!dlen)
			return TEE_SUCCESS;

		res = add_event(snum, pnum, data, dlen);
		if (res)
			return res;
	}
}

static unsigned int get_next_pnum(unsigned int *pnum)
{
	unsigned int nval;
	unsigned int oval = atomic_load_uint(pnum);

	while (true) {
		nval = (oval + 1) % NUM_POOLS;

		if (atomic_cas_uint(pnum, &oval, nval)) {
			/*
			 * *pnum is normally initialized to 0 and we'd like
			 * to start feeding pool number 0 as that's the
			 * most important one.
			 *
			 * If we where to take just *pnum and increase it
			 * later multiple updaters could end up with the
			 * same number.
			 *
			 * By increasing first we get the number unique for
			 * next update and by subtracting one (using
			 * modulus) we get the number for this update.
			 */
			return (nval + NUM_POOLS - 1) % NUM_POOLS;
		}
		/*
		 * At this point atomic_cas_uint() has updated oval to the
		 * current *pnum.
		 */
	}
}

void crypto_rng_add_event(enum crypto_rng_src sid, unsigned int *pnum,
			  const void *data, size_t dlen)
{
	unsigned int pn = get_next_pnum(pnum);
	uint8_t snum = sid >> 1;

	if (CRYPTO_RNG_SRC_IS_QUICK(sid)) {
		push_ring_buffer(snum, pn, data, dlen);
	} else {
		mutex_lock(&state_mu);
		add_event(snum, pn, data, dlen);
		drain_ring_buffer();
		mutex_unlock(&state_mu);
	}
}

/* GenerateBlocks */
static TEE_Result generate_blocks(void *block, size_t nblocks)
{
	uint8_t *b = block;
	size_t n;

	for (n = 0; n < nblocks; n++) {
		TEE_Result res = crypto_cipher_update(state.ctx,
						      TEE_MODE_ENCRYPT, false,
						      (void *)state.counter,
						      BLOCK_SIZE,
						      b + n * BLOCK_SIZE);

		/*
		 * Make sure to increase the counter before returning an
		 * eventual errors, we must never re-use the counter with
		 * the same key.
		 */
		inc_counter(state.counter);
		if (res)
			return res;
	}

	return TEE_SUCCESS;
}

/* GenerateRandomData */
static TEE_Result generate_random_data(void *buf, size_t blen)
{
	TEE_Result res;

	res = generate_blocks(buf, blen / BLOCK_SIZE);
	if (res)
		return res;
	if (blen % BLOCK_SIZE) {
		uint8_t block[BLOCK_SIZE];
		uint8_t *b = (uint8_t *)buf + ROUNDDOWN(blen, BLOCK_SIZE);

		res = generate_blocks(block, 1);
		if (res)
			return res;
		memcpy(b, block, blen % BLOCK_SIZE);
	}

	return TEE_SUCCESS;
}

#ifdef CFG_SECURE_TIME_SOURCE_REE
static bool reseed_rate_limiting(void)
{
	/*
	 * There's no point in checking REE time for reseed rate limiting,
	 * and also it makes it less complicated if we can avoid doing RPC
	 * here.
	 */
	return false;
}
#else
static bool reseed_rate_limiting(void)
{
	TEE_Result res;
	TEE_Time time;
	const TEE_Time time_100ms = { 0, 100 };

	res = tee_time_get_sys_time(&time);
	/*
	 * Failure to read time must result in allowing reseed or we could
	 * block reseeding forever.
	 */
	if (res)
		return false;

	if (TEE_TIME_LT(time, state.next_reseed_time))
		return true;

	/* Time to reseed, calculate next time reseed is OK */
	TEE_TIME_ADD(time, time_100ms, state.next_reseed_time);
	return false;
}
#endif

static TEE_Result restart_pool(void *pool_ctx, uint8_t pool_digest[KEY_SIZE])
{
	TEE_Result res = hash_final(pool_ctx, pool_digest);

	if (res)
		return res;

	res = hash_init(pool_ctx);
	if (res)
		return res;

	/*
	 * Restart the pool with the digest of the old pool. This is an
	 * extension to Fortuna. In the original Fortuna all pools was
	 * restarted from scratch. This extension is one more defense
	 * against spamming of the pools with known data which could lead
	 * to the spammer knowing the state of the pools.
	 *
	 * This extra precaution could be useful since OP-TEE sometimes
	 * have very few sources of good entropy and at the same time has
	 * sources that could quite easily be predicted by an attacker.
	 */
	return hash_update(pool_ctx, pool_digest, KEY_SIZE);
}

static bool reseed_from_pool(uint32_t reseed_count, size_t pool_num)
{
	/*
	 * Specification says: use pool if
	 * 2^pool_num is a divisor of reseed_count
	 *
	 * in order to avoid an expensive modulus operation we're
	 * optimizing this below.
	 */
	return !pool_num || !((reseed_count >> (pool_num - 1)) & 1);
}

static TEE_Result maybe_reseed(void)
{
	TEE_Result res;
	size_t n;
	uint8_t pool_digest[KEY_SIZE];

	if (state.pool0_length < MIN_POOL_SIZE)
		return TEE_SUCCESS;

	if (reseed_rate_limiting())
		return TEE_SUCCESS;

	state.reseed_count++;

	res = hash_init(state.reseed_ctx);
	if (res)
		return res;

	for (n = 0;
	     n < NUM_POOLS && reseed_from_pool(state.reseed_count, n); n++) {
		res = restart_pool(state.pool_ctx[n], pool_digest);
		if (res)
			return res;
		if (!n)
			state.pool0_length = 0;

		res = hash_update(state.reseed_ctx, pool_digest, KEY_SIZE);
		if (res)
			return res;
	}
	res = hash_final(state.reseed_ctx, pool_digest);
	if (res)
		return res;

	crypto_cipher_final(state.ctx);
	res = crypto_cipher_init(state.ctx, TEE_MODE_ENCRYPT,
				 pool_digest, KEY_SIZE, NULL, 0, NULL, 0);
	if (res)
		return res;
	inc_counter(state.counter);

	return TEE_SUCCESS;
}

static TEE_Result fortuna_read(void *buf, size_t blen)
{
	TEE_Result res;

	if (!state.ctx)
		return TEE_ERROR_BAD_STATE;

	mutex_lock(&state_mu);

	res = maybe_reseed();
	if (res)
		goto out;

	if (blen) {
		uint8_t new_key[KEY_SIZE];

		res = generate_random_data(buf, blen);
		if (res)
			goto out;

		res = generate_blocks(new_key, KEY_SIZE / BLOCK_SIZE);
		if (res)
			goto out;
		crypto_cipher_final(state.ctx);
		res = cipher_init(state.ctx, new_key);
		if (res)
			goto out;
	}

	res = drain_ring_buffer();
out:
	if (res)
		fortuna_done();
	mutex_unlock(&state_mu);

	return res;
}

TEE_Result crypto_rng_read(void *buf, size_t blen)
{
	size_t offs = 0;

	while (true) {
		TEE_Result res;
		size_t n;

		/* Draw at most 1 MiB of random on a single key */
		n = MIN(blen - offs, SIZE_1M);
		if (!n)
			return TEE_SUCCESS;
		res = fortuna_read((uint8_t *)buf + offs, n);
		if (res)
			return res;
		offs += n;
	}
}