Differential D20313 Diff 58377 sys/dev/random/fortuna.c

Changeset View

Standalone View

sys/dev/random/fortuna.c

Show First 20 Lines • Show All 55 Lines • ▼ Show 20 Lines
#include <stdio.h>		#include <stdio.h>
#include <stdlib.h>		#include <stdlib.h>
#include <string.h>		#include <string.h>
#include <threads.h>		#include <threads.h>

#include "unit_test.h"		#include "unit_test.h"
#endif /* _KERNEL */		#endif /* _KERNEL */

		#include <crypto/chacha20/chacha.h>
#include <crypto/rijndael/rijndael-api-fst.h>		#include <crypto/rijndael/rijndael-api-fst.h>
#include <crypto/sha2/sha256.h>		#include <crypto/sha2/sha256.h>

#include <dev/random/hash.h>		#include <dev/random/hash.h>
#include <dev/random/randomdev.h>		#include <dev/random/randomdev.h>
#ifdef _KERNEL		#ifdef _KERNEL
#include <dev/random/random_harvestq.h>		#include <dev/random/random_harvestq.h>
#endif		#endif
#include <dev/random/uint128.h>		#include <dev/random/uint128.h>
#include <dev/random/fortuna.h>		#include <dev/random/fortuna.h>

/* Defined in FS&K */		/* Defined in FS&K */
#define RANDOM_FORTUNA_NPOOLS 32 /* The number of accumulation pools */		#define RANDOM_FORTUNA_NPOOLS 32 /* The number of accumulation pools */
#define RANDOM_FORTUNA_DEFPOOLSIZE 64 /* The default pool size/length for a (re)seed */		#define RANDOM_FORTUNA_DEFPOOLSIZE 64 /* The default pool size/length for a (re)seed */
#define RANDOM_FORTUNA_MAX_READ (1 << 20) /* Max bytes in a single read */		#define RANDOM_FORTUNA_MAX_READ (1 << 20) /* Max bytes from AES before rekeying */
		#define RANDOM_FORTUNA_BLOCKS_PER_KEY (1 << 16) /* Max blocks from AES before rekeying */
		CTASSERT(RANDOM_FORTUNA_BLOCKS_PER_KEY * RANDOM_BLOCKSIZE ==
		RANDOM_FORTUNA_MAX_READ);

/*		/*
* The allowable range of RANDOM_FORTUNA_DEFPOOLSIZE. The default value is above.		* The allowable range of RANDOM_FORTUNA_DEFPOOLSIZE. The default value is above.
* Making RANDOM_FORTUNA_DEFPOOLSIZE too large will mean a long time between reseeds,		* Making RANDOM_FORTUNA_DEFPOOLSIZE too large will mean a long time between reseeds,
* and too small may compromise initial security but get faster reseeds.		* and too small may compromise initial security but get faster reseeds.
*/		*/
#define RANDOM_FORTUNA_MINPOOLSIZE 16		#define RANDOM_FORTUNA_MINPOOLSIZE 16
#define RANDOM_FORTUNA_MAXPOOLSIZE INT_MAX		#define RANDOM_FORTUNA_MAXPOOLSIZE INT_MAX
Show All 28 Lines
#ifdef _KERNEL		#ifdef _KERNEL
/* For use when 'pacing' the reseeds */		/* For use when 'pacing' the reseeds */
sbintime_t fs_lasttime;		sbintime_t fs_lasttime;
#endif		#endif
/* Reseed lock */		/* Reseed lock */
mtx_t fs_mtx;		mtx_t fs_mtx;
} fortuna_state;		} fortuna_state;

		/*
		* Experimental concurrent reads feature. For now, disabled by default. But
		* we may enable it in the future.
		*
		* The benefit is improved concurrency in Fortuna. That is reflected in two
		* related aspects:
		*
		* 1. Concurrent devrandom readers can achieve similar throughput to a single
		* reader thread.
		*
		* 2. The rand_harvestq process spends much less time spinning when one or more
		* readers is processing a large request. Partially this is due to
		* rand_harvestq / ra_event_processor design, which only passes one event at
		* a time to the underlying algorithm. Each time, Fortuna must take its
		* global state mutex, potentially blocking on a reader. Our adaptive
		* mutexes assume that a lock holder currently on CPU will release the lock
		* quickly, and spin if the owning thread is currently running.
		*/
		static bool fortuna_concurrent_read __read_frequently = false;

