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. @@ -306,45 +310,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. - */ -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 @@ -443,47 +408,106 @@ 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; + union randomdev_key key_copy; + + 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) { - /* - * 128-bit block ciphers like AES must be re-keyed at 1MB - * intervals to avoid unacceptable statistical differentiation - * from true random data. - * - * 256-bit block ciphers like Chacha20 do not have this - * problem. (FS&K 9.4) - */ - if (random_chachamode) - read_chunk = read_directly_len; - else + /* + * 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. + * + * 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); + + /* + * We have everything we need to generate a unique PRF for this + * consumer. + */ + RANDOM_RESEED_UNLOCK(); + + /* + * The rest of this is basically GenerateBlocks() from FS&K, although + * we now have a good 256-bit block PRF that doesn't need special + * handling for non-block multiple output sizes. + */ + if (random_chachamode) { + randomdev_keystream(&key_copy, &counter_copy, 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. + * + * 256-bit block ciphers like Chacha20 do not have this + * problem. (FS&K 9.4) + */ 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(&key_copy, &counter_copy, buf, read_chunk); + + /* Rekey AES at 1MB intervals. */ + if (read_chunk == RANDOM_FORTUNA_MAX_READ && + bytecount > read_chunk) { + randomdev_keystream(&key_copy, &counter_copy, + newkey, sizeof(newkey)); + randomdev_encrypt_init(&key_copy, newkey); + } - if (bytecount > 0) { - random_fortuna_genrandom(remainder_buf, sizeof(remainder_buf)); - memcpy(buf, remainder_buf, bytecount); - explicit_bzero(remainder_buf, sizeof(remainder_buf)); + buf += read_chunk; + read_directly_len -= read_chunk; + bytecount -= read_chunk; + } + if (bytecount > 0) { + randomdev_keystream(&key_copy, &counter_copy, + remainder_buf, sizeof(remainder_buf)); + memcpy(buf, remainder_buf, bytecount); + explicit_bzero(remainder_buf, sizeof(remainder_buf)); + } } - RANDOM_RESEED_UNLOCK(); + explicit_bzero(&counter_copy, sizeof(counter_copy)); + explicit_bzero(&key_copy, sizeof(key_copy)); + 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) {