Index: sys/dev/random/fortuna.c =================================================================== --- sys/dev/random/fortuna.c +++ sys/dev/random/fortuna.c @@ -61,6 +61,7 @@ #include "unit_test.h" #endif /* _KERNEL */ +#include #include #include @@ -75,7 +76,10 @@ /* Defined in FS&K */ #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_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. @@ -120,6 +124,26 @@ mtx_t fs_mtx; } 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 = false; + #ifdef _KERNEL static struct sysctl_ctx_list random_clist; RANDOM_CHECK_UINT(fs_minpoolsize, RANDOM_FORTUNA_MINPOOLSIZE, RANDOM_FORTUNA_MAXPOOLSIZE); @@ -176,6 +200,11 @@ random_check_uint_fs_minpoolsize, "IU", "Minimum pool size necessary to cause a reseed"); 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 /*- @@ -305,48 +334,6 @@ 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 256 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) * Used to return processed entropy from the PRNG. There is a pre_read @@ -445,47 +432,127 @@ void random_fortuna_read(uint8_t *buf, size_t bytecount) { - uint8_t remainder_buf[RANDOM_BLOCKSIZE]; - size_t read_directly_len, read_chunk; - - /* - * The underlying AES generator expects multiples of RANDOM_BLOCKSIZE. - */ - if (random_chachamode) - read_directly_len = bytecount; - else + uint8_t remainder_buf[RANDOM_BLOCKSIZE], newkey[RANDOM_KEYSIZE]; + size_t read_directly_len, read_chunk, blockcount; + uint128_t counter_copy, *p_counter; + union randomdev_key key_copy, *p_key; + + if (random_chachamode) { + blockcount = howmany(bytecount, CHACHA_BLOCKLEN); + /* Unused; squash GCC maybe-uninitialized warning: */ + read_directly_len = 0; + } else { + /* + * The underlying AES generator expects multiples of + * RANDOM_BLOCKSIZE. + */ read_directly_len = rounddown(bytecount, RANDOM_BLOCKSIZE); + 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")); - while (read_directly_len > 0) { + if (fortuna_concurrent_read) { /* - * 128-bit block ciphers like AES must be re-keyed at 1MB - * intervals to avoid unacceptable statistical differentiation - * from true random data. + * Technically, we only need mutual exclusion to: + * 1. Step the counter by the number of output blocks, so that + * consumers get unique counter values, and + * 2. Rekey the shared key for forward secrecy. + * + * We can do either of those and drop the global mutex before + * we actually generate N bytes of output. * - * 256-bit block ciphers like Chacha20 do not have this - * problem. (FS&K 9.4) + * Save the original counter and key values for this 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: */ + uint128_add(&fortuna_state.fs_counter, blockcount); + + /* Rekey; this is part of PseudoRandomData() in FS&K, 9.4.4 */ + randomdev_keystream(&fortuna_state.fs_key, &fortuna_state.fs_counter, + newkey, sizeof(newkey)); + randomdev_encrypt_init(&fortuna_state.fs_key, newkey); + + p_counter = &counter_copy; + p_key = &key_copy; + + /* + * We have everything we need to generate a unique PRF for this + * consumer. */ - if (random_chachamode) - read_chunk = read_directly_len; - else + RANDOM_RESEED_UNLOCK(); + } else { + p_counter = &fortuna_state.fs_counter; + p_key = &fortuna_state.fs_key; + } + + /* + * The rest of this is basically GenerateBlocks() from FS&K. + * + * It differs in two ways: + * + * 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 256-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 block size, then the collisions would not have + * been an issue at all" (p. 144). + */ + if (random_chachamode) { + randomdev_keystream(p_key, p_counter, buf, bytecount); + } else { + while (read_directly_len > 0) { + /* + * 128-bit block ciphers like AES must be re-keyed at 1MB + * intervals to avoid unacceptable statistical differentiation + * from true random data (FS&K 9.4, p. 143-144). + */ read_chunk = MIN(read_directly_len, RANDOM_FORTUNA_MAX_READ); - random_fortuna_genrandom(buf, read_chunk); - buf += read_chunk; - read_directly_len -= read_chunk; - bytecount -= read_chunk; + randomdev_keystream(p_key, p_counter, buf, read_chunk); + + /* Rekey AES at 1MB intervals. */ + if (read_chunk == RANDOM_FORTUNA_MAX_READ && + bytecount > read_chunk) { + randomdev_keystream(p_key, p_counter, + newkey, sizeof(newkey)); + randomdev_encrypt_init(p_key, newkey); + } + + buf += read_chunk; + read_directly_len -= read_chunk; + bytecount -= read_chunk; + } + if (bytecount > 0) { + randomdev_keystream(p_key, p_counter, + remainder_buf, sizeof(remainder_buf)); + memcpy(buf, remainder_buf, bytecount); + explicit_bzero(remainder_buf, sizeof(remainder_buf)); + } } - if (bytecount > 0) { - random_fortuna_genrandom(remainder_buf, sizeof(remainder_buf)); - memcpy(buf, remainder_buf, bytecount); - explicit_bzero(remainder_buf, sizeof(remainder_buf)); + if (fortuna_concurrent_read) { + explicit_bzero(&counter_copy, sizeof(counter_copy)); + explicit_bzero(&key_copy, sizeof(key_copy)); + } else { + RANDOM_RESEED_UNLOCK(); } - RANDOM_RESEED_UNLOCK(); + explicit_bzero(newkey, sizeof(newkey)); } #ifdef _KERNEL Index: sys/dev/random/uint128.h =================================================================== --- sys/dev/random/uint128.h +++ sys/dev/random/uint128.h @@ -65,6 +65,21 @@ #endif } +static __inline void +uint128_add(uint128_t *big_uintp, uint64_t add) +{ +#ifdef USE_REAL_UINT128_T + (*big_uintp) += add; +#else + uint64_t word0p; + + word0p = big_uintp->u128t_word0 + add; + if (word0p < big_uintp->u128t_word0) + big_uintp->u128t_word1++; + big_uintp->u128t_word0 = word0p; +#endif +} + static __inline bool uint128_equals(uint128_t a, uint128_t b) {