#ifdef _KERNEL		#ifdef _KERNEL
static struct sysctl_ctx_list random_clist;		static struct sysctl_ctx_list random_clist;
RANDOM_CHECK_UINT(fs_minpoolsize, RANDOM_FORTUNA_MINPOOLSIZE, RANDOM_FORTUNA_MAXPOOLSIZE);		RANDOM_CHECK_UINT(fs_minpoolsize, RANDOM_FORTUNA_MINPOOLSIZE, RANDOM_FORTUNA_MAXPOOLSIZE);
#else		#else
static uint8_t zero_region[RANDOM_ZERO_BLOCKSIZE];		static uint8_t zero_region[RANDOM_ZERO_BLOCKSIZE];
#endif		#endif

static void random_fortuna_pre_read(void);		static void random_fortuna_pre_read(void);
Show All 40 Lines	random_fortuna_o = SYSCTL_ADD_NODE(&random_clist,
"Fortuna Parameters");		"Fortuna Parameters");
SYSCTL_ADD_PROC(&random_clist,		SYSCTL_ADD_PROC(&random_clist,
SYSCTL_CHILDREN(random_fortuna_o), OID_AUTO,		SYSCTL_CHILDREN(random_fortuna_o), OID_AUTO,
"minpoolsize", CTLTYPE_UINT \| CTLFLAG_RWTUN,		"minpoolsize", CTLTYPE_UINT \| CTLFLAG_RWTUN,
&fortuna_state.fs_minpoolsize, RANDOM_FORTUNA_DEFPOOLSIZE,		&fortuna_state.fs_minpoolsize, RANDOM_FORTUNA_DEFPOOLSIZE,
random_check_uint_fs_minpoolsize, "IU",		random_check_uint_fs_minpoolsize, "IU",
"Minimum pool size necessary to cause a reseed");		"Minimum pool size necessary to cause a reseed");
KASSERT(fortuna_state.fs_minpoolsize > 0, ("random: Fortuna threshold must be > 0 at startup"));		KASSERT(fortuna_state.fs_minpoolsize > 0, ("random: Fortuna threshold must be > 0 at startup"));

		SYSCTL_ADD_BOOL(&random_clist, SYSCTL_CHILDREN(random_fortuna_o),
		OID_AUTO, "concurrent_read", CTLFLAG_RDTUN,
		&fortuna_concurrent_read, 0, "If non-zero, enable EXPERIMENTAL "
		"feature to improve concurrent Fortuna performance.");
#endif		#endif

/*-		/*-
* FS&K - InitializePRNG()		* FS&K - InitializePRNG()
* - P_i = \epsilon		* - P_i = \epsilon
* - ReseedCNT = 0		* - ReseedCNT = 0
*/		*/
for (i = 0; i < RANDOM_FORTUNA_NPOOLS; i++) {		for (i = 0; i < RANDOM_FORTUNA_NPOOLS; i++) {
▲ Show 20 Lines • Show All 114 Lines • ▼ Show 20 Lines	random_fortuna_reseed_internal(uint32_t *entropy_data, u_int blockcount)
explicit_bzero(hash, sizeof(hash));		explicit_bzero(hash, sizeof(hash));
/* Unblock the device if this is the first time we are reseeding. */		/* Unblock the device if this is the first time we are reseeding. */
if (uint128_is_zero(fortuna_state.fs_counter))		if (uint128_is_zero(fortuna_state.fs_counter))
randomdev_unblock();		randomdev_unblock();
uint128_increment(&fortuna_state.fs_counter);		uint128_increment(&fortuna_state.fs_counter);
}		}

