From 6e954a6e42bd37911605d3b4cd22e4d1d23c2372 Mon Sep 17 00:00:00 2001 From: Jens Wiklander Date: Thu, 14 Jun 2018 11:12:00 +0200 Subject: core: add new RNG implementation Adds a new cryptographically secure pseudo random number generator known as Fortuna. The implementation is based on the description in [0]. This implementation replaces the implementation in LTC which was used until now. Gathering of entropy has been refined with crypto_rng_add_event() to better match how entropy is added to Fortuna. A enum crypto_rng_src identifies the source of the event. The source also controls how the event is added. There are two options available, queue it in a circular buffer for later processing or adding it directly to a pool. The former option is suitable when being called from an interrupt handler or some other place where RPC to normal world is forbidden. plat_prng_add_jitter_entropy_norpc() is removed and plat_prng_add_jitter_entropy() is updated to use this new entropy source scheme. The configuration of LTC is simplified by this, now PRNG is always drawn via prng_mpa_desc. plat_rng_init() takes care of initializing the PRNG in order to allow platforms to override or enhance the Fortuna integration. [0] Link:https://www.schneier.com/academic/paperfiles/fortuna.pdf Reviewed-by: Jerome Forissier Signed-off-by: Jens Wiklander --- core/crypto/rng_fortuna.c | 531 ++++++++++++++++++++++++++++++++++++++++++++++ core/crypto/rng_hw.c | 26 +++ core/crypto/sub.mk | 8 +- 3 files changed, 564 insertions(+), 1 deletion(-) create mode 100644 core/crypto/rng_fortuna.c create mode 100644 core/crypto/rng_hw.c (limited to 'core/crypto') diff --git a/core/crypto/rng_fortuna.c b/core/crypto/rng_fortuna.c new file mode 100644 index 00000000..b9ce2d22 --- /dev/null +++ b/core/crypto/rng_fortuna.c @@ -0,0 +1,531 @@ +// 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 +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#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, HASH_ALGO); +} + +static TEE_Result hash_update(void *ctx, const void *data, size_t dlen) +{ + return crypto_hash_update(ctx, HASH_ALGO, data, dlen); +} + +static TEE_Result hash_final(void *ctx, uint8_t digest[KEY_SIZE]) +{ + return crypto_hash_final(ctx, HASH_ALGO, 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, CIPHER_ALGO, 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], HASH_ALGO); + state.pool_ctx[n] = NULL; + } + crypto_hash_free_ctx(state.reseed_ctx, HASH_ALGO); + state.reseed_ctx = NULL; + crypto_cipher_free_ctx(state.ctx, CIPHER_ALGO); + 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], HASH_ALGO); + 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, CIPHER_ALGO, + 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, CIPHER_ALGO); + res = crypto_cipher_init(state.ctx, CIPHER_ALGO, 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, CIPHER_ALGO); + 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; + } +} diff --git a/core/crypto/rng_hw.c b/core/crypto/rng_hw.c new file mode 100644 index 00000000..577eacaa --- /dev/null +++ b/core/crypto/rng_hw.c @@ -0,0 +1,26 @@ +// SPDX-License-Identifier: BSD-2-Clause +/* Copyright (c) 2018, Linaro Limited */ + +#include +#include +#include +#include + +TEE_Result __weak crypto_rng_init(const void *data __unused, + size_t dlen __unused) +{ + return TEE_SUCCESS; +} + +void __weak crypto_rng_add_event(enum crypto_rng_src sid __unused, + unsigned int *pnum __unused, + const void *data __unused, + size_t dlen __unused) +{ +} + +TEE_Result __weak crypto_rng_read(void *buf, size_t blen) +{ + return get_rng_array(buf, blen); +} + diff --git a/core/crypto/sub.mk b/core/crypto/sub.mk index f21eface..bb16a3eb 100644 --- a/core/crypto/sub.mk +++ b/core/crypto/sub.mk @@ -6,4 +6,10 @@ srcs-y += aes-gcm-ghash-tbl.c else srcs-y += aes-gcm-ghash.c endif -srcs-$(CFG_WITH_USER_TA) += signed_hdr.c \ No newline at end of file +srcs-$(CFG_WITH_USER_TA) += signed_hdr.c + +ifeq ($(CFG_WITH_SOFTWARE_PRNG),y) +srcs-y += rng_fortuna.c +else +srcs-y += rng_hw.c +endif -- cgit v1.2.3