diff --git a/sys/dev/random/fortuna.c b/sys/dev/random/fortuna.c index 48620a14c349..f7f8a753c790 100644 --- a/sys/dev/random/fortuna.c +++ b/sys/dev/random/fortuna.c @@ -1,541 +1,720 @@ /*- * Copyright (c) 2017 W. Dean Freeman * Copyright (c) 2013-2015 Mark R V Murray * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer * in this position and unchanged. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * */ /* * This implementation of Fortuna is based on the descriptions found in * ISBN 978-0-470-47424-2 "Cryptography Engineering" by Ferguson, Schneier * and Kohno ("FS&K"). */ #include __FBSDID("$FreeBSD$"); #include #include #ifdef _KERNEL #include #include #include #include #include #include #include #include #include #include #else /* !_KERNEL */ #include #include #include #include #include #include #include "unit_test.h" #endif /* _KERNEL */ +#include #include #include #include #include #ifdef _KERNEL #include #endif #include #include /* 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. * Making RANDOM_FORTUNA_DEFPOOLSIZE too large will mean a long time between reseeds, * and too small may compromise initial security but get faster reseeds. */ #define RANDOM_FORTUNA_MINPOOLSIZE 16 #define RANDOM_FORTUNA_MAXPOOLSIZE INT_MAX CTASSERT(RANDOM_FORTUNA_MINPOOLSIZE <= RANDOM_FORTUNA_DEFPOOLSIZE); CTASSERT(RANDOM_FORTUNA_DEFPOOLSIZE <= RANDOM_FORTUNA_MAXPOOLSIZE); /* This algorithm (and code) presumes that RANDOM_KEYSIZE is twice as large as RANDOM_BLOCKSIZE */ CTASSERT(RANDOM_BLOCKSIZE == sizeof(uint128_t)); CTASSERT(RANDOM_KEYSIZE == 2*RANDOM_BLOCKSIZE); /* Probes for dtrace(1) */ #ifdef _KERNEL SDT_PROVIDER_DECLARE(random); SDT_PROVIDER_DEFINE(random); SDT_PROBE_DEFINE2(random, fortuna, event_processor, debug, "u_int", "struct fs_pool *"); #endif /* _KERNEL */ /* * This is the beastie that needs protecting. It contains all of the * state that we are excited about. Exactly one is instantiated. */ static struct fortuna_state { struct fs_pool { /* P_i */ u_int fsp_length; /* Only the first one is used by Fortuna */ struct randomdev_hash fsp_hash; } fs_pool[RANDOM_FORTUNA_NPOOLS]; u_int fs_reseedcount; /* ReseedCnt */ uint128_t fs_counter; /* C */ union randomdev_key fs_key; /* K */ u_int fs_minpoolsize; /* Extras */ /* Extras for the OS */ #ifdef _KERNEL /* For use when 'pacing' the reseeds */ sbintime_t fs_lasttime; #endif /* Reseed lock */ 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 __read_frequently = false; + #ifdef _KERNEL static struct sysctl_ctx_list random_clist; RANDOM_CHECK_UINT(fs_minpoolsize, RANDOM_FORTUNA_MINPOOLSIZE, RANDOM_FORTUNA_MAXPOOLSIZE); #else static uint8_t zero_region[RANDOM_ZERO_BLOCKSIZE]; #endif static void random_fortuna_pre_read(void); static void random_fortuna_read(uint8_t *, size_t); static bool random_fortuna_seeded(void); static bool random_fortuna_seeded_internal(void); static void random_fortuna_process_event(struct harvest_event *); static void random_fortuna_init_alg(void *); static void random_fortuna_deinit_alg(void *); static void random_fortuna_reseed_internal(uint32_t *entropy_data, u_int blockcount); struct random_algorithm random_alg_context = { .ra_ident = "Fortuna", .ra_init_alg = random_fortuna_init_alg, .ra_deinit_alg = random_fortuna_deinit_alg, .ra_pre_read = random_fortuna_pre_read, .ra_read = random_fortuna_read, .ra_seeded = random_fortuna_seeded, .ra_event_processor = random_fortuna_process_event, .ra_poolcount = RANDOM_FORTUNA_NPOOLS, }; /* ARGSUSED */ static void random_fortuna_init_alg(void *unused __unused) { int i; #ifdef _KERNEL struct sysctl_oid *random_fortuna_o; #endif RANDOM_RESEED_INIT_LOCK(); /* * Fortuna parameters. Do not adjust these unless you have * have a very good clue about what they do! */ fortuna_state.fs_minpoolsize = RANDOM_FORTUNA_DEFPOOLSIZE; #ifdef _KERNEL fortuna_state.fs_lasttime = 0; random_fortuna_o = SYSCTL_ADD_NODE(&random_clist, SYSCTL_STATIC_CHILDREN(_kern_random), OID_AUTO, "fortuna", CTLFLAG_RW, 0, "Fortuna Parameters"); SYSCTL_ADD_PROC(&random_clist, SYSCTL_CHILDREN(random_fortuna_o), OID_AUTO, "minpoolsize", CTLTYPE_UINT | CTLFLAG_RWTUN, &fortuna_state.fs_minpoolsize, RANDOM_FORTUNA_DEFPOOLSIZE, 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 /*- * FS&K - InitializePRNG() * - P_i = \epsilon * - ReseedCNT = 0 */ for (i = 0; i < RANDOM_FORTUNA_NPOOLS; i++) { randomdev_hash_init(&fortuna_state.fs_pool[i].fsp_hash); fortuna_state.fs_pool[i].fsp_length = 0; } fortuna_state.fs_reseedcount = 0; /*- * FS&K - InitializeGenerator() * - C = 0 * - K = 0 */ fortuna_state.fs_counter = UINT128_ZERO; explicit_bzero(&fortuna_state.fs_key, sizeof(fortuna_state.fs_key)); } /* ARGSUSED */ static void random_fortuna_deinit_alg(void *unused __unused) { RANDOM_RESEED_DEINIT_LOCK(); explicit_bzero(&fortuna_state, sizeof(fortuna_state)); #ifdef _KERNEL sysctl_ctx_free(&random_clist); #endif } /*- * FS&K - AddRandomEvent() * Process a single stochastic event off the harvest queue */ static void random_fortuna_process_event(struct harvest_event *event) { u_int pl; RANDOM_RESEED_LOCK(); /*- * FS&K - P_i = P_i| * Accumulate the event into the appropriate pool * where each event carries the destination information. * * The hash_init() and hash_finish() calls are done in * random_fortuna_pre_read(). * * We must be locked against pool state modification which can happen * during accumulation/reseeding and reading/regating. */ pl = event->he_destination % RANDOM_FORTUNA_NPOOLS; /* * We ignore low entropy static/counter fields towards the end of the * he_event structure in order to increase measurable entropy when * conducting SP800-90B entropy analysis measurements of seed material * fed into PRNG. * -- wdf */ KASSERT(event->he_size <= sizeof(event->he_entropy), ("%s: event->he_size: %hhu > sizeof(event->he_entropy): %zu\n", __func__, event->he_size, sizeof(event->he_entropy))); randomdev_hash_iterate(&fortuna_state.fs_pool[pl].fsp_hash, &event->he_somecounter, sizeof(event->he_somecounter)); randomdev_hash_iterate(&fortuna_state.fs_pool[pl].fsp_hash, event->he_entropy, event->he_size); /*- * Don't wrap the length. This is a "saturating" add. * XXX: FIX!!: We don't actually need lengths for anything but fs_pool[0], * but it's been useful debugging to see them all. */ fortuna_state.fs_pool[pl].fsp_length = MIN(RANDOM_FORTUNA_MAXPOOLSIZE, fortuna_state.fs_pool[pl].fsp_length + sizeof(event->he_somecounter) + event->he_size); RANDOM_RESEED_UNLOCK(); } /*- * FS&K - Reseed() * This introduces new key material into the output generator. * Additionally it increments the output generator's counter * variable C. When C > 0, the output generator is seeded and * will deliver output. * The entropy_data buffer passed is a very specific size; the * product of RANDOM_FORTUNA_NPOOLS and RANDOM_KEYSIZE. */ static void random_fortuna_reseed_internal(uint32_t *entropy_data, u_int blockcount) { 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_internal(); 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); 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); randomdev_hash_iterate(&context, hash, RANDOM_KEYSIZE); randomdev_hash_finish(&context, hash); randomdev_encrypt_init(&fortuna_state.fs_key, hash); explicit_bzero(hash, sizeof(hash)); /* Unblock the device if this is the first time we are reseeding. */ if (uint128_is_zero(fortuna_state.fs_counter)) randomdev_unblock(); 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) * 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 * specific actions at the begin of the read. */ void random_fortuna_pre_read(void) { #ifdef _KERNEL sbintime_t now; #endif struct randomdev_hash context; uint32_t s[RANDOM_FORTUNA_NPOOLS*RANDOM_KEYSIZE_WORDS]; uint8_t temp[RANDOM_KEYSIZE]; u_int i; KASSERT(fortuna_state.fs_minpoolsize > 0, ("random: Fortuna threshold must be > 0")); RANDOM_RESEED_LOCK(); #ifdef _KERNEL /* FS&K - Use 'getsbinuptime()' to prevent reseed-spamming. */ now = getsbinuptime(); #endif if (fortuna_state.fs_pool[0].fsp_length < fortuna_state.fs_minpoolsize #ifdef _KERNEL /* * FS&K - Use 'getsbinuptime()' to prevent reseed-spamming, but do * not block initial seeding (fs_lasttime == 0). */ || (__predict_true(fortuna_state.fs_lasttime != 0) && now - fortuna_state.fs_lasttime <= SBT_1S/10) #endif ) { RANDOM_RESEED_UNLOCK(); return; } #ifdef _KERNEL /* * When set, pretend we do not have enough entropy to reseed yet. */ KFAIL_POINT_CODE(DEBUG_FP, random_fortuna_pre_read, { if (RETURN_VALUE != 0) { RANDOM_RESEED_UNLOCK(); return; } }); #endif #ifdef _KERNEL fortuna_state.fs_lasttime = now; #endif /* FS&K - ReseedCNT = ReseedCNT + 1 */ fortuna_state.fs_reseedcount++; /* s = \epsilon at start */ for (i = 0; i < RANDOM_FORTUNA_NPOOLS; i++) { /* FS&K - if Divides(ReseedCnt, 2^i) ... */ if ((fortuna_state.fs_reseedcount % (1 << i)) == 0) { /*- * FS&K - temp = (P_i) * - P_i = \epsilon * - s = s|H(temp) */ randomdev_hash_finish(&fortuna_state.fs_pool[i].fsp_hash, temp); randomdev_hash_init(&fortuna_state.fs_pool[i].fsp_hash); fortuna_state.fs_pool[i].fsp_length = 0; randomdev_hash_init(&context); randomdev_hash_iterate(&context, temp, RANDOM_KEYSIZE); randomdev_hash_finish(&context, s + i*RANDOM_KEYSIZE_WORDS); } else break; } #ifdef _KERNEL SDT_PROBE2(random, fortuna, event_processor, debug, fortuna_state.fs_reseedcount, fortuna_state.fs_pool); #endif /* FS&K */ random_fortuna_reseed_internal(s, i); RANDOM_RESEED_UNLOCK(); /* Clean up and secure */ explicit_bzero(s, sizeof(s)); explicit_bzero(temp, sizeof(temp)); } -/*- - * FS&K - RandomData() (Part 2) - * Main read from Fortuna, continued. May be called multiple times after - * the random_fortuna_pre_read() above. +/* + * This is basically GenerateBlocks() from FS&K. * - * 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. + * 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 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 -random_fortuna_read(uint8_t *buf, size_t bytecount) +enum { + 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]; - size_t read_directly_len, read_chunk; + size_t chunk_size; - /* - * The underlying AES generator expects multiples of RANDOM_BLOCKSIZE. - */ - if (random_chachamode) - read_directly_len = bytecount; + if (locked) + RANDOM_RESEED_ASSERT_LOCK_OWNED(); else - read_directly_len = rounddown(bytecount, RANDOM_BLOCKSIZE); + RANDOM_RESEED_ASSERT_LOCK_NOT_OWNED(); - RANDOM_RESEED_LOCK(); - KASSERT(!uint128_is_zero(fortuna_state.fs_counter), ("FS&K: C != 0")); + /* + * 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 (!locked && random_chachamode) { + randomdev_keystream(p_key, p_counter, buf, bytecount); + return; + } - while (read_directly_len > 0) { + if (locked) { /* - * 128-bit block ciphers like AES must be re-keyed at 1MB - * intervals to avoid unacceptable statistical differentiation - * from true random data. - * - * 512-bit block ciphers like Chacha20 do not have this - * problem. (FS&K 9.4) + * While holding the global lock, limit PRF generation to + * mitigate, but not eliminate, bullying symptoms. */ - if (random_chachamode) - read_chunk = read_directly_len; - else - read_chunk = MIN(read_directly_len, - RANDOM_FORTUNA_MAX_READ); - + chunk_size = PAGE_SIZE; + } else { /* - * For now, we hold the global Fortuna mutex, so yield - * periodically to provide vague availability to other lock - * users. PAGE_SIZE is chosen to match existing behavior. - */ - read_chunk = MIN(read_chunk, PAGE_SIZE); + * 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). + */ + MPASS(!random_chachamode); + chunk_size = RANDOM_FORTUNA_MAX_READ; + } - random_fortuna_genrandom(buf, read_chunk); - buf += read_chunk; - read_directly_len -= read_chunk; - bytecount -= read_chunk; + chunk_size = MIN(bytecount, chunk_size); + if (!random_chachamode) + chunk_size = rounddown(chunk_size, RANDOM_BLOCKSIZE); - /* Perform the actual yield. */ - if (read_directly_len != 0) { - RANDOM_RESEED_UNLOCK(); - RANDOM_RESEED_LOCK(); + while (bytecount >= chunk_size) { + randomdev_keystream(p_key, p_counter, buf, chunk_size); + + buf += chunk_size; + bytecount -= chunk_size; + + /* We have to rekey if there is any data remaining to be + * generated, in two scenarios: + * + * locked: we need to rekey before we unlock and release the + * 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 (bytecount > 0) { + if (locked || chunk_size == RANDOM_FORTUNA_MAX_READ) { + randomdev_keystream(p_key, p_counter, newkey, + RANDOM_KEYSIZE); + randomdev_encrypt_init(p_key, newkey); + } + + /* + * If we're holding the global lock, yield it briefly + * now. + */ + if (locked) { + RANDOM_RESEED_UNLOCK(); + 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; + } } } - if (bytecount > 0) - random_fortuna_genrandom(remainder_buf, sizeof(remainder_buf)); + /* + * Generate any partial AES block remaining into a temporary buffer and + * copy the desired substring out. + */ + if (bytecount > 0) { + MPASS(!random_chachamode); - RANDOM_RESEED_UNLOCK(); + randomdev_keystream(p_key, p_counter, remainder_buf, + sizeof(remainder_buf)); + } + + /* + * In locked mode, re-key global K before dropping the lock, which we + * don't need for memcpy/bzero below. + */ + if (locked) { + randomdev_keystream(p_key, p_counter, newkey, RANDOM_KEYSIZE); + randomdev_encrypt_init(p_key, newkey); + RANDOM_RESEED_UNLOCK(); + } if (bytecount > 0) { memcpy(buf, remainder_buf, bytecount); 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_add64(&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_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); + /* Returns unlocked */ + RANDOM_RESEED_ASSERT_LOCK_NOT_OWNED(); + +out: + explicit_bzero(newkey, sizeof(newkey)); +} + #ifdef _KERNEL static bool block_seeded_status = false; SYSCTL_BOOL(_kern_random, OID_AUTO, block_seeded_status, CTLFLAG_RWTUN, &block_seeded_status, 0, "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 " "unavailable."); #endif static bool random_fortuna_seeded_internal(void) { return (!uint128_is_zero(fortuna_state.fs_counter)); } static bool random_fortuna_seeded(void) { #ifdef _KERNEL if (block_seeded_status) return (false); #endif if (__predict_true(random_fortuna_seeded_internal())) return (true); /* * Maybe we have enough entropy in the zeroth pool but just haven't * kicked the initial seed step. Do so now. */ random_fortuna_pre_read(); return (random_fortuna_seeded_internal()); } diff --git a/sys/dev/random/fortuna.h b/sys/dev/random/fortuna.h index 43aad04fb13c..3b75a008d91d 100644 --- a/sys/dev/random/fortuna.h +++ b/sys/dev/random/fortuna.h @@ -1,47 +1,49 @@ /*- * Copyright (c) 2013-2015 Mark R V Murray * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer * in this position and unchanged. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * * $FreeBSD$ */ #ifndef SYS_DEV_RANDOM_FORTUNA_H_INCLUDED #define SYS_DEV_RANDOM_FORTUNA_H_INCLUDED #ifdef _KERNEL typedef struct mtx mtx_t; #define RANDOM_RESEED_INIT_LOCK(x) mtx_init(&fortuna_state.fs_mtx, "reseed mutex", NULL, MTX_DEF) #define RANDOM_RESEED_DEINIT_LOCK(x) mtx_destroy(&fortuna_state.fs_mtx) #define RANDOM_RESEED_LOCK(x) mtx_lock(&fortuna_state.fs_mtx) #define RANDOM_RESEED_UNLOCK(x) mtx_unlock(&fortuna_state.fs_mtx) #define RANDOM_RESEED_ASSERT_LOCK_OWNED(x) mtx_assert(&fortuna_state.fs_mtx, MA_OWNED) +#define RANDOM_RESEED_ASSERT_LOCK_NOT_OWNED() mtx_assert(&fortuna_state.fs_mtx, MA_NOTOWNED) #else #define RANDOM_RESEED_INIT_LOCK(x) mtx_init(&fortuna_state.fs_mtx, mtx_plain) #define RANDOM_RESEED_DEINIT_LOCK(x) mtx_destroy(&fortuna_state.fs_mtx) #define RANDOM_RESEED_LOCK(x) mtx_lock(&fortuna_state.fs_mtx) #define RANDOM_RESEED_UNLOCK(x) mtx_unlock(&fortuna_state.fs_mtx) #define RANDOM_RESEED_ASSERT_LOCK_OWNED(x) +#define RANDOM_RESEED_ASSERT_LOCK_NOT_OWNED() #endif #endif /* SYS_DEV_RANDOM_FORTUNA_H_INCLUDED */ diff --git a/sys/dev/random/hash.c b/sys/dev/random/hash.c index cd29b74c43a4..99965513350d 100644 --- a/sys/dev/random/hash.c +++ b/sys/dev/random/hash.c @@ -1,247 +1,247 @@ /*- * Copyright (c) 2000-2015 Mark R V Murray * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer * in this position and unchanged. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * */ #include __FBSDID("$FreeBSD$"); #ifdef _KERNEL #include #include #include #include #include #else /* !_KERNEL */ #include #include #include #include #include #include #include #include #include #include #define KASSERT(x, y) assert(x) #define CTASSERT(x) _Static_assert(x, "CTASSERT " #x) #endif /* _KERNEL */ #define CHACHA_EMBED #define KEYSTREAM_ONLY #define CHACHA_NONCE0_CTR128 #include #include #include #include #ifdef _KERNEL #include #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; +bool random_chachamode __read_frequently = 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) { SHA256_Init(&context->sha); } /* Iterate the hash */ void randomdev_hash_iterate(struct randomdev_hash *context, const void *data, size_t size) { SHA256_Update(&context->sha, data, size); } /* Conclude by returning the hash in the supplied <*buf> which must be * RANDOM_KEYSIZE bytes long. */ void randomdev_hash_finish(struct randomdev_hash *context, void *buf) { SHA256_Final(buf, &context->sha); } /* Initialise the encryption routine by setting up the key schedule * from the supplied <*data> which must be RANDOM_KEYSIZE bytes of binary * data. */ void randomdev_encrypt_init(union randomdev_key *context, const void *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); } } /* * Create a psuedorandom output stream of 'bytecount' bytes using a CTR-mode * cipher or similar. The 128-bit counter is supplied in the in-out parmeter * 'ctr.' The output stream goes to 'd_out.' * * If AES is used, 'bytecount' is guaranteed to be a multiple of * RANDOM_BLOCKSIZE. */ void randomdev_keystream(union randomdev_key *context, uint128_t *ctr, void *d_out, size_t bytecount) { size_t i, blockcount, read_chunk; 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. */ le128enc(&lectr, *ctr); chacha_ivsetup(&context->chacha, NULL, (const void *)&lectr); while (bytecount > 0) { /* * We are limited by the chacha_encrypt_bytes API to * u32 bytes per chunk. */ read_chunk = MIN(bytecount, rounddown((size_t)UINT32_MAX, CHACHA_BLOCKLEN)); chacha_encrypt_bytes(&context->chacha, NULL, d_out, read_chunk); d_out = (char *)d_out + read_chunk; bytecount -= read_chunk; } /* * 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); explicit_bzero(&lectr, sizeof(lectr)); } else { KASSERT(bytecount % RANDOM_BLOCKSIZE == 0, ("%s: AES mode invalid bytecount, not a multiple of native " "block size", __func__)); blockcount = bytecount / RANDOM_BLOCKSIZE; 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 } diff --git a/sys/dev/random/hash.h b/sys/dev/random/hash.h index ca2f3db56a00..92a5950f9932 100644 --- a/sys/dev/random/hash.h +++ b/sys/dev/random/hash.h @@ -1,67 +1,71 @@ /*- * Copyright (c) 2000-2015 Mark R V Murray * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer * in this position and unchanged. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * * $FreeBSD$ */ #ifndef SYS_DEV_RANDOM_HASH_H_INCLUDED #define SYS_DEV_RANDOM_HASH_H_INCLUDED #include #include +#ifndef _KERNEL +#define __read_frequently +#endif + /* Keys are formed from cipher blocks */ #define RANDOM_KEYSIZE 32 /* (in bytes) == 256 bits */ #define RANDOM_KEYSIZE_WORDS (RANDOM_KEYSIZE/sizeof(uint32_t)) #define RANDOM_BLOCKSIZE 16 /* (in bytes) == 128 bits */ #define RANDOM_BLOCKSIZE_WORDS (RANDOM_BLOCKSIZE/sizeof(uint32_t)) #define RANDOM_KEYS_PER_BLOCK (RANDOM_KEYSIZE/RANDOM_BLOCKSIZE) /* The size of the zero block portion used to form H_d(m) */ #define RANDOM_ZERO_BLOCKSIZE 64 /* (in bytes) == 512 zero bits */ struct randomdev_hash { SHA256_CTX sha; }; union randomdev_key { struct { keyInstance key; /* Key schedule */ cipherInstance cipher; /* Rijndael internal */ }; struct chacha_ctx chacha; }; extern bool random_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(union randomdev_key *, const void *); void randomdev_keystream(union randomdev_key *context, uint128_t *, void *, size_t); void randomdev_getkey(union randomdev_key *, const void **, size_t *); #endif /* SYS_DEV_RANDOM_HASH_H_INCLUDED */ diff --git a/sys/dev/random/uint128.h b/sys/dev/random/uint128.h index 63de28a3864a..71056a63a93b 100644 --- a/sys/dev/random/uint128.h +++ b/sys/dev/random/uint128.h @@ -1,114 +1,129 @@ /*- * Copyright (c) 2015 Mark R V Murray * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer * in this position and unchanged. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * * $FreeBSD$ */ #ifndef SYS_DEV_RANDOM_UINT128_H_INCLUDED #define SYS_DEV_RANDOM_UINT128_H_INCLUDED #include /* This whole thing is a crock :-( * * Everyone knows you always need the __uint128_t types! */ #ifdef __SIZEOF_INT128__ #define USE_REAL_UINT128_T #endif #ifdef USE_REAL_UINT128_T typedef __uint128_t uint128_t; #define UINT128_ZERO 0ULL #else typedef struct { /* Ignore endianness */ uint64_t u128t_word0; uint64_t u128t_word1; } uint128_t; static const uint128_t very_long_zero = {0UL,0UL}; #define UINT128_ZERO very_long_zero #endif static __inline void uint128_increment(uint128_t *big_uintp) { #ifdef USE_REAL_UINT128_T (*big_uintp)++; #else big_uintp->u128t_word0++; if (big_uintp->u128t_word0 == 0UL) big_uintp->u128t_word1++; #endif } +static __inline void +uint128_add64(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) { #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 (((uint128_t)le64dec(p + 8) << 64) | le64dec(p)); #else 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 } #endif /* SYS_DEV_RANDOM_UINT128_H_INCLUDED */ diff --git a/tests/sys/devrandom/uint128_test.c b/tests/sys/devrandom/uint128_test.c index c621b0cc1a8d..288e8a2e9f79 100644 --- a/tests/sys/devrandom/uint128_test.c +++ b/tests/sys/devrandom/uint128_test.c @@ -1,224 +1,281 @@ /*- * SPDX-License-Identifier: BSD-2-Clause-FreeBSD * * Copyright (c) 2019 Conrad Meyer * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. */ #include __FBSDID("$FreeBSD$"); #include #include #include #include #include #include #include #include #include #include #include #include static void vec_u32_tole128(uint8_t dst[static 16], const uint32_t src[static 4]) { le32enc(dst, src[0]); le32enc(&dst[4], src[1]); le32enc(&dst[8], src[2]); le32enc(&dst[12], src[3]); } static void le128_to_vec_u32(uint32_t dst[static 4], const uint8_t src[static 16]) { dst[0] = le32dec(src); dst[1] = le32dec(&src[4]); dst[2] = le32dec(&src[8]); dst[3] = le32dec(&src[12]); } static void formatu128(char buf[static 52], uint128_t x) { uint8_t le128x[16]; uint32_t vx[4]; size_t sz, i; int rc; le128enc(le128x, x); le128_to_vec_u32(vx, le128x); sz = 52; for (i = 0; i < 4; i++) { rc = snprintf(buf, sz, "0x%x ", vx[i]); ATF_REQUIRE(rc > 0 && (size_t)rc < sz); buf += rc; sz -= rc; } /* Delete last trailing space */ buf[-1] = '\0'; } static void u128_check_equality(uint128_t a, uint128_t b, const char *descr) { char fmtbufa[52], fmtbufb[52]; formatu128(fmtbufa, a); formatu128(fmtbufb, b); ATF_CHECK_MSG(uint128_equals(a, b), "Expected: [%s] != Actual: [%s]: %s", fmtbufa, fmtbufb, descr); } ATF_TC_WITHOUT_HEAD(uint128_inc); ATF_TC_BODY(uint128_inc, tc) { static const struct u128_inc_tc { uint32_t input[4]; uint32_t expected[4]; const char *descr; } tests[] = { { .input = { 0, 0, 0, 0 }, .expected = { 1, 0, 0, 0 }, .descr = "0 -> 1", }, { .input = { 1, 0, 0, 0 }, .expected = { 2, 0, 0, 0 }, .descr = "0 -> 2", }, { .input = { 0xff, 0, 0, 0 }, .expected = { 0x100, 0, 0, 0 }, .descr = "0xff -> 0x100 (byte carry)", }, { .input = { UINT32_MAX, 0, 0, 0 }, .expected = { 0, 1, 0, 0 }, .descr = "2^32 - 1 -> 2^32 (word carry)", }, { .input = { UINT32_MAX, UINT32_MAX, 0, 0 }, .expected = { 0, 0, 1, 0 }, .descr = "2^64 - 1 -> 2^64 (u128t_word0 carry)", }, { .input = { UINT32_MAX, UINT32_MAX, UINT32_MAX, 0 }, .expected = { 0, 0, 0, 1 }, .descr = "2^96 - 1 -> 2^96 (word carry)", }, }; uint8_t inputle[16], expectedle[16]; uint128_t a; size_t i; for (i = 0; i < nitems(tests); i++) { vec_u32_tole128(inputle, tests[i].input); vec_u32_tole128(expectedle, tests[i].expected); a = le128dec(inputle); uint128_increment(&a); u128_check_equality(le128dec(expectedle), a, tests[i].descr); } } +ATF_TC_WITHOUT_HEAD(uint128_add64); +ATF_TC_BODY(uint128_add64, tc) +{ + static const struct u128_add64_tc { + uint32_t input[4]; + uint64_t addend; + uint32_t expected[4]; + const char *descr; + } tests[] = { + { + .input = { 0, 0, 0, 0 }, + .addend = 1, + .expected = { 1, 0, 0, 0 }, + .descr = "0 + 1 -> 1", + }, + { + .input = { 1, 0, 0, 0 }, + .addend = UINT32_MAX, + .expected = { 0, 1, 0, 0 }, + .descr = "1 + (2^32 - 1) -> 2^32 (word carry)", + }, + { + .input = { 1, 0, 0, 0 }, + .addend = UINT64_MAX, + .expected = { 0, 0, 1, 0 }, + .descr = "1 + (2^64 - 1) -> 2^64 (u128t_word0 carry)", + }, + { + .input = { 0x11111111, 0x11111111, 0, 0 }, + .addend = 0xf0123456789abcdeULL, + .expected = { 0x89abcdef, 0x01234567, 1, 0 }, + .descr = "0x1111_1111_1111_1111 +" + "0xf012_3456_789a_bcde ->" + "0x1_0123_4567_89ab_cdef", + }, + { + .input = { 1, 0, UINT32_MAX, 0 }, + .addend = UINT64_MAX, + .expected = { 0, 0, 0, 1 }, + .descr = "Carry ~2^96", + }, + }; + uint8_t inputle[16], expectedle[16]; + uint128_t a; + size_t i; + + for (i = 0; i < nitems(tests); i++) { + vec_u32_tole128(inputle, tests[i].input); + vec_u32_tole128(expectedle, tests[i].expected); + + a = le128dec(inputle); + uint128_add64(&a, tests[i].addend); + u128_check_equality(le128dec(expectedle), a, tests[i].descr); + } +} + /* * Test assumptions about Chacha incrementing counter in the same way as * uint128.h */ ATF_TC_WITHOUT_HEAD(uint128_chacha_ctr); ATF_TC_BODY(uint128_chacha_ctr, tc) { static const struct u128_chacha_tc { uint32_t input[4]; uint32_t expected[4]; const char *descr; } tests[] = { { .input = { 0, 0, 0, 0 }, .expected = { 1, 0, 0, 0 }, .descr = "Single block", }, { .input = { 1, 0, 0, 0 }, .expected = { 2, 0, 0, 0 }, .descr = "0 -> 2", }, { .input = { 0xff, 0, 0, 0 }, .expected = { 0x100, 0, 0, 0 }, .descr = "0xff -> 0x100 (byte carry)", }, { .input = { UINT32_MAX, 0, 0, 0 }, .expected = { 0, 1, 0, 0 }, .descr = "2^32 - 1 -> 2^32 (word carry)", }, { .input = { UINT32_MAX, UINT32_MAX, 0, 0 }, .expected = { 0, 0, 1, 0 }, .descr = "2^64 - 1 -> 2^64 (u128t_word0 carry)", }, { .input = { UINT32_MAX, UINT32_MAX, UINT32_MAX, 0 }, .expected = { 0, 0, 0, 1 }, .descr = "2^96 - 1 -> 2^96 (word carry)", }, }; union randomdev_key context; uint8_t inputle[16], expectedle[16], trash[CHACHA_BLOCKLEN]; uint8_t notrandomkey[RANDOM_KEYSIZE] = { 0 }; uint128_t a; size_t i; random_chachamode = true; randomdev_encrypt_init(&context, notrandomkey); for (i = 0; i < nitems(tests); i++) { vec_u32_tole128(inputle, tests[i].input); vec_u32_tole128(expectedle, tests[i].expected); a = le128dec(inputle); randomdev_keystream(&context, &a, trash, sizeof(trash)); u128_check_equality(le128dec(expectedle), a, tests[i].descr); } } ATF_TP_ADD_TCS(tp) { ATF_TP_ADD_TC(tp, uint128_inc); + ATF_TP_ADD_TC(tp, uint128_add64); ATF_TP_ADD_TC(tp, uint128_chacha_ctr); return (atf_no_error()); }