/*-		/*-
* FS&K - PseudoRandomData()
*
* If Chacha20 is used, output size is unrestricted. If AES-CTR is used,
* output size MUST be <= 1MB and a multiple of RANDOM_BLOCKSIZE. The
* reasoning for this is discussed in FS&K 9.4; the significant distinction
* between the two ciphers is that AES has a block size of 128 bits while
* Chacha has a block size of 512 bits.
*/
static __inline void
random_fortuna_genrandom(uint8_t *buf, size_t bytecount)
{
uint8_t newkey[RANDOM_KEYSIZE];

RANDOM_RESEED_ASSERT_LOCK_OWNED();

/*-
* FS&K - assert(n < 2^20 (== 1 MB)) when 128-bit block cipher is used
* - r = first-n-bytes(GenerateBlocks(ceil(n/16)))
* - K = GenerateBlocks(2)
*/
KASSERT(random_chachamode \|\| bytecount <= RANDOM_FORTUNA_MAX_READ,
("%s: invalid large read request: %zu bytes", __func__,
bytecount));

/*
* This is where FS&K would invoke GenerateBlocks(). GenerateBlocks()
* doesn't make a lot of sense or have much value if we use bytecount
* for the API (which is useful for ciphers that do not require
* block-sized output, like Chacha20).
*
* Just invoke our PRF abstraction directly, which is responsible for
* updating fs_counter ('C').
*/
randomdev_keystream(&fortuna_state.fs_key, &fortuna_state.fs_counter,
buf, bytecount);
randomdev_keystream(&fortuna_state.fs_key, &fortuna_state.fs_counter,
newkey, sizeof(newkey));
randomdev_encrypt_init(&fortuna_state.fs_key, newkey);
explicit_bzero(newkey, sizeof(newkey));
}

/*-
* FS&K - RandomData() (Part 1)		* FS&K - RandomData() (Part 1)
* Used to return processed entropy from the PRNG. There is a pre_read		* Used to return processed entropy from the PRNG. There is a pre_read
* required to be present (but it can be a stub) in order to allow		* required to be present (but it can be a stub) in order to allow
* specific actions at the begin of the read.		* specific actions at the begin of the read.
*/		*/
void		void
random_fortuna_pre_read(void)		random_fortuna_pre_read(void)
{		{
▲ Show 20 Lines • Show All 69 Lines • ▼ Show 20 Lines	#endif
random_fortuna_reseed_internal(s, i);		random_fortuna_reseed_internal(s, i);
RANDOM_RESEED_UNLOCK();		RANDOM_RESEED_UNLOCK();

/* Clean up and secure */		/* Clean up and secure */
explicit_bzero(s, sizeof(s));		explicit_bzero(s, sizeof(s));
explicit_bzero(temp, sizeof(temp));		explicit_bzero(temp, sizeof(temp));
}		}

