diff --git a/random/jitterentropy-base-user.h b/random/jitterentropy-base-user.h index 8a8dbd55..f0fd4842 100644 --- a/random/jitterentropy-base-user.h +++ b/random/jitterentropy-base-user.h @@ -1,134 +1,301 @@ /* * Non-physical true random number generator based on timing jitter. * * Copyright Stephan Mueller , 2013 * * License * ======= * * 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, and the entire permission notice in its entirety, * including the disclaimer of warranties. * 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. * 3. The name of the author may not be used to endorse or promote * products derived from this software without specific prior * written permission. * * ALTERNATIVELY, this product may be distributed under the terms of * the GNU General Public License, in which case the provisions of the GPL are * required INSTEAD OF the above restrictions. (This clause is * necessary due to a potential bad interaction between the GPL and * the restrictions contained in a BSD-style copyright.) * * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ALL OF * WHICH ARE HEREBY 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 NOT ADVISED OF THE POSSIBILITY OF SUCH * DAMAGE. */ #ifndef GCRYPT_JITTERENTROPY_BASE_USER_H #define GCRYPT_JITTERENTROPY_BASE_USER_H /* * This is Libgcrypt specific platform dependent code. We use a * separate file because jitterentropy.h expects such a file. */ #ifndef USE_JENT # error This file expects to be included from rndjent.c (via jitterentropy.h) #endif #ifndef HAVE_STDINT_H # error This module needs stdint.h - try ./configure --disable-jent-support #endif /* When using the libgcrypt secure memory mechanism, all precautions * are taken to protect our state. If the user disables secmem during * runtime, it is his decision and we thus try not to overrule his * decision for less memory protection. */ #define JENT_CPU_JITTERENTROPY_SECURE_MEMORY 1 #define jent_zalloc(n) _gcry_calloc_secure (1, (n)) static void jent_get_nstime(u64 *out) { #if USE_JENT == JENT_USES_RDTSC u32 t_eax, t_edx; asm volatile (".byte 0x0f,0x31\n\t" : "=a" (t_eax), "=d" (t_edx) ); *out = (((u64)t_edx << 32) | t_eax); #elif USE_JENT == JENT_USES_GETTIME struct timespec tv; u64 tmp; /* On Linux we could use CLOCK_MONOTONIC(_RAW), but with * CLOCK_REALTIME we get some nice extra entropy once in a while * from the NTP actions that we want to use as well... though, we do * not rely on that extra little entropy. */ if (!clock_gettime (CLOCK_REALTIME, &tv)) { tmp = tv.tv_sec; tmp = tmp << 32; tmp = tmp | tv.tv_nsec; } else tmp = 0; *out = tmp; #elif USE_JENT == JENT_USES_READ_REAL_TIME /* clock_gettime() on AIX returns a timer value that increments in * steps of 1000. */ u64 tmp = 0; timebasestruct_t aixtime; read_real_time (&aixtime, TIMEBASE_SZ); tmp = aixtime.tb_high; tmp = tmp << 32; tmp = tmp | aixtime.tb_low; *out = tmp; #else # error No clock available in jent_get_nstime #endif } static GPGRT_INLINE void jent_zfree (void *ptr, unsigned int len) { if (ptr) { wipememory (ptr, len); _gcry_free (ptr); } } static GPGRT_INLINE int jent_fips_enabled(void) { return fips_mode(); } +static inline void jent_memset_secure(void *s, size_t n) +{ + memset(s, 0, n); + __asm__ __volatile__("" : : "r" (s) : "memory"); +} + +static inline long jent_ncpu(void) +{ +#ifdef _POSIX_SOURCE + long ncpu = sysconf(_SC_NPROCESSORS_ONLN); + + if (ncpu == -1) + return -errno; + + if (ncpu == 0) + return -EFAULT; + + return ncpu; +#else + return 1; +#endif +} + +#ifdef __linux__ + +# if defined(_SC_LEVEL1_DCACHE_SIZE) && \ + defined(_SC_LEVEL2_CACHE_SIZE) && \ + defined(_SC_LEVEL3_CACHE_SIZE) + +static inline void jent_get_cachesize(long *l1, long *l2, long *l3) +{ + *l1 = sysconf(_SC_LEVEL1_DCACHE_SIZE); + *l2 = sysconf(_SC_LEVEL2_CACHE_SIZE); + *l3 = sysconf(_SC_LEVEL3_CACHE_SIZE); +} + +# else + +static inline void jent_get_cachesize(long *l1, long *l2, long *l3) +{ +#define JENT_SYSFS_CACHE_DIR "/sys/devices/system/cpu/cpu0/cache" + long val; + unsigned int i; + char buf[10], file[50]; + int fd = 0; + + /* Iterate over all caches */ + for (i = 0; i < 4; i++) { + unsigned int shift = 0; + char *ext; + + /* + * Check the cache type - we are only interested in Unified + * and Data caches. + */ + memset(buf, 0, sizeof(buf)); + snprintf(file, sizeof(file), "%s/index%u/type", + JENT_SYSFS_CACHE_DIR, i); + fd = open(file, O_RDONLY); + if (fd < 0) + continue; + while (read(fd, buf, sizeof(buf)) < 0 && errno == EINTR); + close(fd); + buf[sizeof(buf) - 1] = '\0'; + + if (strncmp(buf, "Data", 4) && strncmp(buf, "Unified", 7)) + continue; + + /* Get size of cache */ + memset(buf, 0, sizeof(buf)); + snprintf(file, sizeof(file), "%s/index%u/size", + JENT_SYSFS_CACHE_DIR, i); + + fd = open(file, O_RDONLY); + if (fd < 0) + continue; + while (read(fd, buf, sizeof(buf)) < 0 && errno == EINTR); + close(fd); + buf[sizeof(buf) - 1] = '\0'; + + ext = strstr(buf, "K"); + if (ext) { + shift = 10; + ext = '\0'; + } else { + ext = strstr(buf, "M"); + if (ext) { + shift = 20; + ext = '\0'; + } + } + + val = strtol(buf, NULL, 10); + if (val == LONG_MAX) + continue; + val <<= shift; + + if (!*l1) + *l1 = val; + else if (!*l2) + *l2 = val; + else { + *l3 = val; + break; + } + } +#undef JENT_SYSFS_CACHE_DIR +} + +# endif + +static inline uint32_t jent_cache_size_roundup(void) +{ + static int checked = 0; + static uint32_t cache_size = 0; + + if (!checked) { + long l1 = 0, l2 = 0, l3 = 0; + + jent_get_cachesize(&l1, &l2, &l3); + checked = 1; + + /* Cache size reported by system */ + if (l1 > 0) + cache_size += (uint32_t)l1; + if (l2 > 0) + cache_size += (uint32_t)l2; + if (l3 > 0) + cache_size += (uint32_t)l3; + + /* + * Force the output_size to be of the form + * (bounding_power_of_2 - 1). + */ + cache_size |= (cache_size >> 1); + cache_size |= (cache_size >> 2); + cache_size |= (cache_size >> 4); + cache_size |= (cache_size >> 8); + cache_size |= (cache_size >> 16); + + if (cache_size == 0) + return 0; + + /* + * Make the output_size the smallest power of 2 strictly + * greater than cache_size. + */ + cache_size++; + } + + return cache_size; +} + +#else /* __linux__ */ + +static inline uint32_t jent_cache_size_roundup(void) +{ + return 0; +} + +#endif /* __linux__ */ + +static inline void jent_yield(void) +{ + sched_yield(); +} + #endif /* GCRYPT_JITTERENTROPY_BASE_USER_H */ diff --git a/random/jitterentropy-base.c b/random/jitterentropy-base.c index a5cf160b..30109dc1 100644 --- a/random/jitterentropy-base.c +++ b/random/jitterentropy-base.c @@ -1,793 +1,732 @@ /* * Non-physical true random number generator based on timing jitter. * - * Copyright Stephan Mueller , 2014 - 2017 + * Copyright Stephan Mueller , 2014 - 2021 * * Design * ====== * * See documentation in doc/ folder. * * Interface * ========= * - * See documentation in doc/ folder. - * - * License - * ======= - * - * 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, and the entire permission notice in its entirety, - * including the disclaimer of warranties. - * 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. - * 3. The name of the author may not be used to endorse or promote - * products derived from this software without specific prior - * written permission. + * See documentation in jitterentropy(3) man page. * - * ALTERNATIVELY, this product may be distributed under the terms of - * the GNU General Public License, in which case the provisions of the GPL2 are - * required INSTEAD OF the above restrictions. (This clause is - * necessary due to a potential bad interaction between the GPL and - * the restrictions contained in a BSD-style copyright.) + * License: see LICENSE file in root directory * * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ALL OF * WHICH ARE HEREBY 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 NOT ADVISED OF THE POSSIBILITY OF SUCH * DAMAGE. */ -#undef _FORTIFY_SOURCE -#ifdef __OPTIMIZE__ -#pragma GCC optimize ("O0") -#endif - #include "jitterentropy.h" -#ifndef CONFIG_CRYPTO_CPU_JITTERENTROPY_STAT - /* only check optimization in a compilation for real work */ - #ifdef __OPTIMIZE__ - #error "The CPU Jitter random number generator must not be compiled with optimizations. See documentation. Use the compiler switch -O0 for compiling jitterentropy-base.c." - #endif -#endif +#include "jitterentropy-base.h" +#include "jitterentropy-gcd.h" +#include "jitterentropy-health.h" +#include "jitterentropy-noise.h" +#include "jitterentropy-timer.h" +#include "jitterentropy-sha3.h" -#define MAJVERSION 2 /* API / ABI incompatible changes, functional changes that +#define MAJVERSION 3 /* API / ABI incompatible changes, functional changes that * require consumer to be updated (as long as this number * is zero, the API is not considered stable and can * change without a bump of the major version) */ -#define MINVERSION 1 /* API compatible, ABI may change, functional +#define MINVERSION 3 /* API compatible, ABI may change, functional * enhancements only, consumer can be left unchanged if * enhancements are not considered */ #define PATCHLEVEL 0 /* API / ABI compatible, no functional changes, no * enhancements, bug fixes only */ +/*************************************************************************** + * Jitter RNG Static Definitions + * + * None of the following should be altered + ***************************************************************************/ + +#ifdef __OPTIMIZE__ + #error "The CPU Jitter random number generator must not be compiled with optimizations. See documentation. Use the compiler switch -O0 for compiling jitterentropy.c." +#endif + +/* + * JENT_POWERUP_TESTLOOPCOUNT needs some loops to identify edge + * systems. 100 is definitely too little. + * + * SP800-90B requires at least 1024 initial test cycles. + */ +#define JENT_POWERUP_TESTLOOPCOUNT 1024 + /** * jent_version() - Return machine-usable version number of jent library * * The function returns a version number that is monotonic increasing * for newer versions. The version numbers are multiples of 100. For example, * version 1.2.3 is converted to 1020300 -- the last two digits are reserved * for future use. * * The result of this function can be used in comparing the version number * in a calling program if version-specific calls need to be make. * - * Return: Version number of kcapi library + * @return Version number of jitterentropy library */ JENT_PRIVATE_STATIC unsigned int jent_version(void) { unsigned int version = 0; version = MAJVERSION * 1000000; version += MINVERSION * 10000; version += PATCHLEVEL * 100; return version; } -/** - * Update of the loop count used for the next round of - * an entropy collection. - * - * Input: - * @ec entropy collector struct -- may be NULL - * @bits is the number of low bits of the timer to consider - * @min is the number of bits we shift the timer value to the right at - * the end to make sure we have a guaranteed minimum value - * - * @return Newly calculated loop counter - */ -static uint64_t jent_loop_shuffle(struct rand_data *ec, - unsigned int bits, unsigned int min) -{ - uint64_t time = 0; - uint64_t shuffle = 0; - unsigned int i = 0; - unsigned int mask = (1<data; - /* - * We fold the time value as much as possible to ensure that as many - * bits of the time stamp are included as possible. - */ - for (i = 0; (DATA_SIZE_BITS / bits) > i; i++) { - shuffle ^= time & mask; - time = time >> bits; - } - - /* - * We add a lower boundary value to ensure we have a minimum - * RNG loop count. - */ - return (shuffle + (1<data - * - * @return Number of loops the folding operation is performed - */ -static uint64_t jent_lfsr_time(struct rand_data *ec, uint64_t time, - uint64_t loop_cnt) +/* Calculate log2 of given value assuming that the value is a power of 2 */ +static inline unsigned int jent_log2_simple(unsigned int val) { - unsigned int i; - uint64_t j = 0; - uint64_t new = 0; -#define MAX_FOLD_LOOP_BIT 4 -#define MIN_FOLD_LOOP_BIT 0 - uint64_t fold_loop_cnt = - jent_loop_shuffle(ec, MAX_FOLD_LOOP_BIT, MIN_FOLD_LOOP_BIT); - - /* - * testing purposes -- allow test app to set the counter, not - * needed during runtime - */ - if (loop_cnt) - fold_loop_cnt = loop_cnt; - for (j = 0; j < fold_loop_cnt; j++) { - new = ec->data; - for (i = 1; (DATA_SIZE_BITS) >= i; i++) { - uint64_t tmp = time << (DATA_SIZE_BITS - i); - - tmp = tmp >> (DATA_SIZE_BITS - 1); + unsigned int idx = 0; - /* - * Fibonacci LSFR with polynomial of - * x^64 + x^61 + x^56 + x^31 + x^28 + x^23 + 1 which is - * primitive according to - * http://poincare.matf.bg.ac.rs/~ezivkovm/publications/primpol1.pdf - * (the shift values are the polynomial values minus one - * due to counting bits from 0 to 63). As the current - * position is always the LSB, the polynomial only needs - * to shift data in from the left without wrap. - */ - new ^= tmp; - new ^= ((new >> 63) & 1); - new ^= ((new >> 60) & 1); - new ^= ((new >> 55) & 1); - new ^= ((new >> 30) & 1); - new ^= ((new >> 27) & 1); - new ^= ((new >> 22) & 1); - new = rol64(new, 1); - } - } - ec->data = new; - - return fold_loop_cnt; + while (val >>= 1) + idx++; + return idx; } -/** - * Memory Access noise source -- this is a noise source based on variations in - * memory access times - * - * This function performs memory accesses which will add to the timing - * variations due to an unknown amount of CPU wait states that need to be - * added when accessing memory. The memory size should be larger than the L1 - * caches as outlined in the documentation and the associated testing. - * - * The L1 cache has a very high bandwidth, albeit its access rate is usually - * slower than accessing CPU registers. Therefore, L1 accesses only add minimal - * variations as the CPU has hardly to wait. Starting with L2, significant - * variations are added because L2 typically does not belong to the CPU any more - * and therefore a wider range of CPU wait states is necessary for accesses. - * L3 and real memory accesses have even a wider range of wait states. However, - * to reliably access either L3 or memory, the ec->mem memory must be quite - * large which is usually not desirable. - * - * Input: - * @ec Reference to the entropy collector with the memory access data -- if - * the reference to the memory block to be accessed is NULL, this noise - * source is disabled - * @loop_cnt if a value not equal to 0 is set, use the given value as number of - * loops to perform the folding - * - * @return Number of memory access operations - */ -static unsigned int jent_memaccess(struct rand_data *ec, uint64_t loop_cnt) +/* Increase the memory size by one step */ +static inline unsigned int jent_update_memsize(unsigned int flags) { - unsigned int wrap = 0; - uint64_t i = 0; -#define MAX_ACC_LOOP_BIT 7 -#define MIN_ACC_LOOP_BIT 0 - uint64_t acc_loop_cnt = - jent_loop_shuffle(ec, MAX_ACC_LOOP_BIT, MIN_ACC_LOOP_BIT); + unsigned int global_max = JENT_FLAGS_TO_MAX_MEMSIZE( + JENT_MAX_MEMSIZE_MAX); + unsigned int max; - if (NULL == ec || NULL == ec->mem) - return 0; - wrap = ec->memblocksize * ec->memblocks; - - /* - * testing purposes -- allow test app to set the counter, not - * needed during runtime - */ - if (loop_cnt) - acc_loop_cnt = loop_cnt; + max = JENT_FLAGS_TO_MAX_MEMSIZE(flags); - for (i = 0; i < (ec->memaccessloops + acc_loop_cnt); i++) { - unsigned char *tmpval = ec->mem + ec->memlocation; - /* - * memory access: just add 1 to one byte, - * wrap at 255 -- memory access implies read - * from and write to memory location - */ - *tmpval = (*tmpval + 1) & 0xff; + if (!max) { /* - * Addition of memblocksize - 1 to pointer - * with wrap around logic to ensure that every - * memory location is hit evenly + * The safe starting value is the amount of memory we allocated + * last round. */ - ec->memlocation = ec->memlocation + ec->memblocksize - 1; - ec->memlocation = ec->memlocation % wrap; + max = jent_log2_simple(JENT_MEMORY_SIZE); + /* Adjust offset */ + max = (max > JENT_MAX_MEMSIZE_OFFSET) ? + max - JENT_MAX_MEMSIZE_OFFSET : 0; + } else { + max++; } - return i; -} -/*************************************************************************** - * Start of entropy processing logic - ***************************************************************************/ + max = (max > global_max) ? global_max : max; -/** - * Stuck test by checking the: - * 1st derivation of the jitter measurement (time delta) - * 2nd derivation of the jitter measurement (delta of time deltas) - * 3rd derivation of the jitter measurement (delta of delta of time deltas) - * - * All values must always be non-zero. - * - * Input: - * @ec Reference to entropy collector - * @current_delta Jitter time delta - * - * @return - * 0 jitter measurement not stuck (good bit) - * 1 jitter measurement stuck (reject bit) - */ -static int jent_stuck(struct rand_data *ec, uint64_t current_delta) -{ - int64_t delta2 = ec->last_delta - current_delta; - int64_t delta3 = (uint64_t)delta2 - (uint64_t)ec->last_delta2; - - ec->last_delta = current_delta; - ec->last_delta2 = delta2; + /* Clear out the max size */ + flags &= ~JENT_MAX_MEMSIZE_MASK; + /* Set the freshly calculated max size */ + flags |= JENT_MAX_MEMSIZE_TO_FLAGS(max); - if (!current_delta || !delta2 || !delta3) - return 1; - - return 0; + return flags; } -/** - * This is the heart of the entropy generation: calculate time deltas and - * use the CPU jitter in the time deltas. The jitter is injected into the - * entropy pool. - * - * WARNING: ensure that ->prev_time is primed before using the output - * of this function! This can be done by calling this function - * and not using its result. - * - * Input: - * @entropy_collector Reference to entropy collector - * - * @return: result of stuck test - */ -static int jent_measure_jitter(struct rand_data *ec) -{ - uint64_t time = 0; - uint64_t current_delta = 0; - int stuck; - - /* Invoke one noise source before time measurement to add variations */ - jent_memaccess(ec, 0); - - /* - * Get time stamp and calculate time delta to previous - * invocation to measure the timing variations - */ - jent_get_nstime(&time); - current_delta = time - ec->prev_time; - ec->prev_time = time; - - /* Now call the next noise sources which also injects the data */ - jent_lfsr_time(ec, current_delta, 0); - - /* Check whether we have a stuck measurement. */ - stuck = jent_stuck(ec, current_delta); - - /* - * Rotate the data buffer by a prime number (any odd number would - * do) to ensure that every bit position of the input time stamp - * has an even chance of being merged with a bit position in the - * entropy pool. We do not use one here as the adjacent bits in - * successive time deltas may have some form of dependency. The - * chosen value of 7 implies that the low 7 bits of the next - * time delta value is concatenated with the current time delta. - */ - if (!stuck) - ec->data = rol64(ec->data, 7); - - return stuck; -} - -/** - * Shuffle the pool a bit by mixing some value with a bijective function (XOR) - * into the pool. - * - * The function generates a mixer value that depends on the bits set and the - * location of the set bits in the random number generated by the entropy - * source. Therefore, based on the generated random number, this mixer value - * can have 2**64 different values. That mixer value is initialized with the - * first two SHA-1 constants. After obtaining the mixer value, it is XORed into - * the random number. - * - * The mixer value is not assumed to contain any entropy. But due to the XOR - * operation, it can also not destroy any entropy present in the entropy pool. - * - * Input: - * @entropy_collector Reference to entropy collector - */ -static void jent_stir_pool(struct rand_data *entropy_collector) -{ - /* - * to shut up GCC on 32 bit, we have to initialize the 64 variable - * with two 32 bit variables - */ - union c { - uint64_t uint64; - uint32_t uint32[2]; - }; - /* - * This constant is derived from the first two 32 bit initialization - * vectors of SHA-1 as defined in FIPS 180-4 section 5.3.1 - */ - union c constant; - /* - * The start value of the mixer variable is derived from the third - * and fourth 32 bit initialization vector of SHA-1 as defined in - * FIPS 180-4 section 5.3.1 - */ - union c mixer; - unsigned int i = 0; - - /* Ensure that the function implements a constant time operation. */ - union c throw_away; - - /* - * Store the SHA-1 constants in reverse order to make up the 64 bit - * value -- this applies to a little endian system, on a big endian - * system, it reverses as expected. But this really does not matter - * as we do not rely on the specific numbers. We just pick the SHA-1 - * constants as they have a good mix of bit set and unset. - */ - constant.uint32[1] = 0x67452301; - constant.uint32[0] = 0xefcdab89; - mixer.uint32[1] = 0x98badcfe; - mixer.uint32[0] = 0x10325476; - - for (i = 0; i < DATA_SIZE_BITS; i++) { - /* - * get the i-th bit of the input random number and only XOR - * the constant into the mixer value when that bit is set - */ - if ((entropy_collector->data >> i) & 1) - mixer.uint64 ^= constant.uint64; - else - throw_away.uint64 ^= constant.uint64; - mixer.uint64 = rol64(mixer.uint64, 1); - } - entropy_collector->data ^= mixer.uint64; -} - -/** - * Generator of one 64 bit random number - * Function fills rand_data->data - * - * Input: - * @ec Reference to entropy collector - */ -static void jent_gen_entropy(struct rand_data *ec) -{ - unsigned int k = 0; - - /* priming of the ->prev_time value */ - jent_measure_jitter(ec); - - while (1) { - /* If a stuck measurement is received, repeat measurement */ - if (jent_measure_jitter(ec)) - continue; - - /* - * We multiply the loop value with ->osr to obtain the - * oversampling rate requested by the caller - */ - if (++k >= (DATA_SIZE_BITS * ec->osr)) - break; - } - if (ec->stir) - jent_stir_pool(ec); -} - -/** - * The continuous test required by FIPS 140-2 -- the function automatically - * primes the test if needed. - * - * Return: - * 0 if FIPS test passed - * < 0 if FIPS test failed - */ -static int jent_fips_test(struct rand_data *ec) -{ - if (ec->fips_enabled == -1) - return 0; - - if (ec->fips_enabled == 0) { - if (!jent_fips_enabled()) { - ec->fips_enabled = -1; - return 0; - } else - ec->fips_enabled = 1; - } - - /* prime the FIPS test */ - if (!ec->old_data) { - ec->old_data = ec->data; - jent_gen_entropy(ec); - } - - if (ec->data == ec->old_data) - return -1; - - ec->old_data = ec->data; - - return 0; -} +/*************************************************************************** + * Random Number Generation + ***************************************************************************/ /** * Entry function: Obtain entropy for the caller. * * This function invokes the entropy gathering logic as often to generate * as many bytes as requested by the caller. The entropy gathering logic * creates 64 bit per invocation. * * This function truncates the last 64 bit entropy value output to the exact * size specified by the caller. * - * Input: - * @ec Reference to entropy collector - * @data pointer to buffer for storing random data -- buffer must already - * exist - * @len size of the buffer, specifying also the requested number of random - * in bytes + * @ec [in] Reference to entropy collector + * @data [out] pointer to buffer for storing random data -- buffer must + * already exist + * @len [in] size of the buffer, specifying also the requested number of random + * in bytes * * @return number of bytes returned when request is fulfilled or an error * * The following error codes can occur: * -1 entropy_collector is NULL - * -2 FIPS test failed + * -2 RCT failed + * -3 APT test failed + * -4 The timer cannot be initialized + * -5 LAG failure */ JENT_PRIVATE_STATIC ssize_t jent_read_entropy(struct rand_data *ec, char *data, size_t len) { char *p = data; size_t orig_len = len; + int ret = 0; if (NULL == ec) return -1; - while (0 < len) { + if (jent_notime_settick(ec)) + return -4; + + while (len > 0) { size_t tocopy; + unsigned int health_test_result; - jent_gen_entropy(ec); - if (jent_fips_test(ec)) - return -2; + jent_random_data(ec); + + if ((health_test_result = jent_health_failure(ec))) { + if (health_test_result & JENT_RCT_FAILURE) + ret = -2; + else if (health_test_result & JENT_APT_FAILURE) + ret = -3; + else + ret = -5; + + goto err; + } if ((DATA_SIZE_BITS / 8) < len) tocopy = (DATA_SIZE_BITS / 8); else tocopy = len; memcpy(p, &ec->data, tocopy); len -= tocopy; p += tocopy; } /* * To be on the safe side, we generate one more round of entropy * which we do not give out to the caller. That round shall ensure * that in case the calling application crashes, memory dumps, pages * out, or due to the CPU Jitter RNG lingering in memory for long * time without being moved and an attacker cracks the application, * all he reads in the entropy pool is a value that is NEVER EVER * being used for anything. Thus, he does NOT see the previous value * that was returned to the caller for cryptographic purposes. */ /* * If we use secured memory, do not use that precaution as the secure * memory protects the entropy pool. Moreover, note that using this * call reduces the speed of the RNG by up to half */ #ifndef CONFIG_CRYPTO_CPU_JITTERENTROPY_SECURE_MEMORY - jent_gen_entropy(ec); + jent_random_data(ec); #endif - return orig_len; + +err: + jent_notime_unsettick(ec); + return ret ? ret : (ssize_t)orig_len; +} + +static struct rand_data *_jent_entropy_collector_alloc(unsigned int osr, + unsigned int flags); + +/** + * Entry function: Obtain entropy for the caller. + * + * This is a service function to jent_read_entropy() with the difference + * that it automatically re-allocates the entropy collector if a health + * test failure is observed. Before reallocation, a new power-on health test + * is performed. The allocation of the new entropy collector automatically + * increases the OSR by one. This is done based on the idea that a health + * test failure indicates that the assumed entropy rate is too high. + * + * Note the function returns with an health test error if the OSR is + * getting too large. If an error is returned by this function, the Jitter RNG + * is not safe to be used on the current system. + * + * @ec [in] Reference to entropy collector - this is a double pointer as + * The entropy collector may be freed and reallocated. + * @data [out] pointer to buffer for storing random data -- buffer must + * already exist + * @len [in] size of the buffer, specifying also the requested number of random + * in bytes + * + * @return see jent_read_entropy() + */ +JENT_PRIVATE_STATIC +ssize_t jent_read_entropy_safe(struct rand_data **ec, char *data, size_t len) +{ + char *p = data; + size_t orig_len = len; + ssize_t ret = 0; + + if (!ec) + return -1; + + while (len > 0) { + unsigned int osr, flags, max_mem_set; + + ret = jent_read_entropy(*ec, p, len); + + switch (ret) { + case -1: + case -4: + return ret; + case -2: + case -3: + case -5: + osr = (*ec)->osr + 1; + flags = (*ec)->flags; + max_mem_set = (*ec)->max_mem_set; + + /* generic arbitrary cutoff */ + if (osr > 20) + return ret; + + /* + * If the caller did not set any specific maximum value + * let the Jitter RNG increase the maximum memory by + * one step. + */ + if (!max_mem_set) + flags = jent_update_memsize(flags); + + /* + * re-allocate entropy collector with higher OSR and + * memory size + */ + jent_entropy_collector_free(*ec); + + /* Perform new health test with updated OSR */ + if (jent_entropy_init_ex(osr, flags)) + return -1; + + *ec = _jent_entropy_collector_alloc(osr, flags); + if (!*ec) + return -1; + + /* Remember whether caller configured memory size */ + (*ec)->max_mem_set = !!max_mem_set; + + break; + + default: + len -= (size_t)ret; + p += (size_t)ret; + } + } + + return (ssize_t)orig_len; } /*************************************************************************** * Initialization logic ***************************************************************************/ -JENT_PRIVATE_STATIC -struct rand_data *jent_entropy_collector_alloc(unsigned int osr, - unsigned int flags) +/* + * Obtain memory size to allocate for memory access variations. + * + * The maximum variations we can get from the memory access is when we allocate + * a bit more memory than we have as data cache. But allocating as much + * memory as we have as data cache might strain the resources on the system + * more than necessary. + * + * On a lot of systems it is not necessary to need so much memory as the + * variations coming from the general Jitter RNG execution commonly provide + * large amount of variations. + * + * Thus, the default is: + * + * min(JENT_MEMORY_SIZE, data cache size) + * + * In case the data cache size cannot be obtained, use JENT_MEMORY_SIZE. + * + * If the caller provides a maximum memory size, use + * min(provided max memory, data cache size). + */ +static inline uint32_t jent_memsize(unsigned int flags) +{ + uint32_t memsize, max_memsize; + + max_memsize = JENT_FLAGS_TO_MAX_MEMSIZE(flags); + + if (max_memsize == 0) { + max_memsize = JENT_MEMORY_SIZE; + } else { + max_memsize = UINT32_C(1) << (max_memsize + + JENT_MAX_MEMSIZE_OFFSET); + } + + /* Allocate memory for adding variations based on memory access */ + memsize = jent_cache_size_roundup(); + + /* Limit the memory as defined by caller */ + memsize = (memsize > max_memsize) ? max_memsize : memsize; + + /* Set a value if none was found */ + if (!memsize) + memsize = JENT_MEMORY_SIZE; + + return memsize; +} + +static int jent_selftest_run = 0; + +static struct rand_data +*jent_entropy_collector_alloc_internal(unsigned int osr, unsigned int flags) { struct rand_data *entropy_collector; + /* + * Requesting disabling and forcing of internal timer + * makes no sense. + */ + if ((flags & JENT_DISABLE_INTERNAL_TIMER) && + (flags & JENT_FORCE_INTERNAL_TIMER)) + return NULL; + + /* Force the self test to be run */ + if (!jent_selftest_run && jent_entropy_init_ex(osr, flags)) + return NULL; + + /* + * If the initial test code concludes to force the internal timer + * and the user requests it not to be used, do not allocate + * the Jitter RNG instance. + */ + if (jent_notime_forced() && (flags & JENT_DISABLE_INTERNAL_TIMER)) + return NULL; + entropy_collector = jent_zalloc(sizeof(struct rand_data)); if (NULL == entropy_collector) return NULL; if (!(flags & JENT_DISABLE_MEMORY_ACCESS)) { - /* Allocate memory for adding variations based on memory - * access + uint32_t memsize = jent_memsize(flags); + + entropy_collector->mem = (unsigned char *)jent_zalloc(memsize); + +#ifdef JENT_RANDOM_MEMACCESS + /* + * Transform the size into a mask - it is assumed that size is + * a power of 2. */ - entropy_collector->mem = - (unsigned char *)jent_zalloc(JENT_MEMORY_SIZE); - if (NULL == entropy_collector->mem) { - jent_zfree(entropy_collector, sizeof(struct rand_data)); - return NULL; - } - entropy_collector->memblocksize = JENT_MEMORY_BLOCKSIZE; + entropy_collector->memmask = memsize - 1; +#else /* JENT_RANDOM_MEMACCESS */ + entropy_collector->memblocksize = memsize / JENT_MEMORY_BLOCKS; entropy_collector->memblocks = JENT_MEMORY_BLOCKS; + + /* sanity check */ + if (entropy_collector->memblocksize * + entropy_collector->memblocks != memsize) + goto err; + +#endif /* JENT_RANDOM_MEMACCESS */ + + if (entropy_collector->mem == NULL) + goto err; entropy_collector->memaccessloops = JENT_MEMORY_ACCESSLOOPS; } /* verify and set the oversampling rate */ - if (0 == osr) - osr = 1; /* minimum sampling rate is 1 */ + if (osr < JENT_MIN_OSR) + osr = JENT_MIN_OSR; entropy_collector->osr = osr; + entropy_collector->flags = flags; - entropy_collector->stir = 1; - if (flags & JENT_DISABLE_STIR) - entropy_collector->stir = 0; - if (flags & JENT_DISABLE_UNBIAS) - entropy_collector->disable_unbias = 1; + if (jent_fips_enabled() || (flags & JENT_FORCE_FIPS)) + entropy_collector->fips_enabled = 1; - /* fill the data pad with non-zero values */ - jent_gen_entropy(entropy_collector); + /* Initialize the APT */ + jent_apt_init(entropy_collector, osr); + + /* Initialize the Lag Predictor Test */ + jent_lag_init(entropy_collector, osr); + + /* Was jent_entropy_init run (establishing the common GCD)? */ + if (jent_gcd_get(&entropy_collector->jent_common_timer_gcd)) { + /* + * It was not. This should probably be an error, but this + * behavior breaks the test code. Set the gcd to a value that + * won't hurt anything. + */ + entropy_collector->jent_common_timer_gcd = 1; + } + + /* + * Use timer-less noise source - note, OSR must be set in + * entropy_collector! + */ + if (!(flags & JENT_DISABLE_INTERNAL_TIMER)) { + if (jent_notime_enable(entropy_collector, flags)) + goto err; + } return entropy_collector; + +err: + if (entropy_collector->mem != NULL) + jent_zfree(entropy_collector->mem, JENT_MEMORY_SIZE); + jent_zfree(entropy_collector, sizeof(struct rand_data)); + return NULL; +} + +static struct rand_data *_jent_entropy_collector_alloc(unsigned int osr, + unsigned int flags) +{ + struct rand_data *ec = jent_entropy_collector_alloc_internal(osr, + flags); + + if (!ec) + return ec; + + /* fill the data pad with non-zero values */ + if (jent_notime_settick(ec)) { + jent_entropy_collector_free(ec); + return NULL; + } + jent_random_data(ec); + jent_notime_unsettick(ec); + + return ec; +} + +JENT_PRIVATE_STATIC +struct rand_data *jent_entropy_collector_alloc(unsigned int osr, + unsigned int flags) +{ + struct rand_data *ec = _jent_entropy_collector_alloc(osr, flags); + + /* Remember that the caller provided a maximum size flag */ + if (ec) + ec->max_mem_set = !!JENT_FLAGS_TO_MAX_MEMSIZE(flags); + + return ec; } JENT_PRIVATE_STATIC void jent_entropy_collector_free(struct rand_data *entropy_collector) { - if (NULL != entropy_collector) { - if (NULL != entropy_collector->mem) { - jent_zfree(entropy_collector->mem, JENT_MEMORY_SIZE); + if (entropy_collector != NULL) { + jent_notime_disable(entropy_collector); + if (entropy_collector->mem != NULL) { + jent_zfree(entropy_collector->mem, + jent_memsize(entropy_collector->flags)); entropy_collector->mem = NULL; } jent_zfree(entropy_collector, sizeof(struct rand_data)); } } -JENT_PRIVATE_STATIC -int jent_entropy_init(void) +int jent_time_entropy_init(unsigned int osr, unsigned int flags) { - int i; - uint64_t delta_sum = 0; - uint64_t old_delta = 0; - int time_backwards = 0; - int count_mod = 0; - int count_stuck = 0; - struct rand_data ec; + struct rand_data *ec; + uint64_t *delta_history; + int i, time_backwards = 0, count_stuck = 0, ret = 0; + unsigned int health_test_result; + + delta_history = jent_gcd_init(JENT_POWERUP_TESTLOOPCOUNT); + if (!delta_history) + return EMEM; + + if (flags & JENT_FORCE_INTERNAL_TIMER) + jent_notime_force(); + else + flags |= JENT_DISABLE_INTERNAL_TIMER; - memset(&ec, 0, sizeof(ec)); + /* + * If the start-up health tests (including the APT and RCT) are not + * run, then the entropy source is not 90B compliant. We could test if + * fips_enabled should be set using the jent_fips_enabled() function, + * but this can be overridden using the JENT_FORCE_FIPS flag, which + * isn't passed in yet. It is better to run the tests on the small + * amount of data that we have, which should not fail unless things + * are really bad. + */ + flags |= JENT_FORCE_FIPS; + ec = jent_entropy_collector_alloc_internal(osr, flags); + if (!ec) { + ret = EMEM; + goto out; + } + + if (jent_notime_settick(ec)) { + ret = EMEM; + goto out; + } + + /* To initialize the prior time. */ + jent_measure_jitter(ec, 0, NULL); /* We could perform statistical tests here, but the problem is * that we only have a few loop counts to do testing. These - * loop counts may show some slight skew and we produce - * false positives. - * - * Moreover, only old systems show potentially problematic - * jitter entropy that could potentially be caught here. But - * the RNG is intended for hardware that is available or widely - * used, but not old systems that are long out of favor. Thus, - * no statistical tests. + * loop counts may show some slight skew leading to false positives. */ /* * We could add a check for system capabilities such as clock_getres or * check for CONFIG_X86_TSC, but it does not make much sense as the * following sanity checks verify that we have a high-resolution * timer. */ - /* - * TESTLOOPCOUNT needs some loops to identify edge systems. 100 is - * definitely too little. - */ -#define TESTLOOPCOUNT 300 #define CLEARCACHE 100 - for (i = 0; (TESTLOOPCOUNT + CLEARCACHE) > i; i++) { - uint64_t time = 0; - uint64_t time2 = 0; - uint64_t delta = 0; - unsigned int lowdelta = 0; - int stuck; + for (i = -CLEARCACHE; i < JENT_POWERUP_TESTLOOPCOUNT; i++) { + uint64_t start_time = 0, end_time = 0, delta = 0; + unsigned int stuck; /* Invoke core entropy collection logic */ - jent_get_nstime(&time); - ec.prev_time = time; - jent_lfsr_time(&ec, time, 0); - jent_get_nstime(&time2); + stuck = jent_measure_jitter(ec, 0, &delta); + end_time = ec->prev_time; + start_time = ec->prev_time - delta; /* test whether timer works */ - if (!time || !time2) - return ENOTIME; - delta = time2 - time; + if (!start_time || !end_time) { + ret = ENOTIME; + goto out; + } + /* * test whether timer is fine grained enough to provide * delta even when called shortly after each other -- this * implies that we also have a high resolution timer */ - if (!delta) - return ECOARSETIME; - - stuck = jent_stuck(&ec, delta); + if (!delta || (end_time == start_time)) { + ret = ECOARSETIME; + goto out; + } /* * up to here we did not modify any variable that will be * evaluated later, but we already performed some work. Thus we * already have had an impact on the caches, branch prediction, * etc. with the goal to clear it to get the worst case * measurements. */ - if (CLEARCACHE > i) + if (i < 0) continue; if (stuck) count_stuck++; /* test whether we have an increasing timer */ - if (!(time2 > time)) + if (!(end_time > start_time)) time_backwards++; - /* use 32 bit value to ensure compilation on 32 bit arches */ - lowdelta = time2 - time; - if (!(lowdelta % 100)) - count_mod++; - - /* - * ensure that we have a varying delta timer which is necessary - * for the calculation of entropy -- perform this check - * only after the first loop is executed as we need to prime - * the old_data value - */ - if (delta > old_delta) - delta_sum += (delta - old_delta); - else - delta_sum += (old_delta - delta); - old_delta = delta; + /* Watch for common adjacent GCD values */ + jent_gcd_add_value(delta_history, delta, i); } /* * we allow up to three times the time running backwards. * CLOCK_REALTIME is affected by adjtime and NTP operations. Thus, * if such an operation just happens to interfere with our test, it * should not fail. The value of 3 should cover the NTP case being * performed during our test run. */ - if (3 < time_backwards) - return ENOMONOTONIC; + if (time_backwards > 3) { + ret = ENOMONOTONIC; + goto out; + } - /* - * Variations of deltas of time must on average be larger - * than 1 to ensure the entropy estimation - * implied with 1 is preserved - */ - if ((delta_sum) <= 1) - return EMINVARVAR; + /* First, did we encounter a health test failure? */ + if ((health_test_result = jent_health_failure(ec))) { + ret = (health_test_result & JENT_RCT_FAILURE) ? ERCT : EHEALTH; + goto out; + } - /* - * Ensure that we have variations in the time stamp below 10 for at least - * 10% of all checks -- on some platforms, the counter increments in - * multiples of 100, but not always - */ - if ((TESTLOOPCOUNT/10 * 9) < count_mod) - return ECOARSETIME; + ret = jent_gcd_analyze(delta_history, JENT_POWERUP_TESTLOOPCOUNT); + if (ret) + goto out; /* * If we have more than 90% stuck results, then this Jitter RNG is * likely to not work well. */ - if (JENT_STUCK_INIT_THRES(TESTLOOPCOUNT) < count_stuck) - return ESTUCK; + if (JENT_STUCK_INIT_THRES(JENT_POWERUP_TESTLOOPCOUNT) < count_stuck) + ret = ESTUCK; + +out: + jent_gcd_fini(delta_history, JENT_POWERUP_TESTLOOPCOUNT); + + if ((flags & JENT_FORCE_INTERNAL_TIMER) && ec) + jent_notime_unsettick(ec); - return 0; + jent_entropy_collector_free(ec); + + return ret; } -/*************************************************************************** - * Statistical test logic not compiled for regular operation - ***************************************************************************/ +static inline int jent_entropy_init_common_pre(void) +{ + int ret; + + jent_notime_block_switch(); + + if (sha3_tester()) + return EHASH; + + ret = jent_gcd_selftest(); + + jent_selftest_run = 1; + + return ret; +} + +static inline int jent_entropy_init_common_post(int ret) +{ + /* Unmark the execution of the self tests if they failed. */ + if (ret) + jent_selftest_run = 0; + + return ret; +} + +JENT_PRIVATE_STATIC +int jent_entropy_init(void) +{ + int ret = jent_entropy_init_common_pre(); + + if (ret) + return ret; + + ret = jent_time_entropy_init(0, JENT_DISABLE_INTERNAL_TIMER); + +#ifdef JENT_CONF_ENABLE_INTERNAL_TIMER + if (ret) + ret = jent_time_entropy_init(0, JENT_FORCE_INTERNAL_TIMER); +#endif /* JENT_CONF_ENABLE_INTERNAL_TIMER */ + + return jent_entropy_init_common_post(ret); +} + +JENT_PRIVATE_STATIC +int jent_entropy_init_ex(unsigned int osr, unsigned int flags) +{ + int ret = jent_entropy_init_common_pre(); + + if (ret) + return ret; + + /* Test without internal timer unless caller does not want it */ + if (!(flags & JENT_FORCE_INTERNAL_TIMER)) + ret = jent_time_entropy_init(osr, + flags | JENT_DISABLE_INTERNAL_TIMER); + +#ifdef JENT_CONF_ENABLE_INTERNAL_TIMER + /* Test with internal timer unless caller does not want it */ + if (ret && !(flags & JENT_DISABLE_INTERNAL_TIMER)) + ret = jent_time_entropy_init(osr, + flags | JENT_FORCE_INTERNAL_TIMER); +#endif /* JENT_CONF_ENABLE_INTERNAL_TIMER */ + + return jent_entropy_init_common_post(ret); +} -#ifdef CONFIG_CRYPTO_CPU_JITTERENTROPY_STAT -/* - * Statistical test: return the time duration for the folding operation. If min - * is set, perform the given number of LFSR ops. Otherwise, allow the - * loop count shuffling to define the number of LFSR ops. - */ JENT_PRIVATE_STATIC -uint64_t jent_lfsr_var_stat(struct rand_data *ec, unsigned int min) +int jent_entropy_switch_notime_impl(struct jent_notime_thread *new_thread) { - uint64_t time = 0; - uint64_t time2 = 0; - - jent_get_nstime(&time); - jent_memaccess(ec, min); - jent_lfsr_time(ec, time, min); - jent_get_nstime(&time2); - return ((time2 - time)); + return jent_notime_switch(new_thread); } -#endif /* CONFIG_CRYPTO_CPU_JITTERENTROPY_STAT */ diff --git a/random/jitterentropy-base.h b/random/jitterentropy-base.h new file mode 100644 index 00000000..85d417cc --- /dev/null +++ b/random/jitterentropy-base.h @@ -0,0 +1,34 @@ +/* + * Copyright (C) 2021, Stephan Mueller + * + * License: see LICENSE file in root directory + * + * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED + * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ALL OF + * WHICH ARE HEREBY 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 NOT ADVISED OF THE POSSIBILITY OF SUCH + * DAMAGE. + */ + +#ifndef JITTERENTROPY_BASE_H +#define JITTERENTROPY_BASE_H + +#ifdef __cplusplus +extern "C" +{ +#endif + +int jent_time_entropy_init(unsigned int osr, unsigned int flags); + +#ifdef __cplusplus +} +#endif + +#endif /* JITTERENTROPY_BASE_H */ diff --git a/random/jitterentropy-gcd.c b/random/jitterentropy-gcd.c new file mode 100644 index 00000000..aa9c6797 --- /dev/null +++ b/random/jitterentropy-gcd.c @@ -0,0 +1,188 @@ +/* Jitter RNG: GCD health test + * + * Copyright (C) 2021, Joshua E. Hill + * Copyright (C) 2021, Stephan Mueller + * + * License: see LICENSE file in root directory + * + * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED + * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ALL OF + * WHICH ARE HEREBY 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 NOT ADVISED OF THE POSSIBILITY OF SUCH + * DAMAGE. + */ + +#include "jitterentropy.h" +#include "jitterentropy-gcd.h" + +/* The common divisor for all timestamp deltas */ +static uint64_t jent_common_timer_gcd = 0; + +static inline int jent_gcd_tested(void) +{ + return (jent_common_timer_gcd != 0); +} + +/* A straight forward implementation of the Euclidean algorithm for GCD. */ +static inline uint64_t jent_gcd64(uint64_t a, uint64_t b) +{ + /* Make a greater a than or equal b. */ + if (a < b) { + uint64_t c = a; + a = b; + b = c; + } + + /* Now perform the standard inner-loop for this algorithm.*/ + while (b != 0) { + uint64_t r; + + r = a % b; + + a = b; + b = r; + } + + return a; +} + +static int jent_gcd_analyze_internal(uint64_t *delta_history, size_t nelem, + uint64_t *running_gcd_out, + uint64_t *delta_sum_out) +{ + uint64_t running_gcd, delta_sum = 0; + size_t i; + + if (!delta_history) + return -EAGAIN; + + running_gcd = delta_history[0]; + + /* Now perform the analysis on the accumulated delta data. */ + for (i = 1; i < nelem; i++) { + /* + * ensure that we have a varying delta timer which is necessary + * for the calculation of entropy -- perform this check + * only after the first loop is executed as we need to prime + * the old_data value + */ + if (delta_history[i] >= delta_history[i - 1]) + delta_sum += delta_history[i] - delta_history[i - 1]; + else + delta_sum += delta_history[i - 1] - delta_history[i]; + + /* + * This calculates the gcd of all the delta values. that is + * gcd(delta_1, delta_2, ..., delta_nelem) + + * Some timers increment by a fixed (non-1) amount each step. + * This code checks for such increments, and allows the library + * to output the number of such changes have occurred. + */ + running_gcd = jent_gcd64(delta_history[i], running_gcd); + } + + *running_gcd_out = running_gcd; + *delta_sum_out = delta_sum; + + return 0; +} + +int jent_gcd_analyze(uint64_t *delta_history, size_t nelem) +{ + uint64_t running_gcd, delta_sum; + int ret = jent_gcd_analyze_internal(delta_history, nelem, &running_gcd, + &delta_sum); + + if (ret == -EAGAIN) + return 0; + + /* + * Variations of deltas of time must on average be larger than 1 to + * ensure the entropy estimation implied with 1 is preserved. + */ + if (delta_sum <= nelem - 1) { + ret = EMINVARVAR; + goto out; + } + + /* + * Ensure that we have variations in the time stamp below 100 for at + * least 10% of all checks -- on some platforms, the counter increments + * in multiples of 100, but not always + */ + if (running_gcd >= 100) { + ret = ECOARSETIME; + goto out; + } + + /* Adjust all deltas by the observed (small) common factor. */ + if (!jent_gcd_tested()) + jent_common_timer_gcd = running_gcd; + +out: + return ret; +} + +uint64_t *jent_gcd_init(size_t nelem) +{ + uint64_t *delta_history; + + delta_history = jent_zalloc(nelem * sizeof(uint64_t)); + if (!delta_history) + return NULL; + + return delta_history; +} + +void jent_gcd_fini(uint64_t *delta_history, size_t nelem) +{ + if (delta_history) + jent_zfree(delta_history, + (unsigned int)(nelem * sizeof(uint64_t))); +} + +int jent_gcd_get(uint64_t *value) +{ + if (!jent_gcd_tested()) + return 1; + + *value = jent_common_timer_gcd; + return 0; +} + +int jent_gcd_selftest(void) +{ +#define JENT_GCD_SELFTEST_ELEM 10 +#define JENT_GCD_SELFTEST_EXP 3ULL + uint64_t *gcd = jent_gcd_init(JENT_GCD_SELFTEST_ELEM); + uint64_t running_gcd, delta_sum; + unsigned int i; + int ret = EGCD; + + if (!gcd) + return EMEM; + + for (i = 0; i < JENT_GCD_SELFTEST_ELEM; i++) + jent_gcd_add_value(gcd, i * JENT_GCD_SELFTEST_EXP, i); + + if (jent_gcd_analyze_internal(gcd, JENT_GCD_SELFTEST_ELEM, + &running_gcd, &delta_sum)) + goto out; + + if (running_gcd != JENT_GCD_SELFTEST_EXP) + goto out; + + ret = 0; + +out: + jent_gcd_fini(gcd, JENT_GCD_SELFTEST_ELEM); + return ret; +} diff --git a/random/jitterentropy-gcd.h b/random/jitterentropy-gcd.h new file mode 100644 index 00000000..44599567 --- /dev/null +++ b/random/jitterentropy-gcd.h @@ -0,0 +1,42 @@ +/* + * Copyright (C) 2021, Stephan Mueller + * + * License: see LICENSE file in root directory + * + * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED + * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ALL OF + * WHICH ARE HEREBY 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 NOT ADVISED OF THE POSSIBILITY OF SUCH + * DAMAGE. + */ + +#ifndef JITTERENTROPY_GCD_H +#define JITTERENTROPY_GCD_H + +#ifdef __cplusplus +extern "C" +{ +#endif + +int jent_gcd_analyze(uint64_t *delta_history, size_t nelem); +uint64_t *jent_gcd_init(size_t nelem); +void jent_gcd_fini(uint64_t *delta_history, size_t nelem); +int jent_gcd_get(uint64_t *value); +int jent_gcd_selftest(void); + +/* Watch for common adjacent GCD values */ +#define jent_gcd_add_value(delta_history, delta, idx) \ + delta_history[idx] = delta; + +#ifdef __cplusplus +} +#endif + +#endif /* JITTERENTROPY_GCD_H */ diff --git a/random/jitterentropy-health.c b/random/jitterentropy-health.c new file mode 100644 index 00000000..a0b0e3e1 --- /dev/null +++ b/random/jitterentropy-health.c @@ -0,0 +1,438 @@ +/* Jitter RNG: Health Tests + * + * Copyright (C) 2021, Joshua E. Hill + * Copyright (C) 2021, Stephan Mueller + * + * License: see LICENSE file in root directory + * + * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED + * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ALL OF + * WHICH ARE HEREBY 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 NOT ADVISED OF THE POSSIBILITY OF SUCH + * DAMAGE. + */ + +#include "jitterentropy.h" +#include "jitterentropy-health.h" + +/*************************************************************************** + * Lag Predictor Test + * + * This test is a vendor-defined conditional test that is designed to detect + * a known failure mode where the result becomes mostly deterministic + * Note that (lag_observations & JENT_LAG_MASK) is the index where the next + * value provided will be stored. + ***************************************************************************/ + +#ifdef JENT_HEALTH_LAG_PREDICTOR + +/* + * These cutoffs are configured using an entropy estimate of 1/osr under an + * alpha=2^(-22) for a window size of 131072. The other health tests use + * alpha=2^-30, but operate on much smaller window sizes. This larger selection + * of alpha makes the behavior per-lag-window similar to the APT test. + * + * The global cutoffs are calculated using the + * InverseBinomialCDF(n=(JENT_LAG_WINDOW_SIZE-JENT_LAG_HISTORY_SIZE), p=2^(-1/osr); 1-alpha) + * The local cutoffs are somewhat more complicated. For background, see Feller's + * _Introduction to Probability Theory and It's Applications_ Vol. 1, + * Chapter 13, section 7 (in particular see equation 7.11, where x is a root + * of the denominator of equation 7.6). + * + * We'll proceed using the notation of SP 800-90B Section 6.3.8 (which is + * developed in Kelsey-McKay-Turan paper "Predictive Models for Min-entropy + * Estimation".) + * + * Here, we set p=2^(-1/osr), seeking a run of successful guesses (r) with + * probability of less than (1-alpha). That is, it is very very likely + * (probability 1-alpha) that there is _no_ run of length r in a block of size + * JENT_LAG_WINDOW_SIZE-JENT_LAG_HISTORY_SIZE. + * + * We have to iteratively look for an appropriate value for the cutoff r. + */ +static const unsigned int jent_lag_global_cutoff_lookup[20] = + { 66443, 93504, 104761, 110875, 114707, 117330, 119237, 120686, 121823, + 122739, 123493, 124124, 124660, 125120, 125520, 125871, 126181, 126457, + 126704, 126926 }; +static const unsigned int jent_lag_local_cutoff_lookup[20] = + { 38, 75, 111, 146, 181, 215, 250, 284, 318, 351, + 385, 419, 452, 485, 518, 551, 584, 617, 650, 683 }; + +void jent_lag_init(struct rand_data *ec, unsigned int osr) +{ + /* + * Establish the lag global and local cutoffs based on the presumed + * entropy rate of 1/osr. + */ + if (osr > ARRAY_SIZE(jent_lag_global_cutoff_lookup)) { + ec->lag_global_cutoff = + jent_lag_global_cutoff_lookup[ + ARRAY_SIZE(jent_lag_global_cutoff_lookup) - 1]; + } else { + ec->lag_global_cutoff = jent_lag_global_cutoff_lookup[osr - 1]; + } + + if (osr > ARRAY_SIZE(jent_lag_local_cutoff_lookup)) { + ec->lag_local_cutoff = + jent_lag_local_cutoff_lookup[ + ARRAY_SIZE(jent_lag_local_cutoff_lookup) - 1]; + } else { + ec->lag_local_cutoff = jent_lag_local_cutoff_lookup[osr - 1]; + } +} + +/** + * Reset the lag counters + * + * @ec [in] Reference to entropy collector + */ +static void jent_lag_reset(struct rand_data *ec) +{ + unsigned int i; + + /* Reset Lag counters */ + ec->lag_prediction_success_count = 0; + ec->lag_prediction_success_run = 0; + ec->lag_best_predictor = 0; //The first guess is basically arbitrary. + ec->lag_observations = 0; + + for (i = 0; i < JENT_LAG_HISTORY_SIZE; i++) { + ec->lag_scoreboard[i] = 0; + ec->lag_delta_history[i] = 0; + } +} + +/* + * A macro for accessing the history. Index 0 is the last observed symbol + * index 1 is the symbol observed two inputs ago, etc. + */ +#define JENT_LAG_HISTORY(EC,LOC) \ + ((EC)->lag_delta_history[((EC)->lag_observations - (LOC) - 1) & \ + JENT_LAG_MASK]) + +/** + * Insert a new entropy event into the lag predictor test + * + * @ec [in] Reference to entropy collector + * @current_delta [in] Current time delta + */ +static void jent_lag_insert(struct rand_data *ec, uint64_t current_delta) +{ + uint64_t prediction; + unsigned int i; + + /* Initialize the delta_history */ + if (ec->lag_observations < JENT_LAG_HISTORY_SIZE) { + ec->lag_delta_history[ec->lag_observations] = current_delta; + ec->lag_observations++; + return; + } + + /* + * The history is initialized. First make a guess and examine the + * results. + */ + prediction = JENT_LAG_HISTORY(ec, ec->lag_best_predictor); + + if (prediction == current_delta) { + /* The prediction was correct. */ + ec->lag_prediction_success_count++; + ec->lag_prediction_success_run++; + + if ((ec->lag_prediction_success_run >= ec->lag_local_cutoff) || + (ec->lag_prediction_success_count >= ec->lag_global_cutoff)) + ec->health_failure |= JENT_LAG_FAILURE; + } else { + /* The prediction wasn't correct. End any run of successes.*/ + ec->lag_prediction_success_run = 0; + } + + /* Now update the predictors using the current data. */ + for (i = 0; i < JENT_LAG_HISTORY_SIZE; i++) { + if (JENT_LAG_HISTORY(ec, i) == current_delta) { + /* + * The ith predictor (which guesses i + 1 symbols in + * the past) successfully guessed. + */ + ec->lag_scoreboard[i] ++; + + /* + * Keep track of the best predictor (tie goes to the + * shortest lag) + */ + if (ec->lag_scoreboard[i] > + ec->lag_scoreboard[ec->lag_best_predictor]) + ec->lag_best_predictor = i; + } + } + + /* + * Finally, update the lag_delta_history array with the newly input + * value. + */ + ec->lag_delta_history[(ec->lag_observations) & JENT_LAG_MASK] = + current_delta; + ec->lag_observations++; + + /* + * lag_best_predictor now is the index of the predictor with the largest + * number of correct guesses. + * This establishes our next guess. + */ + + /* Do we now need a new window? */ + if (ec->lag_observations >= JENT_LAG_WINDOW_SIZE) + jent_lag_reset(ec); +} + +static inline uint64_t jent_delta2(struct rand_data *ec, uint64_t current_delta) +{ + /* Note that delta2_n = delta_n - delta_{n-1} */ + return jent_delta(JENT_LAG_HISTORY(ec, 0), current_delta); +} + +static inline uint64_t jent_delta3(struct rand_data *ec, uint64_t delta2) +{ + /* + * Note that delta3_n = delta2_n - delta2_{n-1} + * = delta2_n - (delta_{n-1} - delta_{n-2}) + */ + return jent_delta(jent_delta(JENT_LAG_HISTORY(ec, 1), + JENT_LAG_HISTORY(ec, 0)), delta2); +} + +#else /* JENT_HEALTH_LAG_PREDICTOR */ + +static inline void jent_lag_insert(struct rand_data *ec, uint64_t current_delta) +{ + (void)ec; + (void)current_delta; +} + +static inline uint64_t jent_delta2(struct rand_data *ec, uint64_t current_delta) +{ + uint64_t delta2 = jent_delta(ec->last_delta, current_delta); + + ec->last_delta = current_delta; + return delta2; +} + +static inline uint64_t jent_delta3(struct rand_data *ec, uint64_t delta2) +{ + uint64_t delta3 = jent_delta(ec->last_delta2, delta2); + + ec->last_delta2 = delta2; + return delta3; +} + +#endif /* JENT_HEALTH_LAG_PREDICTOR */ + +/*************************************************************************** + * Adaptive Proportion Test + * + * This test complies with SP800-90B section 4.4.2. + ***************************************************************************/ + +/* + * See the SP 800-90B comment #10b for the corrected cutoff for the SP 800-90B + * APT. + * http://www.untruth.org/~josh/sp80090b/UL%20SP800-90B-final%20comments%20v1.9%2020191212.pdf + * In in the syntax of R, this is C = 2 + qbinom(1 - 2^(-30), 511, 2^(-1/osr)). + * (The original formula wasn't correct because the first symbol must + * necessarily have been observed, so there is no chance of observing 0 of these + * symbols.) + * + * For any value above 14, this yields the maximal allowable value of 512 + * (by FIPS 140-2 IG 7.19 Resolution # 16, we cannot choose a cutoff value that + * renders the test unable to fail). + */ +static const unsigned int jent_apt_cutoff_lookup[15]= + { 325, 422, 459, 477, 488, 494, 499, 502, + 505, 507, 508, 509, 510, 511, 512 }; + +void jent_apt_init(struct rand_data *ec, unsigned int osr) +{ + /* + * Establish the apt_cutoff based on the presumed entropy rate of + * 1/osr. + */ + if (osr >= ARRAY_SIZE(jent_apt_cutoff_lookup)) { + ec->apt_cutoff = jent_apt_cutoff_lookup[ + ARRAY_SIZE(jent_apt_cutoff_lookup) - 1]; + } else { + ec->apt_cutoff = jent_apt_cutoff_lookup[osr - 1]; + } +} + +/** + * Reset the APT counter + * + * @ec [in] Reference to entropy collector + */ +static void jent_apt_reset(struct rand_data *ec) +{ + /* When reset, accept the _next_ value input as the new base. */ + ec->apt_base_set = 0; +} + +/** + * Insert a new entropy event into APT + * + * @ec [in] Reference to entropy collector + * @current_delta [in] Current time delta + */ +static void jent_apt_insert(struct rand_data *ec, uint64_t current_delta) +{ + /* Initialize the base reference */ + if (!ec->apt_base_set) { + ec->apt_base = current_delta; // APT Step 1 + ec->apt_base_set = 1; // APT Step 2 + + /* + * Reset APT counter + * Note that we've taken in the first symbol in the window. + */ + ec->apt_count = 1; // B = 1 + ec->apt_observations = 1; + + return; + } + + if (current_delta == ec->apt_base) { + ec->apt_count++; // B = B + 1 + + /* Note, ec->apt_count starts with one. */ + if (ec->apt_count >= ec->apt_cutoff) + ec->health_failure |= JENT_APT_FAILURE; + } + + ec->apt_observations++; + + /* Completed one window, the next symbol input will be new apt_base. */ + if (ec->apt_observations >= JENT_APT_WINDOW_SIZE) + jent_apt_reset(ec); // APT Step 4 +} + +/*************************************************************************** + * Stuck Test and its use as Repetition Count Test + * + * The Jitter RNG uses an enhanced version of the Repetition Count Test + * (RCT) specified in SP800-90B section 4.4.1. Instead of counting identical + * back-to-back values, the input to the RCT is the counting of the stuck + * values during the generation of one Jitter RNG output block. + * + * The RCT is applied with an alpha of 2^{-30} compliant to FIPS 140-2 IG 9.8. + * + * During the counting operation, the Jitter RNG always calculates the RCT + * cut-off value of C. If that value exceeds the allowed cut-off value, + * the Jitter RNG output block will be calculated completely but discarded at + * the end. The caller of the Jitter RNG is informed with an error code. + ***************************************************************************/ + +/** + * Repetition Count Test as defined in SP800-90B section 4.4.1 + * + * @ec [in] Reference to entropy collector + * @stuck [in] Indicator whether the value is stuck + */ +static void jent_rct_insert(struct rand_data *ec, int stuck) +{ + /* + * If we have a count less than zero, a previous RCT round identified + * a failure. We will not overwrite it. + */ + if (ec->rct_count < 0) + return; + + if (stuck) { + ec->rct_count++; + + /* + * The cutoff value is based on the following consideration: + * alpha = 2^-30 as recommended in FIPS 140-2 IG 9.8. + * In addition, we require an entropy value H of 1/osr as this + * is the minimum entropy required to provide full entropy. + * Note, we collect (DATA_SIZE_BITS + ENTROPY_SAFETY_FACTOR)*osr + * deltas for inserting them into the entropy pool which should + * then have (close to) DATA_SIZE_BITS bits of entropy in the + * conditioned output. + * + * Note, ec->rct_count (which equals to value B in the pseudo + * code of SP800-90B section 4.4.1) starts with zero. Hence + * we need to subtract one from the cutoff value as calculated + * following SP800-90B. Thus C = ceil(-log_2(alpha)/H) = 30*osr. + */ + if ((unsigned int)ec->rct_count >= (30 * ec->osr)) { + ec->rct_count = -1; + ec->health_failure |= JENT_RCT_FAILURE; + } + } else { + ec->rct_count = 0; + } +} + +/** + * Stuck test by checking the: + * 1st derivative of the jitter measurement (time delta) + * 2nd derivative of the jitter measurement (delta of time deltas) + * 3rd derivative of the jitter measurement (delta of delta of time deltas) + * + * All values must always be non-zero. + * + * @ec [in] Reference to entropy collector + * @current_delta [in] Jitter time delta + * + * @return + * 0 jitter measurement not stuck (good bit) + * 1 jitter measurement stuck (reject bit) + */ +unsigned int jent_stuck(struct rand_data *ec, uint64_t current_delta) +{ + uint64_t delta2 = jent_delta2(ec, current_delta); + uint64_t delta3 = jent_delta3(ec, delta2); + + /* + * Insert the result of the comparison of two back-to-back time + * deltas. + */ + jent_apt_insert(ec, current_delta); + jent_lag_insert(ec, current_delta); + + if (!current_delta || !delta2 || !delta3) { + /* RCT with a stuck bit */ + jent_rct_insert(ec, 1); + return 1; + } + + /* RCT with a non-stuck bit */ + jent_rct_insert(ec, 0); + + return 0; +} + +/** + * Report any health test failures + * + * @ec [in] Reference to entropy collector + * + * @return a bitmask indicating which tests failed + * 0 No health test failure + * 1 RCT failure + * 2 APT failure + * 4 Lag predictor test failure + */ +unsigned int jent_health_failure(struct rand_data *ec) +{ + /* Test is only enabled in FIPS mode */ + if (!ec->fips_enabled) + return 0; + + return ec->health_failure; +} diff --git a/random/jitterentropy-health.h b/random/jitterentropy-health.h new file mode 100644 index 00000000..7754629a --- /dev/null +++ b/random/jitterentropy-health.h @@ -0,0 +1,51 @@ +/* + * Copyright (C) 2021, Stephan Mueller + * + * License: see LICENSE file in root directory + * + * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED + * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ALL OF + * WHICH ARE HEREBY 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 NOT ADVISED OF THE POSSIBILITY OF SUCH + * DAMAGE. + */ + +#ifndef JITTERENTROPY_HEALTH_H +#define JITTERENTROPY_HEALTH_H + +#ifdef __cplusplus +extern "C" +{ +#endif + +static inline uint64_t jent_delta(uint64_t prev, uint64_t next) +{ + return (next - prev); +} + +#ifdef JENT_HEALTH_LAG_PREDICTOR +void jent_lag_init(struct rand_data *ec, unsigned int osr); +#else /* JENT_HEALTH_LAG_PREDICTOR */ +static inline void jent_lag_init(struct rand_data *ec, unsigned int osr) +{ + (void)ec; + (void)osr; +} +#endif /* JENT_HEALTH_LAG_PREDICTOR */ + +void jent_apt_init(struct rand_data *ec, unsigned int osr); +unsigned int jent_stuck(struct rand_data *ec, uint64_t current_delta); +unsigned int jent_health_failure(struct rand_data *ec); + +#ifdef __cplusplus +} +#endif + +#endif /* JITTERENTROPY_HEALTH_H */ diff --git a/random/jitterentropy-noise.c b/random/jitterentropy-noise.c new file mode 100644 index 00000000..0802650f --- /dev/null +++ b/random/jitterentropy-noise.c @@ -0,0 +1,383 @@ +/* Jitter RNG: Noise Sources + * + * Copyright (C) 2021, Stephan Mueller + * + * License: see LICENSE file in root directory + * + * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED + * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ALL OF + * WHICH ARE HEREBY 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 NOT ADVISED OF THE POSSIBILITY OF SUCH + * DAMAGE. + */ + +#include "jitterentropy-noise.h" +#include "jitterentropy-health.h" +#include "jitterentropy-timer.h" +#include "jitterentropy-sha3.h" + +#define BUILD_BUG_ON(condition) ((void)sizeof(char[1 - 2*!!(condition)])) + +/*************************************************************************** + * Noise sources + ***************************************************************************/ + +/** + * Update of the loop count used for the next round of + * an entropy collection. + * + * @ec [in] entropy collector struct -- may be NULL + * @bits [in] is the number of low bits of the timer to consider + * @min [in] is the number of bits we shift the timer value to the right at + * the end to make sure we have a guaranteed minimum value + * + * @return Newly calculated loop counter + */ +static uint64_t jent_loop_shuffle(struct rand_data *ec, + unsigned int bits, unsigned int min) +{ +#ifdef JENT_CONF_DISABLE_LOOP_SHUFFLE + + (void)ec; + (void)bits; + + return (UINT64_C(1)<data[0]; + } + + /* + * We fold the time value as much as possible to ensure that as many + * bits of the time stamp are included as possible. + */ + for (i = 0; ((DATA_SIZE_BITS + bits - 1) / bits) > i; i++) { + shuffle ^= time & mask; + time = time >> bits; + } + + /* + * We add a lower boundary value to ensure we have a minimum + * RNG loop count. + */ + return (shuffle + (UINT64_C(1)< 63); + uint64_t hash_loop_cnt = + jent_loop_shuffle(ec, MAX_HASH_LOOP, MIN_HASH_LOOP); + + sha3_256_init(&ctx); + + /* + * testing purposes -- allow test app to set the counter, not + * needed during runtime + */ + if (loop_cnt) + hash_loop_cnt = loop_cnt; + + /* + * This loop basically slows down the SHA-3 operation depending + * on the hash_loop_cnt. Each iteration of the loop generates the + * same result. + */ + for (j = 0; j < hash_loop_cnt; j++) { + sha3_update(&ctx, ec->data, SHA3_256_SIZE_DIGEST); + sha3_update(&ctx, (uint8_t *)&time, sizeof(uint64_t)); + sha3_update(&ctx, (uint8_t *)&j, sizeof(uint64_t)); + + /* + * If the time stamp is stuck, do not finally insert the value + * into the entropy pool. Although this operation should not do + * any harm even when the time stamp has no entropy, SP800-90B + * requires that any conditioning operation to have an identical + * amount of input data according to section 3.1.5. + */ + + /* + * The sha3_final operations re-initialize the context for the + * next loop iteration. + */ + if (stuck || (j < hash_loop_cnt - 1)) + sha3_final(&ctx, itermediary); + else + sha3_final(&ctx, ec->data); + } + + jent_memset_secure(&ctx, SHA_MAX_CTX_SIZE); + jent_memset_secure(itermediary, sizeof(itermediary)); +} + +#define MAX_ACC_LOOP_BIT 7 +#define MIN_ACC_LOOP_BIT 0 +#ifdef JENT_RANDOM_MEMACCESS + +static inline uint32_t uint32rotl(const uint32_t x, int k) +{ + return (x << k) | (x >> (32 - k)); +} + +static inline uint32_t xoshiro128starstar(uint32_t *s) +{ + const uint32_t result = uint32rotl(s[1] * 5, 7) * 9; + const uint32_t t = s[1] << 9; + + s[2] ^= s[0]; + s[3] ^= s[1]; + s[1] ^= s[2]; + s[0] ^= s[3]; + + s[2] ^= t; + + s[3] = uint32rotl(s[3], 11); + + return result; +} + +static void jent_memaccess(struct rand_data *ec, uint64_t loop_cnt) +{ + uint64_t i = 0; + union { + uint32_t u[4]; + uint8_t b[sizeof(uint32_t) * 4]; + } prngState = { .u = {0x8e93eec0, 0xce65608a, 0xa8d46b46, 0xe83cef69} }; + uint32_t addressMask = ec->memmask; + + /* Ensure that macros cannot overflow jent_loop_shuffle() */ + BUILD_BUG_ON((MAX_ACC_LOOP_BIT + MIN_ACC_LOOP_BIT) > 63); + uint64_t acc_loop_cnt = + jent_loop_shuffle(ec, MAX_ACC_LOOP_BIT, MIN_ACC_LOOP_BIT); + + if (NULL == ec || NULL == ec->mem) + return; + + /* + * Mix the current data into prngState + * + * Any time you see a PRNG in a noise source, you should be concerned. + * + * The PRNG doesn't directly produce the raw noise, it just adjusts the + * location being updated. The timing of the update is part of the raw + * sample. The main thing this process gets you isn't better + * "per-update: timing, it gets you mostly independent "per-update" + * timing, so we can now benefit from the Central Limit Theorem! + */ + for (i = 0; i < sizeof(prngState); i++) + prngState.b[i] ^= ec->data[i]; + + /* + * testing purposes -- allow test app to set the counter, not + * needed during runtime + */ + if (loop_cnt) + acc_loop_cnt = loop_cnt; + + for (i = 0; i < (ec->memaccessloops + acc_loop_cnt); i++) { + /* Take PRNG output to find the memory location to update. */ + unsigned char *tmpval = ec->mem + + (xoshiro128starstar(prngState.u) & + addressMask); + + /* + * memory access: just add 1 to one byte, + * wrap at 255 -- memory access implies read + * from and write to memory location + */ + *tmpval = (unsigned char)((*tmpval + 1) & 0xff); + } +} + +#else /* JENT_RANDOM_MEMACCESS */ + +/** + * Memory Access noise source -- this is a noise source based on variations in + * memory access times + * + * This function performs memory accesses which will add to the timing + * variations due to an unknown amount of CPU wait states that need to be + * added when accessing memory. The memory size should be larger than the L1 + * caches as outlined in the documentation and the associated testing. + * + * The L1 cache has a very high bandwidth, albeit its access rate is usually + * slower than accessing CPU registers. Therefore, L1 accesses only add minimal + * variations as the CPU has hardly to wait. Starting with L2, significant + * variations are added because L2 typically does not belong to the CPU any more + * and therefore a wider range of CPU wait states is necessary for accesses. + * L3 and real memory accesses have even a wider range of wait states. However, + * to reliably access either L3 or memory, the ec->mem memory must be quite + * large which is usually not desirable. + * + * @ec [in] Reference to the entropy collector with the memory access data -- if + * the reference to the memory block to be accessed is NULL, this noise + * source is disabled + * @loop_cnt [in] if a value not equal to 0 is set, use the given value as + * number of loops to perform the hash operation + */ +static void jent_memaccess(struct rand_data *ec, uint64_t loop_cnt) +{ + unsigned int wrap = 0; + uint64_t i = 0; + + /* Ensure that macros cannot overflow jent_loop_shuffle() */ + BUILD_BUG_ON((MAX_ACC_LOOP_BIT + MIN_ACC_LOOP_BIT) > 63); + uint64_t acc_loop_cnt = + jent_loop_shuffle(ec, MAX_ACC_LOOP_BIT, MIN_ACC_LOOP_BIT); + + if (NULL == ec || NULL == ec->mem) + return; + wrap = ec->memblocksize * ec->memblocks; + + /* + * testing purposes -- allow test app to set the counter, not + * needed during runtime + */ + if (loop_cnt) + acc_loop_cnt = loop_cnt; + for (i = 0; i < (ec->memaccessloops + acc_loop_cnt); i++) { + unsigned char *tmpval = ec->mem + ec->memlocation; + /* + * memory access: just add 1 to one byte, + * wrap at 255 -- memory access implies read + * from and write to memory location + */ + *tmpval = (unsigned char)((*tmpval + 1) & 0xff); + /* + * Addition of memblocksize - 1 to pointer + * with wrap around logic to ensure that every + * memory location is hit evenly + */ + ec->memlocation = ec->memlocation + ec->memblocksize - 1; + ec->memlocation = ec->memlocation % wrap; + } +} + +#endif /* JENT_RANDOM_MEMACCESS */ + +/*************************************************************************** + * Start of entropy processing logic + ***************************************************************************/ + +/** + * This is the heart of the entropy generation: calculate time deltas and + * use the CPU jitter in the time deltas. The jitter is injected into the + * entropy pool. + * + * WARNING: ensure that ->prev_time is primed before using the output + * of this function! This can be done by calling this function + * and not using its result. + * + * @ec [in] Reference to entropy collector + * @loop_cnt [in] see jent_hash_time + * @ret_current_delta [out] Test interface: return time delta - may be NULL + * + * @return: result of stuck test + */ +unsigned int jent_measure_jitter(struct rand_data *ec, + uint64_t loop_cnt, + uint64_t *ret_current_delta) +{ + uint64_t time = 0; + uint64_t current_delta = 0; + unsigned int stuck; + + /* Invoke one noise source before time measurement to add variations */ + jent_memaccess(ec, loop_cnt); + + /* + * Get time stamp and calculate time delta to previous + * invocation to measure the timing variations + */ + jent_get_nstime_internal(ec, &time); + current_delta = jent_delta(ec->prev_time, time) / + ec->jent_common_timer_gcd; + ec->prev_time = time; + + /* Check whether we have a stuck measurement. */ + stuck = jent_stuck(ec, current_delta); + + /* Now call the next noise sources which also injects the data */ + jent_hash_time(ec, current_delta, loop_cnt, stuck); + + /* return the raw entropy value */ + if (ret_current_delta) + *ret_current_delta = current_delta; + + return stuck; +} + +/** + * Generator of one 256 bit random number + * Function fills rand_data->data + * + * @ec [in] Reference to entropy collector + */ +void jent_random_data(struct rand_data *ec) +{ + unsigned int k = 0, safety_factor = ENTROPY_SAFETY_FACTOR; + + if (!ec->fips_enabled) + safety_factor = 0; + + /* priming of the ->prev_time value */ + jent_measure_jitter(ec, 0, NULL); + + while (1) { + /* If a stuck measurement is received, repeat measurement */ + if (jent_measure_jitter(ec, 0, NULL)) + continue; + + /* + * We multiply the loop value with ->osr to obtain the + * oversampling rate requested by the caller + */ + if (++k >= ((DATA_SIZE_BITS + safety_factor) * ec->osr)) + break; + } +} diff --git a/random/jitterentropy-noise.h b/random/jitterentropy-noise.h new file mode 100644 index 00000000..3998fbf7 --- /dev/null +++ b/random/jitterentropy-noise.h @@ -0,0 +1,39 @@ +/* + * Copyright (C) 2021, Stephan Mueller + * + * License: see LICENSE file in root directory + * + * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED + * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ALL OF + * WHICH ARE HEREBY 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 NOT ADVISED OF THE POSSIBILITY OF SUCH + * DAMAGE. + */ + +#ifndef JITTERENTROPY_NOISE_H +#define JITTERENTROPY_NOISE_H + +#include "jitterentropy.h" + +#ifdef __cplusplus +extern "C" +{ +#endif + +unsigned int jent_measure_jitter(struct rand_data *ec, + uint64_t loop_cnt, + uint64_t *ret_current_delta); +void jent_random_data(struct rand_data *ec); + +#ifdef __cplusplus +} +#endif + +#endif /* JITTERENTROPY_NOISE_H */ diff --git a/random/jitterentropy-sha3.c b/random/jitterentropy-sha3.c new file mode 100644 index 00000000..59fbb74f --- /dev/null +++ b/random/jitterentropy-sha3.c @@ -0,0 +1,382 @@ +/* Jitter RNG: SHA-3 Implementation + * + * Copyright (C) 2021, Stephan Mueller + * + * License: see LICENSE file in root directory + * + * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED + * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ALL OF + * WHICH ARE HEREBY 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 NOT ADVISED OF THE POSSIBILITY OF SUCH + * DAMAGE. + */ + +#include "jitterentropy-sha3.h" + +/*************************************************************************** + * Message Digest Implementation + ***************************************************************************/ + +/* + * Conversion of Little-Endian representations in byte streams - the data + * representation in the integer values is the host representation. + */ +static inline uint32_t ptr_to_le32(const uint8_t *p) +{ + return (uint32_t)p[0] | (uint32_t)p[1] << 8 | + (uint32_t)p[2] << 16 | (uint32_t)p[3] << 24; +} + +static inline uint64_t ptr_to_le64(const uint8_t *p) +{ + return (uint64_t)ptr_to_le32(p) | (uint64_t)ptr_to_le32(p + 4) << 32; +} + +static inline void le32_to_ptr(uint8_t *p, const uint32_t value) +{ + p[0] = (uint8_t)(value); + p[1] = (uint8_t)(value >> 8); + p[2] = (uint8_t)(value >> 16); + p[3] = (uint8_t)(value >> 24); +} + +static inline void le64_to_ptr(uint8_t *p, const uint64_t value) +{ + le32_to_ptr(p + 4, (uint32_t)(value >> 32)); + le32_to_ptr(p, (uint32_t)(value)); +} + +/*********************************** Keccak ***********************************/ +/* state[x + y*5] */ +#define A(x, y) (x + 5 * y) + +static inline void keccakp_theta(uint64_t s[25]) +{ + uint64_t C[5], D[5]; + + /* Step 1 */ + C[0] = s[A(0, 0)] ^ s[A(0, 1)] ^ s[A(0, 2)] ^ s[A(0, 3)] ^ s[A(0, 4)]; + C[1] = s[A(1, 0)] ^ s[A(1, 1)] ^ s[A(1, 2)] ^ s[A(1, 3)] ^ s[A(1, 4)]; + C[2] = s[A(2, 0)] ^ s[A(2, 1)] ^ s[A(2, 2)] ^ s[A(2, 3)] ^ s[A(2, 4)]; + C[3] = s[A(3, 0)] ^ s[A(3, 1)] ^ s[A(3, 2)] ^ s[A(3, 3)] ^ s[A(3, 4)]; + C[4] = s[A(4, 0)] ^ s[A(4, 1)] ^ s[A(4, 2)] ^ s[A(4, 3)] ^ s[A(4, 4)]; + + /* Step 2 */ + D[0] = C[4] ^ rol64(C[1], 1); + D[1] = C[0] ^ rol64(C[2], 1); + D[2] = C[1] ^ rol64(C[3], 1); + D[3] = C[2] ^ rol64(C[4], 1); + D[4] = C[3] ^ rol64(C[0], 1); + + /* Step 3 */ + s[A(0, 0)] ^= D[0]; + s[A(1, 0)] ^= D[1]; + s[A(2, 0)] ^= D[2]; + s[A(3, 0)] ^= D[3]; + s[A(4, 0)] ^= D[4]; + + s[A(0, 1)] ^= D[0]; + s[A(1, 1)] ^= D[1]; + s[A(2, 1)] ^= D[2]; + s[A(3, 1)] ^= D[3]; + s[A(4, 1)] ^= D[4]; + + s[A(0, 2)] ^= D[0]; + s[A(1, 2)] ^= D[1]; + s[A(2, 2)] ^= D[2]; + s[A(3, 2)] ^= D[3]; + s[A(4, 2)] ^= D[4]; + + s[A(0, 3)] ^= D[0]; + s[A(1, 3)] ^= D[1]; + s[A(2, 3)] ^= D[2]; + s[A(3, 3)] ^= D[3]; + s[A(4, 3)] ^= D[4]; + + s[A(0, 4)] ^= D[0]; + s[A(1, 4)] ^= D[1]; + s[A(2, 4)] ^= D[2]; + s[A(3, 4)] ^= D[3]; + s[A(4, 4)] ^= D[4]; +} + +static inline void keccakp_rho(uint64_t s[25]) +{ + /* Step 1 */ + /* s[A(0, 0)] = s[A(0, 0)]; */ + +#define RHO_ROL(t) (((t + 1) * (t + 2) / 2) % 64) + /* Step 3 */ + s[A(1, 0)] = rol64(s[A(1, 0)], RHO_ROL(0)); + s[A(0, 2)] = rol64(s[A(0, 2)], RHO_ROL(1)); + s[A(2, 1)] = rol64(s[A(2, 1)], RHO_ROL(2)); + s[A(1, 2)] = rol64(s[A(1, 2)], RHO_ROL(3)); + s[A(2, 3)] = rol64(s[A(2, 3)], RHO_ROL(4)); + s[A(3, 3)] = rol64(s[A(3, 3)], RHO_ROL(5)); + s[A(3, 0)] = rol64(s[A(3, 0)], RHO_ROL(6)); + s[A(0, 1)] = rol64(s[A(0, 1)], RHO_ROL(7)); + s[A(1, 3)] = rol64(s[A(1, 3)], RHO_ROL(8)); + s[A(3, 1)] = rol64(s[A(3, 1)], RHO_ROL(9)); + s[A(1, 4)] = rol64(s[A(1, 4)], RHO_ROL(10)); + s[A(4, 4)] = rol64(s[A(4, 4)], RHO_ROL(11)); + s[A(4, 0)] = rol64(s[A(4, 0)], RHO_ROL(12)); + s[A(0, 3)] = rol64(s[A(0, 3)], RHO_ROL(13)); + s[A(3, 4)] = rol64(s[A(3, 4)], RHO_ROL(14)); + s[A(4, 3)] = rol64(s[A(4, 3)], RHO_ROL(15)); + s[A(3, 2)] = rol64(s[A(3, 2)], RHO_ROL(16)); + s[A(2, 2)] = rol64(s[A(2, 2)], RHO_ROL(17)); + s[A(2, 0)] = rol64(s[A(2, 0)], RHO_ROL(18)); + s[A(0, 4)] = rol64(s[A(0, 4)], RHO_ROL(19)); + s[A(4, 2)] = rol64(s[A(4, 2)], RHO_ROL(20)); + s[A(2, 4)] = rol64(s[A(2, 4)], RHO_ROL(21)); + s[A(4, 1)] = rol64(s[A(4, 1)], RHO_ROL(22)); + s[A(1, 1)] = rol64(s[A(1, 1)], RHO_ROL(23)); +} + +static inline void keccakp_pi(uint64_t s[25]) +{ + uint64_t t = s[A(4, 4)]; + + /* Step 1 */ + /* s[A(0, 0)] = s[A(0, 0)]; */ + s[A(4, 4)] = s[A(1, 4)]; + s[A(1, 4)] = s[A(3, 1)]; + s[A(3, 1)] = s[A(1, 3)]; + s[A(1, 3)] = s[A(0, 1)]; + s[A(0, 1)] = s[A(3, 0)]; + s[A(3, 0)] = s[A(3, 3)]; + s[A(3, 3)] = s[A(2, 3)]; + s[A(2, 3)] = s[A(1, 2)]; + s[A(1, 2)] = s[A(2, 1)]; + s[A(2, 1)] = s[A(0, 2)]; + s[A(0, 2)] = s[A(1, 0)]; + s[A(1, 0)] = s[A(1, 1)]; + s[A(1, 1)] = s[A(4, 1)]; + s[A(4, 1)] = s[A(2, 4)]; + s[A(2, 4)] = s[A(4, 2)]; + s[A(4, 2)] = s[A(0, 4)]; + s[A(0, 4)] = s[A(2, 0)]; + s[A(2, 0)] = s[A(2, 2)]; + s[A(2, 2)] = s[A(3, 2)]; + s[A(3, 2)] = s[A(4, 3)]; + s[A(4, 3)] = s[A(3, 4)]; + s[A(3, 4)] = s[A(0, 3)]; + s[A(0, 3)] = s[A(4, 0)]; + s[A(4, 0)] = t; +} + +static inline void keccakp_chi(uint64_t s[25]) +{ + uint64_t t0[5], t1[5]; + + t0[0] = s[A(0, 0)]; + t0[1] = s[A(0, 1)]; + t0[2] = s[A(0, 2)]; + t0[3] = s[A(0, 3)]; + t0[4] = s[A(0, 4)]; + + t1[0] = s[A(1, 0)]; + t1[1] = s[A(1, 1)]; + t1[2] = s[A(1, 2)]; + t1[3] = s[A(1, 3)]; + t1[4] = s[A(1, 4)]; + + s[A(0, 0)] ^= ~s[A(1, 0)] & s[A(2, 0)]; + s[A(0, 1)] ^= ~s[A(1, 1)] & s[A(2, 1)]; + s[A(0, 2)] ^= ~s[A(1, 2)] & s[A(2, 2)]; + s[A(0, 3)] ^= ~s[A(1, 3)] & s[A(2, 3)]; + s[A(0, 4)] ^= ~s[A(1, 4)] & s[A(2, 4)]; + + s[A(1, 0)] ^= ~s[A(2, 0)] & s[A(3, 0)]; + s[A(1, 1)] ^= ~s[A(2, 1)] & s[A(3, 1)]; + s[A(1, 2)] ^= ~s[A(2, 2)] & s[A(3, 2)]; + s[A(1, 3)] ^= ~s[A(2, 3)] & s[A(3, 3)]; + s[A(1, 4)] ^= ~s[A(2, 4)] & s[A(3, 4)]; + + s[A(2, 0)] ^= ~s[A(3, 0)] & s[A(4, 0)]; + s[A(2, 1)] ^= ~s[A(3, 1)] & s[A(4, 1)]; + s[A(2, 2)] ^= ~s[A(3, 2)] & s[A(4, 2)]; + s[A(2, 3)] ^= ~s[A(3, 3)] & s[A(4, 3)]; + s[A(2, 4)] ^= ~s[A(3, 4)] & s[A(4, 4)]; + + s[A(3, 0)] ^= ~s[A(4, 0)] & t0[0]; + s[A(3, 1)] ^= ~s[A(4, 1)] & t0[1]; + s[A(3, 2)] ^= ~s[A(4, 2)] & t0[2]; + s[A(3, 3)] ^= ~s[A(4, 3)] & t0[3]; + s[A(3, 4)] ^= ~s[A(4, 4)] & t0[4]; + + s[A(4, 0)] ^= ~t0[0] & t1[0]; + s[A(4, 1)] ^= ~t0[1] & t1[1]; + s[A(4, 2)] ^= ~t0[2] & t1[2]; + s[A(4, 3)] ^= ~t0[3] & t1[3]; + s[A(4, 4)] ^= ~t0[4] & t1[4]; +} + +static const uint64_t keccakp_iota_vals[] = { + 0x0000000000000001ULL, 0x0000000000008082ULL, 0x800000000000808aULL, + 0x8000000080008000ULL, 0x000000000000808bULL, 0x0000000080000001ULL, + 0x8000000080008081ULL, 0x8000000000008009ULL, 0x000000000000008aULL, + 0x0000000000000088ULL, 0x0000000080008009ULL, 0x000000008000000aULL, + 0x000000008000808bULL, 0x800000000000008bULL, 0x8000000000008089ULL, + 0x8000000000008003ULL, 0x8000000000008002ULL, 0x8000000000000080ULL, + 0x000000000000800aULL, 0x800000008000000aULL, 0x8000000080008081ULL, + 0x8000000000008080ULL, 0x0000000080000001ULL, 0x8000000080008008ULL +}; + +static inline void keccakp_iota(uint64_t s[25], unsigned int round) +{ + s[0] ^= keccakp_iota_vals[round]; +} + +static inline void keccakp_1600(uint64_t s[25]) +{ + unsigned int round; + + for (round = 0; round < 24; round++) { + keccakp_theta(s); + keccakp_rho(s); + keccakp_pi(s); + keccakp_chi(s); + keccakp_iota(s, round); + } +} + +/*********************************** SHA-3 ************************************/ + +static inline void sha3_init(struct sha_ctx *ctx) +{ + unsigned int i; + + for (i = 0; i < 25; i++) + ctx->state[i] = 0; + ctx->msg_len = 0; +} + +void sha3_256_init(struct sha_ctx *ctx) +{ + sha3_init(ctx); + ctx->r = SHA3_256_SIZE_BLOCK; + ctx->rword = SHA3_256_SIZE_BLOCK / sizeof(uint64_t); + ctx->digestsize = SHA3_256_SIZE_DIGEST; +} + +static inline void sha3_fill_state(struct sha_ctx *ctx, const uint8_t *in) +{ + unsigned int i; + + for (i = 0; i < ctx->rword; i++) { + ctx->state[i] ^= ptr_to_le64(in); + in += 8; + } +} + +void sha3_update(struct sha_ctx *ctx, const uint8_t *in, size_t inlen) +{ + size_t partial = ctx->msg_len % ctx->r; + + ctx->msg_len += inlen; + + /* Sponge absorbing phase */ + + /* Check if we have a partial block stored */ + if (partial) { + size_t todo = ctx->r - partial; + + /* + * If the provided data is small enough to fit in the partial + * buffer, copy it and leave it unprocessed. + */ + if (inlen < todo) { + memcpy(ctx->partial + partial, in, inlen); + return; + } + + /* + * The input data is large enough to fill the entire partial + * block buffer. Thus, we fill it and transform it. + */ + memcpy(ctx->partial + partial, in, todo); + inlen -= todo; + in += todo; + + sha3_fill_state(ctx, ctx->partial); + keccakp_1600(ctx->state); + } + + /* Perform a transformation of full block-size messages */ + for (; inlen >= ctx->r; inlen -= ctx->r, in += ctx->r) { + sha3_fill_state(ctx, in); + keccakp_1600(ctx->state); + } + + /* If we have data left, copy it into the partial block buffer */ + memcpy(ctx->partial, in, inlen); +} + +void sha3_final(struct sha_ctx *ctx, uint8_t *digest) +{ + size_t partial = ctx->msg_len % ctx->r; + unsigned int i; + + /* Final round in sponge absorbing phase */ + + /* Fill the unused part of the partial buffer with zeros */ + memset(ctx->partial + partial, 0, ctx->r - partial); + + /* + * Add the leading and trailing bit as well as the 01 bits for the + * SHA-3 suffix. + */ + ctx->partial[partial] = 0x06; + ctx->partial[ctx->r - 1] |= 0x80; + + /* Final transformation */ + sha3_fill_state(ctx, ctx->partial); + keccakp_1600(ctx->state); + + /* + * Sponge squeeze phase - the digest size is always smaller as the + * state size r which implies we only have one squeeze round. + */ + for (i = 0; i < ctx->digestsize / 8; i++, digest += 8) + le64_to_ptr(digest, ctx->state[i]); + + /* Add remaining 4 bytes if we use SHA3-224 */ + if (ctx->digestsize % 8) + le32_to_ptr(digest, (uint32_t)(ctx->state[i])); + + memset(ctx->partial, 0, ctx->r); + sha3_init(ctx); +} + +int sha3_tester(void) +{ + HASH_CTX_ON_STACK(ctx); + static const uint8_t msg_256[] = { 0x5E, 0x5E, 0xD6 }; + static const uint8_t exp_256[] = { 0xF1, 0x6E, 0x66, 0xC0, 0x43, 0x72, + 0xB4, 0xA3, 0xE1, 0xE3, 0x2E, 0x07, + 0xC4, 0x1C, 0x03, 0x40, 0x8A, 0xD5, + 0x43, 0x86, 0x8C, 0xC4, 0x0E, 0xC5, + 0x5E, 0x00, 0xBB, 0xBB, 0xBD, 0xF5, + 0x91, 0x1E }; + uint8_t act[SHA3_256_SIZE_DIGEST] = { 0 }; + unsigned int i; + + sha3_256_init(&ctx); + sha3_update(&ctx, msg_256, 3); + sha3_final(&ctx, act); + + for (i = 0; i < SHA3_256_SIZE_DIGEST; i++) { + if (exp_256[i] != act[i]) + return 1; + } + + return 0; +} diff --git a/random/jitterentropy-sha3.h b/random/jitterentropy-sha3.h new file mode 100644 index 00000000..27deb22b --- /dev/null +++ b/random/jitterentropy-sha3.h @@ -0,0 +1,56 @@ +/* + * Copyright (C) 2021, Stephan Mueller + * + * License: see LICENSE file in root directory + * + * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED + * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ALL OF + * WHICH ARE HEREBY 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 NOT ADVISED OF THE POSSIBILITY OF SUCH + * DAMAGE. + */ + +#ifndef JITTERENTROPY_SHA3_H +#define JITTERENTROPY_SHA3_H + +#include "jitterentropy.h" + +#ifdef __cplusplus +extern "C" +{ +#endif + +#define SHA3_SIZE_BLOCK(bits) ((1600 - 2 * bits) >> 3) +#define SHA3_256_SIZE_BLOCK SHA3_SIZE_BLOCK(SHA3_256_SIZE_DIGEST_BITS) +#define SHA3_MAX_SIZE_BLOCK SHA3_256_SIZE_BLOCK + +struct sha_ctx { + uint64_t state[25]; + size_t msg_len; + unsigned int r; + unsigned int rword; + unsigned int digestsize; + uint8_t partial[SHA3_MAX_SIZE_BLOCK]; +}; + +#define SHA_MAX_CTX_SIZE (sizeof(struct sha_ctx)) +#define HASH_CTX_ON_STACK(name) \ + struct sha_ctx name + +void sha3_256_init(struct sha_ctx *ctx); +void sha3_update(struct sha_ctx *ctx, const uint8_t *in, size_t inlen); +void sha3_final(struct sha_ctx *ctx, uint8_t *digest); +int sha3_tester(void); + +#ifdef __cplusplus +} +#endif + +#endif /* JITTERENTROPY_SHA3_H */ diff --git a/random/jitterentropy-timer.c b/random/jitterentropy-timer.c new file mode 100644 index 00000000..72b17ce1 --- /dev/null +++ b/random/jitterentropy-timer.c @@ -0,0 +1,234 @@ +/* Jitter RNG: Internal timer implementation + * + * Copyright (C) 2021, Stephan Mueller + * + * License: see LICENSE file in root directory + * + * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED + * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ALL OF + * WHICH ARE HEREBY 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 NOT ADVISED OF THE POSSIBILITY OF SUCH + * DAMAGE. + */ + +#include "jitterentropy-base.h" +#include "jitterentropy-timer.h" + +#ifdef JENT_CONF_ENABLE_INTERNAL_TIMER + +/*************************************************************************** + * Thread handler + ***************************************************************************/ + +JENT_PRIVATE_STATIC +int jent_notime_init(void **ctx) +{ + struct jent_notime_ctx *thread_ctx; + long ncpu = jent_ncpu(); + + if (ncpu < 0) + return (int)ncpu; + + /* We need at least two CPUs to enable the timer thread */ + if (ncpu < 2) + return -EOPNOTSUPP; + + thread_ctx = calloc(1, sizeof(struct jent_notime_ctx)); + if (!thread_ctx) + return -errno; + + *ctx = thread_ctx; + + return 0; +} + +JENT_PRIVATE_STATIC +void jent_notime_fini(void *ctx) +{ + struct jent_notime_ctx *thread_ctx = (struct jent_notime_ctx *)ctx; + + if (thread_ctx) + free(thread_ctx); +} + +static int jent_notime_start(void *ctx, + void *(*start_routine) (void *), void *arg) +{ + struct jent_notime_ctx *thread_ctx = (struct jent_notime_ctx *)ctx; + int ret; + + if (!thread_ctx) + return -EINVAL; + + ret = -pthread_attr_init(&thread_ctx->notime_pthread_attr); + if (ret) + return ret; + + return -pthread_create(&thread_ctx->notime_thread_id, + &thread_ctx->notime_pthread_attr, + start_routine, arg); +} + +static void jent_notime_stop(void *ctx) +{ + struct jent_notime_ctx *thread_ctx = (struct jent_notime_ctx *)ctx; + + pthread_join(thread_ctx->notime_thread_id, NULL); + pthread_attr_destroy(&thread_ctx->notime_pthread_attr); +} + +static struct jent_notime_thread jent_notime_thread_builtin = { + .jent_notime_init = jent_notime_init, + .jent_notime_fini = jent_notime_fini, + .jent_notime_start = jent_notime_start, + .jent_notime_stop = jent_notime_stop +}; + +/*************************************************************************** + * Timer-less timer replacement + * + * If there is no high-resolution hardware timer available, we create one + * ourselves. This logic is only used when the initialization identifies + * that no suitable time source is available. + ***************************************************************************/ + +static int jent_force_internal_timer = 0; +static int jent_notime_switch_blocked = 0; + +void jent_notime_block_switch(void) +{ + jent_notime_switch_blocked = 1; +} + +static struct jent_notime_thread *notime_thread = &jent_notime_thread_builtin; + +/** + * Timer-replacement loop + * + * @brief The measurement loop triggers the read of the value from the + * counter function. It conceptually acts as the low resolution + * samples timer from a ring oscillator. + */ +static void *jent_notime_sample_timer(void *arg) +{ + struct rand_data *ec = (struct rand_data *)arg; + + ec->notime_timer = 0; + + while (1) { + if (ec->notime_interrupt) + return NULL; + + ec->notime_timer++; + } + + return NULL; +} + +/* + * Enable the clock: spawn a new thread that holds a counter. + * + * Note, although creating a thread is expensive, we do that every time a + * caller wants entropy from us and terminate the thread afterwards. This + * is to ensure an attacker cannot easily identify the ticking thread. + */ +int jent_notime_settick(struct rand_data *ec) +{ + if (!ec->enable_notime || !notime_thread) + return 0; + + ec->notime_interrupt = 0; + ec->notime_prev_timer = 0; + ec->notime_timer = 0; + + return notime_thread->jent_notime_start(ec->notime_thread_ctx, + jent_notime_sample_timer, ec); +} + +void jent_notime_unsettick(struct rand_data *ec) +{ + if (!ec->enable_notime || !notime_thread) + return; + + ec->notime_interrupt = 1; + notime_thread->jent_notime_stop(ec->notime_thread_ctx); +} + +void jent_get_nstime_internal(struct rand_data *ec, uint64_t *out) +{ + if (ec->enable_notime) { + /* + * Allow the counting thread to be initialized and guarantee + * that it ticked since last time we looked. + * + * Note, we do not use an atomic operation here for reading + * jent_notime_timer since if this integer is garbled, it even + * adds to entropy. But on most architectures, read/write + * of an uint64_t should be atomic anyway. + */ + while (ec->notime_timer == ec->notime_prev_timer) + jent_yield(); + + ec->notime_prev_timer = ec->notime_timer; + *out = ec->notime_prev_timer; + } else { + jent_get_nstime(out); + } +} + +static inline int jent_notime_enable_thread(struct rand_data *ec) +{ + if (notime_thread) + return notime_thread->jent_notime_init(&ec->notime_thread_ctx); + return 0; +} + +void jent_notime_disable(struct rand_data *ec) +{ + if (notime_thread) + notime_thread->jent_notime_fini(ec->notime_thread_ctx); +} + +int jent_notime_enable(struct rand_data *ec, unsigned int flags) +{ + /* Use internal timer */ + if (jent_force_internal_timer || (flags & JENT_FORCE_INTERNAL_TIMER)) { + /* Self test not run yet */ + if (!jent_force_internal_timer && + jent_time_entropy_init(flags | JENT_FORCE_INTERNAL_TIMER, + ec->osr)) + return EHEALTH; + + ec->enable_notime = 1; + return jent_notime_enable_thread(ec); + } + + return 0; +} + +int jent_notime_switch(struct jent_notime_thread *new_thread) +{ + if (jent_notime_switch_blocked) + return -EAGAIN; + notime_thread = new_thread; + return 0; +} + +void jent_notime_force(void) +{ + jent_force_internal_timer = 1; +} + +int jent_notime_forced(void) +{ + return jent_force_internal_timer; +} + +#endif /* JENT_CONF_ENABLE_INTERNAL_TIMER */ diff --git a/random/jitterentropy-timer.h b/random/jitterentropy-timer.h new file mode 100644 index 00000000..039f2336 --- /dev/null +++ b/random/jitterentropy-timer.h @@ -0,0 +1,92 @@ +/* + * Copyright (C) 2021, Stephan Mueller + * + * License: see LICENSE file in root directory + * + * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED + * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ALL OF + * WHICH ARE HEREBY 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 NOT ADVISED OF THE POSSIBILITY OF SUCH + * DAMAGE. + */ + +#ifndef JITTERENTROPY_TIMER_H +#define JITTERENTROPY_TIMER_H + +#include "jitterentropy.h" + +#ifdef __cplusplus +extern "C" +{ +#endif + +#ifdef JENT_CONF_ENABLE_INTERNAL_TIMER + +void jent_notime_block_switch(void); +int jent_notime_settick(struct rand_data *ec); +void jent_notime_unsettick(struct rand_data *ec); +void jent_get_nstime_internal(struct rand_data *ec, uint64_t *out); +int jent_notime_enable(struct rand_data *ec, unsigned int flags); +void jent_notime_disable(struct rand_data *ec); +int jent_notime_switch(struct jent_notime_thread *new_thread); +void jent_notime_force(void); +int jent_notime_forced(void); + +#else /* JENT_CONF_ENABLE_INTERNAL_TIMER */ + +static inline void jent_notime_block_switch(void) { } + +static inline int jent_notime_settick(struct rand_data *ec) +{ + (void)ec; + return 0; +} + +static inline void jent_notime_unsettick(struct rand_data *ec) { (void)ec; } + +static inline void jent_get_nstime_internal(struct rand_data *ec, uint64_t *out) +{ + (void)ec; + jent_get_nstime(out); +} + +static inline int jent_notime_enable(struct rand_data *ec, unsigned int flags) +{ + (void)ec; + + /* If we force the timer-less noise source, we return an error */ + if (flags & JENT_FORCE_INTERNAL_TIMER) + return EHEALTH; + + return 0; +} + +static inline void jent_notime_disable(struct rand_data *ec) +{ + (void)ec; +} + +static inline int jent_notime_switch(struct jent_notime_thread *new_thread) +{ + (void)new_thread; + return -EOPNOTSUPP; +} + +static inline void jent_notime_force(void) { } + +static inline int jent_notime_forced(void) { return 0; } + +#endif /* JENT_CONF_ENABLE_INTERNAL_TIMER */ + +#ifdef __cplusplus +} +#endif + +#endif /* JITTERENTROPY-TIMER_H */ diff --git a/random/jitterentropy.h b/random/jitterentropy.h index 3b7d14a1..4322c65d 100644 --- a/random/jitterentropy.h +++ b/random/jitterentropy.h @@ -1,148 +1,447 @@ /* * Non-physical true random number generator based on timing jitter. * - * Copyright Stephan Mueller , 2014 + * Copyright Stephan Mueller , 2014 - 2021 * * License * ======= * * 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, and the entire permission notice in its entirety, * including the disclaimer of warranties. * 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. * 3. The name of the author may not be used to endorse or promote * products derived from this software without specific prior * written permission. * * ALTERNATIVELY, this product may be distributed under the terms of * the GNU General Public License, in which case the provisions of the GPL are * required INSTEAD OF the above restrictions. (This clause is * necessary due to a potential bad interaction between the GPL and * the restrictions contained in a BSD-style copyright.) * * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ALL OF * WHICH ARE HEREBY 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 NOT ADVISED OF THE POSSIBILITY OF SUCH * DAMAGE. */ #ifndef _JITTERENTROPY_H #define _JITTERENTROPY_H -#ifdef __KERNEL__ -#include "jitterentropy-base-kernel.h" -#else +/*************************************************************************** + * Jitter RNG Configuration Section + * + * You may alter the following options + ***************************************************************************/ + +/* + * Enable timer-less timer support + * + * In case the hardware is identified to not provide a high-resolution time + * stamp, this option enables a built-in high-resolution time stamp mechanism. + * + * The timer-less noise source is based on threads. This noise source requires + * the linking with the POSIX threads library. I.e. the executing environment + * must offer POSIX threads. If this option is disabled, no linking + * with the POSIX threads library is needed. + */ +#define JENT_CONF_ENABLE_INTERNAL_TIMER + +/* + * Disable the loop shuffle operation + * + * The shuffle operation enlarges the timing of the conditioning function + * by a variable length defined by the LSB of a time stamp. Some mathematicians + * are concerned that this pseudo-random selection of the loop iteration count + * may create some form of dependency between the different loop counts + * and the associated time duration of the conditioning function. It + * also complicates entropy assessment because it effectively combines a bunch + * of shifted/scaled copies the same distribution and masks failures from the + * health testing. + * + * By enabling this flag, the loop shuffle operation is disabled and + * the entropy collection operates in a way that honor the concerns. + * + * By enabling this flag, the time of collecting entropy may be enlarged. + */ +#define JENT_CONF_DISABLE_LOOP_SHUFFLE + +/* + * Shall the LAG predictor health test be enabled? + */ +#define JENT_HEALTH_LAG_PREDICTOR + +/* + * Shall the jent_memaccess use a (statistically) random selection for the + * memory to update? + */ +#define JENT_RANDOM_MEMACCESS + +/*************************************************************************** + * Jitter RNG State Definition Section + ***************************************************************************/ + #include "jitterentropy-base-user.h" -#endif /* __KERNEL__ */ + +#define SHA3_256_SIZE_DIGEST_BITS 256 +#define SHA3_256_SIZE_DIGEST (SHA3_256_SIZE_DIGEST_BITS >> 3) + +/* + * The output 256 bits can receive more than 256 bits of min entropy, + * of course, but the 256-bit output of SHA3-256(M) can only asymptotically + * approach 256 bits of min entropy, not attain that bound. Random maps will + * tend to have output collisions, which reduces the creditable output entropy + * (that is what SP 800-90B Section 3.1.5.1.2 attempts to bound). + * + * The value "64" is justified in Appendix A.4 of the current 90C draft, + * and aligns with NIST's in "epsilon" definition in this document, which is + * that a string can be considered "full entropy" if you can bound the min + * entropy in each bit of output to at least 1-epsilon, where epsilon is + * required to be <= 2^(-32). + */ +#define ENTROPY_SAFETY_FACTOR 64 + +/** + * Function pointer data structure to register an external thread handler + * used for the timer-less mode of the Jitter RNG. + * + * The external caller provides these function pointers to handle the + * management of the timer thread that is spawned by the Jitter RNG. + * + * @var jent_notime_init This function is intended to initialze the threading + * support. All data that is required by the threading code must be + * held in the data structure @param ctx. The Jitter RNG maintains the + * data structure and uses it for every invocation of the following calls. + * + * @var jent_notime_fini This function shall terminate the threading support. + * The function must dispose of all memory and resources used for the + * threading operation. It must also dispose of the @param ctx memory. + * + * @var jent_notime_start This function is called when the Jitter RNG wants + * to start a thread. Besides providing a pointer to the @param ctx + * allocated during initialization time, the Jitter RNG provides a + * pointer to the function the thread shall execute and the argument + * the function shall be invoked with. These two parameters have the + * same purpose as the trailing two parameters of pthread_create(3). + * + * @var jent_notime_stop This function is invoked by the Jitter RNG when the + * thread should be stopped. Note, the Jitter RNG intends to start/stop + * the thread frequently. + * + * An example implementation is found in the Jitter RNG itself with its + * default thread handler of jent_notime_thread_builtin. + * + * If the caller wants to register its own thread handler, it must be done + * with the API call jent_entropy_switch_notime_impl as the first + * call to interact with the Jitter RNG, even before jent_entropy_init. + * After jent_entropy_init is called, changing of the threading implementation + * is not allowed. + */ +struct jent_notime_thread { + int (*jent_notime_init)(void **ctx); + void (*jent_notime_fini)(void *ctx); + int (*jent_notime_start)(void *ctx, + void *(*start_routine) (void *), void *arg); + void (*jent_notime_stop)(void *ctx); +}; /* The entropy pool */ struct rand_data { /* all data values that are vital to maintain the security * of the RNG are marked as SENSITIVE. A user must not * access that information while the RNG executes its loops to * calculate the next random value. */ - uint64_t data; /* SENSITIVE Actual random number */ - uint64_t old_data; /* SENSITIVE Previous random number */ - uint64_t prev_time; /* SENSITIVE Previous time stamp */ -#define DATA_SIZE_BITS ((sizeof(uint64_t)) * 8) - uint64_t last_delta; /* SENSITIVE stuck test */ - int64_t last_delta2; /* SENSITIVE stuck test */ - unsigned int osr; /* Oversample rate */ - int fips_enabled; /* FIPS enabled? */ - unsigned int stir:1; /* Post-processing stirring */ - unsigned int disable_unbias:1; /* Deactivate Von-Neuman unbias */ -#define JENT_MEMORY_BLOCKS 64 -#define JENT_MEMORY_BLOCKSIZE 32 + uint8_t data[SHA3_256_SIZE_DIGEST]; /* SENSITIVE Actual random number */ + uint64_t prev_time; /* SENSITIVE Previous time stamp */ +#define DATA_SIZE_BITS (SHA3_256_SIZE_DIGEST_BITS) + +#ifndef JENT_HEALTH_LAG_PREDICTOR + uint64_t last_delta; /* SENSITIVE stuck test */ + uint64_t last_delta2; /* SENSITIVE stuck test */ +#endif /* JENT_HEALTH_LAG_PREDICTOR */ + + unsigned int flags; /* Flags used to initialize */ + unsigned int osr; /* Oversampling rate */ + +#ifdef JENT_RANDOM_MEMACCESS + /* The step size should be larger than the cacheline size. */ +# ifndef JENT_MEMORY_BITS +# define JENT_MEMORY_BITS 17 +# endif +# ifndef JENT_MEMORY_SIZE +# define JENT_MEMORY_SIZE (UINT32_C(1)<> JENT_FLAGS_TO_MEMSIZE_SHIFT) +#define JENT_MAX_MEMSIZE_TO_FLAGS(val) (val << JENT_FLAGS_TO_MEMSIZE_SHIFT) +#define JENT_MAX_MEMSIZE_32kB JENT_MAX_MEMSIZE_TO_FLAGS(UINT32_C( 1)) +#define JENT_MAX_MEMSIZE_64kB JENT_MAX_MEMSIZE_TO_FLAGS(UINT32_C( 2)) +#define JENT_MAX_MEMSIZE_128kB JENT_MAX_MEMSIZE_TO_FLAGS(UINT32_C( 3)) +#define JENT_MAX_MEMSIZE_256kB JENT_MAX_MEMSIZE_TO_FLAGS(UINT32_C( 4)) +#define JENT_MAX_MEMSIZE_512kB JENT_MAX_MEMSIZE_TO_FLAGS(UINT32_C( 5)) +#define JENT_MAX_MEMSIZE_1MB JENT_MAX_MEMSIZE_TO_FLAGS(UINT32_C( 6)) +#define JENT_MAX_MEMSIZE_2MB JENT_MAX_MEMSIZE_TO_FLAGS(UINT32_C( 7)) +#define JENT_MAX_MEMSIZE_4MB JENT_MAX_MEMSIZE_TO_FLAGS(UINT32_C( 8)) +#define JENT_MAX_MEMSIZE_8MB JENT_MAX_MEMSIZE_TO_FLAGS(UINT32_C( 9)) +#define JENT_MAX_MEMSIZE_16MB JENT_MAX_MEMSIZE_TO_FLAGS(UINT32_C(10)) +#define JENT_MAX_MEMSIZE_32MB JENT_MAX_MEMSIZE_TO_FLAGS(UINT32_C(11)) +#define JENT_MAX_MEMSIZE_64MB JENT_MAX_MEMSIZE_TO_FLAGS(UINT32_C(12)) +#define JENT_MAX_MEMSIZE_128MB JENT_MAX_MEMSIZE_TO_FLAGS(UINT32_C(13)) +#define JENT_MAX_MEMSIZE_256MB JENT_MAX_MEMSIZE_TO_FLAGS(UINT32_C(14)) +#define JENT_MAX_MEMSIZE_512MB JENT_MAX_MEMSIZE_TO_FLAGS(UINT32_C(15)) +#define JENT_MAX_MEMSIZE_MAX JENT_MAX_MEMSIZE_512MB +#define JENT_MAX_MEMSIZE_MASK JENT_MAX_MEMSIZE_MAX +/* We start at 32kB -> offset is log2(32768) */ +#define JENT_MAX_MEMSIZE_OFFSET 14 + +#ifdef JENT_CONF_DISABLE_LOOP_SHUFFLE +# define JENT_MIN_OSR 3 +#else +# define JENT_MIN_OSR 1 +#endif + +#define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0])) /* -- BEGIN Main interface functions -- */ #ifndef JENT_STUCK_INIT_THRES /* * Per default, not more than 90% of all measurements during initialization * are allowed to be stuck. * * It is allowed to change this value as required for the intended environment. */ -#define JENT_STUCK_INIT_THRES(x) (x/10 * 9) +#define JENT_STUCK_INIT_THRES(x) ((x*9) / 10) #endif #ifdef JENT_PRIVATE_COMPILE # define JENT_PRIVATE_STATIC static #else /* JENT_PRIVATE_COMPILE */ -# define JENT_PRIVATE_STATIC +# define JENT_PRIVATE_STATIC __attribute__((visibility("default"))) #endif /* Number of low bits of the time value that we want to consider */ /* get raw entropy */ JENT_PRIVATE_STATIC ssize_t jent_read_entropy(struct rand_data *ec, char *data, size_t len); +JENT_PRIVATE_STATIC +ssize_t jent_read_entropy_safe(struct rand_data **ec, char *data, size_t len); /* initialize an instance of the entropy collector */ JENT_PRIVATE_STATIC struct rand_data *jent_entropy_collector_alloc(unsigned int osr, unsigned int flags); /* clearing of entropy collector */ JENT_PRIVATE_STATIC void jent_entropy_collector_free(struct rand_data *entropy_collector); /* initialization of entropy collector */ JENT_PRIVATE_STATIC int jent_entropy_init(void); +JENT_PRIVATE_STATIC +int jent_entropy_init_ex(unsigned int osr, unsigned int flags); /* return version number of core library */ JENT_PRIVATE_STATIC unsigned int jent_version(void); +/* Set a different thread handling logic for the notimer support */ +JENT_PRIVATE_STATIC +int jent_entropy_switch_notime_impl(struct jent_notime_thread *new_thread); + /* -- END of Main interface functions -- */ +/* -- BEGIN timer-less threading support functions to prevent code dupes -- */ + +struct jent_notime_ctx { + pthread_attr_t notime_pthread_attr; /* pthreads library */ + pthread_t notime_thread_id; /* pthreads thread ID */ +}; + +#ifdef JENT_CONF_ENABLE_INTERNAL_TIMER + +JENT_PRIVATE_STATIC +int jent_notime_init(void **ctx); + +JENT_PRIVATE_STATIC +void jent_notime_fini(void *ctx); + +#else + +static inline int jent_notime_init(void **ctx) { (void)ctx; return 0; } +static inline void jent_notime_fini(void *ctx) { (void)ctx; } + +#endif /* JENT_CONF_ENABLE_INTERNAL_TIMER */ + +/* -- END timer-less threading support functions to prevent code dupes -- */ + /* -- BEGIN error codes for init function -- */ #define ENOTIME 1 /* Timer service not available */ #define ECOARSETIME 2 /* Timer too coarse for RNG */ #define ENOMONOTONIC 3 /* Timer is not monotonic increasing */ #define EMINVARIATION 4 /* Timer variations too small for RNG */ #define EVARVAR 5 /* Timer does not produce variations of variations (2nd derivation of time is zero) */ #define EMINVARVAR 6 /* Timer variations of variations is too small */ #define EPROGERR 7 /* Programming error */ #define ESTUCK 8 /* Too many stuck results during init. */ +#define EHEALTH 9 /* Health test failed during initialization */ +#define ERCT 10 /* RCT failed during initialization */ +#define EHASH 11 /* Hash self test failed */ +#define EMEM 12 /* Can't allocate memory for initialization */ +#define EGCD 13 /* GCD self-test failed */ +/* -- END error codes for init function -- */ + +/* -- BEGIN error masks for health tests -- */ +#define JENT_RCT_FAILURE 1 /* Failure in RCT health test. */ +#define JENT_APT_FAILURE 2 /* Failure in APT health test. */ +#define JENT_LAG_FAILURE 4 /* Failure in Lag predictor health test. */ +/* -- END error masks for health tests -- */ /* -- BEGIN statistical test functions only complied with CONFIG_CRYPTO_CPU_JITTERENTROPY_STAT -- */ #ifdef CONFIG_CRYPTO_CPU_JITTERENTROPY_STAT JENT_PRIVATE_STATIC uint64_t jent_lfsr_var_stat(struct rand_data *ec, unsigned int min); #endif /* CONFIG_CRYPTO_CPU_JITTERENTROPY_STAT */ /* -- END of statistical test function -- */ #endif /* _JITTERENTROPY_H */