Date: Fri, 8 Mar 2019 01:17:20 +0000 (UTC) From: Conrad Meyer <cem@FreeBSD.org> To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r344913 - head/sys/dev/random Message-ID: <201903080117.x281HK4N002587@repo.freebsd.org>
next in thread | raw e-mail | index | archive | help
Author: cem Date: Fri Mar 8 01:17:20 2019 New Revision: 344913 URL: https://svnweb.freebsd.org/changeset/base/344913 Log: Fortuna: Add Chacha20 as an alternative stream cipher Chacha20 with a 256 bit key and 128 bit counter size is a good match for an AES256-ICM replacement. In userspace, Chacha20 is typically marginally slower than AES-ICM on machines with AESNI intrinsics, but typically much faster than AES on machines without special intrinsics. ChaCha20 does well on typical modern architectures with SIMD instructions, which includes most types of machines FreeBSD runs on. In the kernel, we can't (or don't) make use of AESNI intrinsics for random(4) anyway. So even on amd64, using Chacha provides a modest performance improvement in random device throughput today. This change makes the stream cipher used by random(4) configurable at boot time with the 'kern.random.use_chacha20_cipher' tunable. Very rough, non-scientific measurements at the /dev/random device, on a GENERIC-NODEBUG amd64 VM with 'pv', show a factor of 2.2x higher throughput for Chacha20 over the existing AES-ICM mode. Reviewed by: delphij, markm Approved by: secteam (delphij) Differential Revision: https://reviews.freebsd.org/D19475 Modified: head/sys/dev/random/fortuna.c head/sys/dev/random/hash.c head/sys/dev/random/hash.h head/sys/dev/random/uint128.h Modified: head/sys/dev/random/fortuna.c ============================================================================== --- head/sys/dev/random/fortuna.c Fri Mar 8 01:04:19 2019 (r344912) +++ head/sys/dev/random/fortuna.c Fri Mar 8 01:17:20 2019 (r344913) @@ -109,7 +109,7 @@ static struct fortuna_state { } fs_pool[RANDOM_FORTUNA_NPOOLS]; u_int fs_reseedcount; /* ReseedCnt */ uint128_t fs_counter; /* C */ - struct randomdev_key fs_key; /* K */ + union randomdev_key fs_key; /* K */ u_int fs_minpoolsize; /* Extras */ /* Extras for the OS */ #ifdef _KERNEL @@ -271,16 +271,27 @@ random_fortuna_reseed_internal(uint32_t *entropy_data, { struct randomdev_hash context; uint8_t hash[RANDOM_KEYSIZE]; + const void *keymaterial; + size_t keysz; + bool seeded; RANDOM_RESEED_ASSERT_LOCK_OWNED(); + + seeded = random_fortuna_seeded(); + if (seeded) { + randomdev_getkey(&fortuna_state.fs_key, &keymaterial, &keysz); + KASSERT(keysz == RANDOM_KEYSIZE, ("%s: key size %zu not %u", + __func__, keysz, (unsigned)RANDOM_KEYSIZE)); + } + /*- * FS&K - K = Hd(K|s) where Hd(m) is H(H(0^512|m)) * - C = C + 1 */ randomdev_hash_init(&context); randomdev_hash_iterate(&context, zero_region, RANDOM_ZERO_BLOCKSIZE); - randomdev_hash_iterate(&context, &fortuna_state.fs_key.key.keyMaterial, - fortuna_state.fs_key.key.keyLen / 8); + if (seeded) + randomdev_hash_iterate(&context, keymaterial, keysz); randomdev_hash_iterate(&context, entropy_data, RANDOM_KEYSIZE*blockcount); randomdev_hash_finish(&context, hash); randomdev_hash_init(&context); Modified: head/sys/dev/random/hash.c ============================================================================== --- head/sys/dev/random/hash.c Fri Mar 8 01:04:19 2019 (r344912) +++ head/sys/dev/random/hash.c Fri Mar 8 01:17:20 2019 (r344913) @@ -30,6 +30,9 @@ __FBSDID("$FreeBSD$"); #ifdef _KERNEL #include <sys/param.h> +#include <sys/malloc.h> +#include <sys/random.h> +#include <sys/sysctl.h> #include <sys/systm.h> #else /* !_KERNEL */ #include <sys/param.h> @@ -42,14 +45,39 @@ __FBSDID("$FreeBSD$"); #include "unit_test.h" #endif /* _KERNEL */ +#define CHACHA_EMBED +#define KEYSTREAM_ONLY +#define CHACHA_NONCE0_CTR128 +#include <crypto/chacha20/chacha.c> #include <crypto/rijndael/rijndael-api-fst.h> #include <crypto/sha2/sha256.h> #include <dev/random/hash.h> +#ifdef _KERNEL +#include <dev/random/randomdev.h> +#endif /* This code presumes that RANDOM_KEYSIZE is twice as large as RANDOM_BLOCKSIZE */ CTASSERT(RANDOM_KEYSIZE == 2*RANDOM_BLOCKSIZE); +/* Validate that full Chacha IV is as large as the 128-bit counter */ +_Static_assert(CHACHA_STATELEN == RANDOM_BLOCKSIZE, ""); + +/* + * Experimental Chacha20-based PRF for Fortuna keystream primitive. For now, + * disabled by default. But we may enable it in the future. + * + * Benefits include somewhat faster keystream generation compared with + * unaccelerated AES-ICM. + */ +bool random_chachamode = false; +#ifdef _KERNEL +SYSCTL_BOOL(_kern_random, OID_AUTO, use_chacha20_cipher, CTLFLAG_RDTUN, + &random_chachamode, 0, + "If non-zero, use the ChaCha20 cipher for randomdev PRF. " + "If zero, use AES-ICM cipher for randomdev PRF (default)."); +#endif + /* Initialise the hash */ void randomdev_hash_init(struct randomdev_hash *context) @@ -81,11 +109,15 @@ randomdev_hash_finish(struct randomdev_hash *context, * data. */ void -randomdev_encrypt_init(struct randomdev_key *context, const void *data) +randomdev_encrypt_init(union randomdev_key *context, const void *data) { - rijndael_cipherInit(&context->cipher, MODE_ECB, NULL); - rijndael_makeKey(&context->key, DIR_ENCRYPT, RANDOM_KEYSIZE*8, data); + if (random_chachamode) { + chacha_keysetup(&context->chacha, data, RANDOM_KEYSIZE * 8); + } else { + rijndael_cipherInit(&context->cipher, MODE_ECB, NULL); + rijndael_makeKey(&context->key, DIR_ENCRYPT, RANDOM_KEYSIZE*8, data); + } } /* @@ -95,19 +127,96 @@ randomdev_encrypt_init(struct randomdev_key *context, * bytes are generated. */ void -randomdev_keystream(struct randomdev_key *context, uint128_t *ctr, +randomdev_keystream(union randomdev_key *context, uint128_t *ctr, void *d_out, u_int blockcount) { u_int i; - for (i = 0; i < blockcount; i++) { - /*- - * FS&K - r = r|E(K,C) - * - C = C + 1 + if (random_chachamode) { + uint128_t lectr; + + /* + * Chacha always encodes and increments the counter little + * endian. So on BE machines, we must provide a swapped + * counter to chacha, and swap the output too. */ - rijndael_blockEncrypt(&context->cipher, &context->key, - (void *)ctr, RANDOM_BLOCKSIZE * 8, d_out); - d_out = (char *)d_out + RANDOM_BLOCKSIZE; - uint128_increment(ctr); + le128enc(&lectr, *ctr); + + chacha_ivsetup(&context->chacha, NULL, (const void *)&lectr); + chacha_encrypt_bytes(&context->chacha, NULL, d_out, + RANDOM_BLOCKSIZE * blockcount); + + /* + * Decode Chacha-updated LE counter to native endian and store + * it back in the caller's in-out parameter. + */ + chacha_ctrsave(&context->chacha, (void *)&lectr); + *ctr = le128dec(&lectr); + } else { + for (i = 0; i < blockcount; i++) { + /*- + * FS&K - r = r|E(K,C) + * - C = C + 1 + */ + rijndael_blockEncrypt(&context->cipher, &context->key, + (void *)ctr, RANDOM_BLOCKSIZE * 8, d_out); + d_out = (char *)d_out + RANDOM_BLOCKSIZE; + uint128_increment(ctr); + } } +} + +/* + * Fetch a pointer to the relevant key material and its size. + * + * This API is expected to only be used only for reseeding, where the + * endianness does not matter; the goal is to simply incorporate the key + * material into the hash iterator that will produce key'. + * + * Do not expect the buffer pointed to by this API to match the exact + * endianness, etc, as the key material that was supplied to + * randomdev_encrypt_init(). + */ +void +randomdev_getkey(union randomdev_key *context, const void **keyp, size_t *szp) +{ + + if (!random_chachamode) { + *keyp = &context->key.keyMaterial; + *szp = context->key.keyLen / 8; + return; + } + + /* Chacha20 mode */ + *keyp = (const void *)&context->chacha.input[4]; + + /* Sanity check keysize */ + if (context->chacha.input[0] == U8TO32_LITTLE(sigma) && + context->chacha.input[1] == U8TO32_LITTLE(&sigma[4]) && + context->chacha.input[2] == U8TO32_LITTLE(&sigma[8]) && + context->chacha.input[3] == U8TO32_LITTLE(&sigma[12])) { + *szp = 32; + return; + } + +#if 0 + /* + * Included for the sake of completeness; as-implemented, Fortuna + * doesn't need or use 128-bit Chacha20. + */ + if (context->chacha->input[0] == U8TO32_LITTLE(tau) && + context->chacha->input[1] == U8TO32_LITTLE(&tau[4]) && + context->chacha->input[2] == U8TO32_LITTLE(&tau[8]) && + context->chacha->input[3] == U8TO32_LITTLE(&tau[12])) { + *szp = 16; + return; + } +#endif + +#ifdef _KERNEL + panic("%s: Invalid chacha20 keysize: %16D\n", __func__, + (void *)context->chacha.input, " "); +#else + raise(SIGKILL); +#endif } Modified: head/sys/dev/random/hash.h ============================================================================== --- head/sys/dev/random/hash.h Fri Mar 8 01:04:19 2019 (r344912) +++ head/sys/dev/random/hash.h Fri Mar 8 01:17:20 2019 (r344913) @@ -29,6 +29,7 @@ #ifndef SYS_DEV_RANDOM_HASH_H_INCLUDED #define SYS_DEV_RANDOM_HASH_H_INCLUDED +#include <crypto/chacha20/_chacha.h> #include <dev/random/uint128.h> /* Keys are formed from cipher blocks */ @@ -45,15 +46,22 @@ struct randomdev_hash { SHA256_CTX sha; }; -struct randomdev_key { - keyInstance key; /* Key schedule */ - cipherInstance cipher; /* Rijndael internal */ +union randomdev_key { + struct { + keyInstance key; /* Key schedule */ + cipherInstance cipher; /* Rijndael internal */ + }; + struct chacha_ctx chacha; }; +extern bool fortuna_chachamode; + void randomdev_hash_init(struct randomdev_hash *); void randomdev_hash_iterate(struct randomdev_hash *, const void *, size_t); void randomdev_hash_finish(struct randomdev_hash *, void *); -void randomdev_encrypt_init(struct randomdev_key *, const void *); -void randomdev_keystream(struct randomdev_key *context, uint128_t *, void *, u_int); + +void randomdev_encrypt_init(union randomdev_key *, const void *); +void randomdev_keystream(union randomdev_key *context, uint128_t *, void *, u_int); +void randomdev_getkey(union randomdev_key *, const void **, size_t *); #endif /* SYS_DEV_RANDOM_HASH_H_INCLUDED */ Modified: head/sys/dev/random/uint128.h ============================================================================== --- head/sys/dev/random/uint128.h Fri Mar 8 01:04:19 2019 (r344912) +++ head/sys/dev/random/uint128.h Fri Mar 8 01:17:20 2019 (r344913) @@ -29,6 +29,8 @@ #ifndef SYS_DEV_RANDOM_UINT128_H_INCLUDED #define SYS_DEV_RANDOM_UINT128_H_INCLUDED +#include <sys/endian.h> + /* This whole thing is a crock :-( * * Everyone knows you always need the __uint128_t types! @@ -63,13 +65,49 @@ uint128_increment(uint128_t *big_uintp) #endif } +static __inline bool +uint128_equals(uint128_t a, uint128_t b) +{ +#ifdef USE_REAL_UINT128_T + return (a == b); +#else + return (a.u128t_word0 == b.u128t_word0 && + a.u128t_word1 == b.u128t_word1); +#endif +} + static __inline int uint128_is_zero(uint128_t big_uint) { + return (uint128_equals(big_uint, UINT128_ZERO)); +} + +static __inline uint128_t +le128dec(const void *pp) +{ + const uint8_t *p = pp; + #ifdef USE_REAL_UINT128_T - return (big_uint == UINT128_ZERO); + return (((uint128_t)le64dec(p + 8) << 64) | le64dec(p)); #else - return (big_uint.u128t_word0 == 0UL && big_uint.u128t_word1 == 0UL); + return ((uint128_t){ + .u128t_word0 = le64dec(p), + .u128t_word1 = le64dec(p + 8), + }); +#endif +} + +static __inline void +le128enc(void *pp, uint128_t u) +{ + uint8_t *p = pp; + +#ifdef USE_REAL_UINT128_T + le64enc(p, (uint64_t)(u & UINT64_MAX)); + le64enc(p + 8, (uint64_t)(u >> 64)); +#else + le64enc(p, u.u128t_word0); + le64enc(p + 8, u.u128t_word1); #endif }
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201903080117.x281HK4N002587>