/*-		/*
* FS&K - RandomData() (Part 2)		* This is basically GenerateBlocks() from FS&K.
* Main read from Fortuna, continued. May be called multiple times after
* the random_fortuna_pre_read() above.
*		*
* The supplied buf MAY not be a multiple of RANDOM_BLOCKSIZE in size; it is		* It differs in two ways:
* the responsibility of the algorithm to accommodate partial block reads, if a		*
* block output mode is used.		* 1. Chacha20 is tolerant of non-block-multiple request sizes, so we do not
		* need to handle any remainder bytes specially and can just pass the length
		* directly to the PRF construction; and
		*
		* 2. Chacha20 is a 512-bit block size cipher (whereas AES has 128-bit block
		* size, regardless of key size). This means Chacha does not require re-keying
		* every 1MiB. This is implied by the math in FS&K 9.4 and mentioned
		* explicitly in the conclusion, "If we had a block cipher with a 256-bit [or
		* greater] block size, then the collisions would not have been an issue at
		* all" (p. 144).
		*
		* 3. In conventional ("locked") mode, we produce a maximum of PAGE_SIZE output
		* at a time before dropping the lock, to not bully the lock especially. This
		* has been the status quo since 2015 (r284959).
		*
		* The upstream caller random_fortuna_read is responsible for zeroing out
		* sensitive buffers provided as parameters to this routine.
*/		*/
void		enum {
random_fortuna_read(uint8_t *buf, size_t bytecount)		FORTUNA_UNLOCKED = false,
		FORTUNA_LOCKED = true
		};
		static void
		random_fortuna_genbytes(uint8_t *buf, size_t bytecount,
		uint8_t newkey[static RANDOM_KEYSIZE], uint128_t *p_counter,
		union randomdev_key *p_key, bool locked)
{		{
uint8_t remainder_buf[RANDOM_BLOCKSIZE];		uint8_t remainder_buf[RANDOM_BLOCKSIZE];
size_t read_directly_len, read_chunk;		size_t chunk_size;

		if (locked)
		RANDOM_RESEED_ASSERT_LOCK_OWNED();
		else
		RANDOM_RESEED_ASSERT_LOCK_NOT_OWNED();

/*		/*
* The underlying AES generator expects multiples of RANDOM_BLOCKSIZE.		* Easy case: don't have to worry about bullying the global mutex,
		* don't have to worry about rekeying Chacha; API is byte-oriented.
*/		*/
if (random_chachamode)		if (!locked && random_chachamode) {
read_directly_len = bytecount;		randomdev_keystream(p_key, p_counter, buf, bytecount);
else		return;
read_directly_len = rounddown(bytecount, RANDOM_BLOCKSIZE);		}

RANDOM_RESEED_LOCK();		if (locked) {
KASSERT(!uint128_is_zero(fortuna_state.fs_counter), ("FS&K: C != 0"));

while (read_directly_len > 0) {
/*		/*
		* While holding the global lock, limit PRF generation to
		* mitigate, but not eliminate, bullying symptoms.
		*/
		chunk_size = PAGE_SIZE;
		} else {
		/*
* 128-bit block ciphers like AES must be re-keyed at 1MB		* 128-bit block ciphers like AES must be re-keyed at 1MB
* intervals to avoid unacceptable statistical differentiation		* intervals to avoid unacceptable statistical differentiation
* from true random data.		* from true random data (FS&K 9.4, p. 143-144).
		*/
		MPASS(!random_chachamode);
		chunk_size = RANDOM_FORTUNA_MAX_READ;
		}

		chunk_size = MIN(bytecount, chunk_size);
		if (!random_chachamode)
		chunk_size = rounddown(chunk_size, RANDOM_BLOCKSIZE);

		while (bytecount >= chunk_size) {
		randomdev_keystream(p_key, p_counter, buf, chunk_size);
		delphijUnsubmitted Not Done Inline Actions The mutex would be held for too long for huge block (it seems that we all missed this in D20312), and it shouldn't because it would enable userland to effectively DoS the kernel because the mutexes would spin waiting for something else that is computational intensive. The synchronization model must be revisited here. I think in order to make this work the code needs to be refactored to something more MP friendly, e.g. fortuna_state should be per-CPU, and the read be done in critical sections. delphij: The mutex would be held for too long for huge block (it seems that we all missed this in…
		cemAuthorUnsubmitted Done Inline Actions I noticed and fixed this in D20312, actually. In this revision, please see line 477 above (`if locked ⇒ chunk_size = PAGE_SIZE;`) and corresponding comment. The user can already DoS the kernel (although less severely) today, due to PAGE_SIZE generation under lock. There's no good way to fix this without the exact change in this revision — moving PRF generation out from under the mutex. This change does make the code substantially more MP friendly, please see the proposed commit message. cem: I noticed and fixed this in D20312, actually. In this revision, please see line 477 above (`if…

		buf += chunk_size;
		bytecount -= chunk_size;

		/* We have to rekey if there is any data remaining to be
		* generated, in two scenarios:
*		*
* 512-bit block ciphers like Chacha20 do not have this		* locked: we need to rekey before we unlock and release the
* problem. (FS&K 9.4)		* global state to another consumer; or
		*
		* unlocked: we need to rekey because we're in AES mode and are
		* required to rekey at chunk_size==1MB. But we do not need to
		* rekey during the last trailing <1MB chunk.
*/		*/
if (random_chachamode)		if (bytecount > 0) {
read_chunk = read_directly_len;		if (locked \|\| chunk_size == RANDOM_FORTUNA_MAX_READ) {
else		randomdev_keystream(p_key, p_counter, newkey,
read_chunk = MIN(read_directly_len,		RANDOM_KEYSIZE);
RANDOM_FORTUNA_MAX_READ);		randomdev_encrypt_init(p_key, newkey);
		}

/*		/*
* For now, we hold the global Fortuna mutex, so yield		* If we're holding the global lock, yield it briefly
* periodically to provide vague availability to other lock		* now.
* users. PAGE_SIZE is chosen to match existing behavior.
*/		*/
read_chunk = MIN(read_chunk, PAGE_SIZE);		if (locked) {

random_fortuna_genrandom(buf, read_chunk);
buf += read_chunk;
read_directly_len -= read_chunk;
bytecount -= read_chunk;

/* Perform the actual yield. */
if (read_directly_len != 0) {
RANDOM_RESEED_UNLOCK();		RANDOM_RESEED_UNLOCK();
DELAY(1);		DELAY(1);
RANDOM_RESEED_LOCK();		RANDOM_RESEED_LOCK();
}		}

		/*
		* At the trailing end, scale down chunk_size from 1MB or
		* PAGE_SIZE to all remaining full blocks (AES) or all
		* remaining bytes (Chacha).
		*/
		if (bytecount < chunk_size) {
		if (random_chachamode)
		chunk_size = bytecount;
		else if (bytecount >= RANDOM_BLOCKSIZE)
		chunk_size = rounddown(bytecount,
		RANDOM_BLOCKSIZE);
		else
		break;
}		}
		}
		}

		/*
		* Generate any partial AES block remaining into a temporary buffer and
		* copy the desired substring out.
		*/
if (bytecount > 0) {		if (bytecount > 0) {
random_fortuna_genrandom(remainder_buf, sizeof(remainder_buf));		MPASS(!random_chachamode);

		randomdev_keystream(p_key, p_counter, remainder_buf,
		sizeof(remainder_buf));
memcpy(buf, remainder_buf, bytecount);		memcpy(buf, remainder_buf, bytecount);
explicit_bzero(remainder_buf, sizeof(remainder_buf));		explicit_bzero(remainder_buf, sizeof(remainder_buf));
}		}
		}


		/*
		* Handle only "concurrency-enabled" Fortuna reads to simplify logic.
		*
		* Caller (random_fortuna_read) is responsible for zeroing out sensitive
		* buffers provided as parameters to this routine.
		*/
		static void
		random_fortuna_read_concurrent(uint8_t *buf, size_t bytecount,
		uint8_t newkey[static RANDOM_KEYSIZE])
		{
		union randomdev_key key_copy;
		uint128_t counter_copy;
		size_t blockcount;

		MPASS(fortuna_concurrent_read);

		/*
		* Compute number of blocks required for the PRF request ('delta C').
		* We will step the global counter 'C' by this number under lock, and
		* then actually consume the counter values outside the lock.
		*
		* This ensures that contemporaneous but independent requests for
		* randomness receive distinct 'C' values and thus independent PRF
		* results.
		*/
		if (random_chachamode) {
		blockcount = howmany(bytecount, CHACHA_BLOCKLEN);
		} else {
		blockcount = howmany(bytecount, RANDOM_BLOCKSIZE);

		/*
		* Need to account for the additional blocks generated by
		* rekeying when updating the global fs_counter.
		*/
		blockcount += RANDOM_KEYS_PER_BLOCK *
		(blockcount / RANDOM_FORTUNA_BLOCKS_PER_KEY);
		}

		RANDOM_RESEED_LOCK();
		KASSERT(!uint128_is_zero(fortuna_state.fs_counter), ("FS&K: C != 0"));
		/*
		* Technically, we only need mutual exclusion to update shared state
		* appropriately. Nothing about updating the shared internal state
		* requires that we perform (most) expensive cryptographic keystream
		* generation under lock. (We still need to generate 256 bits of
		* keystream to re-key between consumers.)
		*
		* Save the original counter and key values that will be used as the
		* PRF for this particular consumer.
		*/
		memcpy(&counter_copy, &fortuna_state.fs_counter, sizeof(counter_copy));
		memcpy(&key_copy, &fortuna_state.fs_key, sizeof(key_copy));

		/*
		* Step the counter as if we had generated 'bytecount' blocks for this
		* consumer. I.e., ensure that the next consumer gets an independent
		* range of counter values once we drop the global lock.
		*/
		uint128_add(&fortuna_state.fs_counter, blockcount);

		/*
		* We still need to Rekey the global 'K' between independent calls;
		* this is no different from conventional Fortuna. Note that
		* 'randomdev_keystream()' will step the fs_counter 'C' appropriately
		* for the blocks needed for the 'newkey'.
		*
		* (This is part of PseudoRandomData() in FS&K, 9.4.4.)
		*/
		randomdev_keystream(&fortuna_state.fs_key, &fortuna_state.fs_counter,
		newkey, RANDOM_KEYSIZE);
		randomdev_encrypt_init(&fortuna_state.fs_key, newkey);

		/*
		* We have everything we need to generate a unique PRF for this
		* consumer without touching global state.
		*/
RANDOM_RESEED_UNLOCK();		RANDOM_RESEED_UNLOCK();

		random_fortuna_genbytes(buf, bytecount, newkey, &counter_copy,
		&key_copy, FORTUNA_UNLOCKED);
		RANDOM_RESEED_ASSERT_LOCK_NOT_OWNED();

		explicit_bzero(&counter_copy, sizeof(counter_copy));
		explicit_bzero(&key_copy, sizeof(key_copy));
		}

		/*-
		* FS&K - RandomData() (Part 2)
		* Main read from Fortuna, continued. May be called multiple times after
		* the random_fortuna_pre_read() above.
		*
		* The supplied buf MAY not be a multiple of RANDOM_BLOCKSIZE in size; it is
		* the responsibility of the algorithm to accommodate partial block reads, if a
		* block output mode is used.
		*/
		void
		random_fortuna_read(uint8_t *buf, size_t bytecount)
		{
		uint8_t newkey[RANDOM_KEYSIZE];

		if (fortuna_concurrent_read) {
		random_fortuna_read_concurrent(buf, bytecount, newkey);
		goto out;
		}

		RANDOM_RESEED_LOCK();
		KASSERT(!uint128_is_zero(fortuna_state.fs_counter), ("FS&K: C != 0"));

		random_fortuna_genbytes(buf, bytecount, newkey,
		&fortuna_state.fs_counter, &fortuna_state.fs_key, FORTUNA_LOCKED);
		RANDOM_RESEED_ASSERT_LOCK_OWNED();

		randomdev_keystream(&fortuna_state.fs_key, &fortuna_state.fs_counter,
		newkey, RANDOM_KEYSIZE);
		randomdev_encrypt_init(&fortuna_state.fs_key, newkey);

		RANDOM_RESEED_UNLOCK();
		out:
		explicit_bzero(newkey, sizeof(newkey));
}		}

#ifdef _KERNEL		#ifdef _KERNEL
static bool block_seeded_status = false;		static bool block_seeded_status = false;
SYSCTL_BOOL(_kern_random, OID_AUTO, block_seeded_status, CTLFLAG_RWTUN,		SYSCTL_BOOL(_kern_random, OID_AUTO, block_seeded_status, CTLFLAG_RWTUN,
&block_seeded_status, 0,		&block_seeded_status, 0,
"If non-zero, pretend Fortuna is in an unseeded state. By setting "		"If non-zero, pretend Fortuna is in an unseeded state. By setting "
"this as a tunable, boot can be tested as if the random device is "		"this as a tunable, boot can be tested as if the random device is "
Show All 29 Lines