diff options
Diffstat (limited to 'crypto/jitterentropy.c')
| -rw-r--r-- | crypto/jitterentropy.c | 889 |
1 files changed, 464 insertions, 425 deletions
diff --git a/crypto/jitterentropy.c b/crypto/jitterentropy.c index acf44b2d2d1d..3f93cdc9a7af 100644 --- a/crypto/jitterentropy.c +++ b/crypto/jitterentropy.c @@ -2,12 +2,12 @@ * Non-physical true random number generator based on timing jitter -- * Jitter RNG standalone code. * - * Copyright Stephan Mueller <smueller@chronox.de>, 2015 + * Copyright Stephan Mueller <smueller@chronox.de>, 2015 - 2023 * * Design * ====== * - * See http://www.chronox.de/jent.html + * See https://www.chronox.de/jent.html * * License * ======= @@ -47,7 +47,7 @@ /* * This Jitterentropy RNG is based on the jitterentropy library - * version 1.1.0 provided at http://www.chronox.de/jent.html + * version 3.4.0 provided at https://www.chronox.de/jent.html */ #ifdef __OPTIMIZE__ @@ -57,28 +57,28 @@ typedef unsigned long long __u64; typedef long long __s64; typedef unsigned int __u32; +typedef unsigned char u8; #define NULL ((void *) 0) /* The entropy pool */ struct rand_data { + /* SHA3-256 is used as conditioner */ +#define DATA_SIZE_BITS 256 /* 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. */ - __u64 data; /* SENSITIVE Actual random number */ - __u64 old_data; /* SENSITIVE Previous random number */ - __u64 prev_time; /* SENSITIVE Previous time stamp */ -#define DATA_SIZE_BITS ((sizeof(__u64)) * 8) - __u64 last_delta; /* SENSITIVE stuck test */ - __s64 last_delta2; /* SENSITIVE stuck test */ - unsigned int stuck:1; /* Time measurement stuck */ - unsigned int osr; /* Oversample rate */ - 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 + void *hash_state; /* SENSITIVE hash state entropy pool */ + __u64 prev_time; /* SENSITIVE Previous time stamp */ + __u64 last_delta; /* SENSITIVE stuck test */ + __s64 last_delta2; /* SENSITIVE stuck test */ + + unsigned int flags; /* Flags used to initialize */ + unsigned int osr; /* Oversample rate */ #define JENT_MEMORY_ACCESSLOOPS 128 -#define JENT_MEMORY_SIZE (JENT_MEMORY_BLOCKS*JENT_MEMORY_BLOCKSIZE) +#define JENT_MEMORY_SIZE \ + (CONFIG_CRYPTO_JITTERENTROPY_MEMORY_BLOCKS * \ + CONFIG_CRYPTO_JITTERENTROPY_MEMORY_BLOCKSIZE) unsigned char *mem; /* Memory access location with size of * memblocks * memblocksize */ unsigned int memlocation; /* Pointer to byte in *mem */ @@ -86,11 +86,26 @@ struct rand_data { unsigned int memblocksize; /* Size of one memory block in bytes */ unsigned int memaccessloops; /* Number of memory accesses per random * bit generation */ + + /* Repetition Count Test */ + unsigned int rct_count; /* Number of stuck values */ + + /* Adaptive Proportion Test cutoff values */ + unsigned int apt_cutoff; /* Intermittent health test failure */ + unsigned int apt_cutoff_permanent; /* Permanent health test failure */ +#define JENT_APT_WINDOW_SIZE 512 /* Data window size */ + /* LSB of time stamp to process */ +#define JENT_APT_LSB 16 +#define JENT_APT_WORD_MASK (JENT_APT_LSB - 1) + unsigned int apt_observations; /* Number of collected observations */ + unsigned int apt_count; /* APT counter */ + unsigned int apt_base; /* APT base reference */ + unsigned int health_failure; /* Record health failure */ + + unsigned int apt_base_set:1; /* APT base reference set? */ }; /* Flags that can be used to initialize the RNG */ -#define JENT_DISABLE_STIR (1<<0) /* Disable stirring the entropy pool */ -#define JENT_DISABLE_UNBIAS (1<<1) /* Disable the Von-Neuman Unbiaser */ #define JENT_DISABLE_MEMORY_ACCESS (1<<2) /* Disable memory access for more * entropy, saves MEMORY_SIZE RAM for * entropy collector */ @@ -99,39 +114,274 @@ struct rand_data { #define JENT_ENOTIME 1 /* Timer service not available */ #define JENT_ECOARSETIME 2 /* Timer too coarse for RNG */ #define JENT_ENOMONOTONIC 3 /* Timer is not monotonic increasing */ -#define JENT_EMINVARIATION 4 /* Timer variations too small for RNG */ #define JENT_EVARVAR 5 /* Timer does not produce variations of * variations (2nd derivation of time is * zero). */ -#define JENT_EMINVARVAR 6 /* Timer variations of variations is tooi - * small. */ +#define JENT_ESTUCK 8 /* Too many stuck results during init. */ +#define JENT_EHEALTH 9 /* Health test failed during initialization */ +#define JENT_ERCT 10 /* RCT failed during initialization */ +#define JENT_EHASH 11 /* Hash self test failed */ +#define JENT_EMEM 12 /* Can't allocate memory for initialization */ + +#define JENT_RCT_FAILURE 1 /* Failure in RCT health test. */ +#define JENT_APT_FAILURE 2 /* Failure in APT health test. */ +#define JENT_PERMANENT_FAILURE_SHIFT 16 +#define JENT_PERMANENT_FAILURE(x) (x << JENT_PERMANENT_FAILURE_SHIFT) +#define JENT_RCT_FAILURE_PERMANENT JENT_PERMANENT_FAILURE(JENT_RCT_FAILURE) +#define JENT_APT_FAILURE_PERMANENT JENT_PERMANENT_FAILURE(JENT_APT_FAILURE) + +/* + * The output n bits can receive more than n bits of min entropy, of course, + * but the fixed output of the conditioning function can only asymptotically + * approach the output size 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 JENT_ENTROPY_SAFETY_FACTOR 64 + +#include <linux/array_size.h> +#include <linux/fips.h> +#include <linux/minmax.h> +#include "jitterentropy.h" /*************************************************************************** - * Helper functions + * Adaptive Proportion Test + * + * This test complies with SP800-90B section 4.4.2. ***************************************************************************/ -void jent_get_nstime(__u64 *out); -__u64 jent_rol64(__u64 word, unsigned int shift); -void *jent_zalloc(unsigned int len); -void jent_zfree(void *ptr); -int jent_fips_enabled(void); -void jent_panic(char *s); -void jent_memcpy(void *dest, const void *src, unsigned int n); +/* + * See the SP 800-90B comment #10b for the corrected cutoff for the SP 800-90B + * APT. + * https://www.untruth.org/~josh/sp80090b/UL%20SP800-90B-final%20comments%20v1.9%2020191212.pdf + * 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 the alpha < 2^-53, R cannot be used as it uses a float data type without + * arbitrary precision. A SageMath script is used to calculate those cutoff + * values. + * + * 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 }; +static const unsigned int jent_apt_cutoff_permanent_lookup[15] = { + 355, 447, 479, 494, 502, 507, 510, 512, + 512, 512, 512, 512, 512, 512, 512 }; + +static 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]; + ec->apt_cutoff_permanent = jent_apt_cutoff_permanent_lookup[ + ARRAY_SIZE(jent_apt_cutoff_permanent_lookup) - 1]; + } else { + ec->apt_cutoff = jent_apt_cutoff_lookup[osr - 1]; + ec->apt_cutoff_permanent = + jent_apt_cutoff_permanent_lookup[osr - 1]; + } +} +/* + * Reset the APT counter + * + * @ec [in] Reference to entropy collector + */ +static void jent_apt_reset(struct rand_data *ec, unsigned int delta_masked) +{ + /* Reset APT counter */ + ec->apt_count = 0; + ec->apt_base = delta_masked; + ec->apt_observations = 0; +} + +/* + * Insert a new entropy event into APT + * + * @ec [in] Reference to entropy collector + * @delta_masked [in] Masked time delta to process + */ +static void jent_apt_insert(struct rand_data *ec, unsigned int delta_masked) +{ + /* Initialize the base reference */ + if (!ec->apt_base_set) { + ec->apt_base = delta_masked; + ec->apt_base_set = 1; + return; + } + + if (delta_masked == ec->apt_base) { + ec->apt_count++; -/** + /* Note, ec->apt_count starts with one. */ + if (ec->apt_count >= ec->apt_cutoff_permanent) + ec->health_failure |= JENT_APT_FAILURE_PERMANENT; + else if (ec->apt_count >= ec->apt_cutoff) + ec->health_failure |= JENT_APT_FAILURE; + } + + ec->apt_observations++; + + if (ec->apt_observations >= JENT_APT_WINDOW_SIZE) + jent_apt_reset(ec, delta_masked); +} + +/*************************************************************************** + * 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 (stuck) { + ec->rct_count++; + + /* + * The cutoff value is based on the following consideration: + * alpha = 2^-30 or 2^-60 as recommended in SP800-90B. + * 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 + * or 60*osr. + */ + if ((unsigned int)ec->rct_count >= (60 * ec->osr)) { + ec->rct_count = -1; + ec->health_failure |= JENT_RCT_FAILURE_PERMANENT; + } else if ((unsigned int)ec->rct_count >= (30 * ec->osr)) { + ec->rct_count = -1; + ec->health_failure |= JENT_RCT_FAILURE; + } + } else { + /* Reset RCT */ + ec->rct_count = 0; + } +} + +static inline __u64 jent_delta(__u64 prev, __u64 next) +{ +#define JENT_UINT64_MAX (__u64)(~((__u64) 0)) + return (prev < next) ? (next - prev) : + (JENT_UINT64_MAX - prev + 1 + next); +} + +/* + * 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) + */ +static int jent_stuck(struct rand_data *ec, __u64 current_delta) +{ + __u64 delta2 = jent_delta(ec->last_delta, current_delta); + __u64 delta3 = jent_delta(ec->last_delta2, delta2); + + ec->last_delta = current_delta; + ec->last_delta2 = delta2; + + /* + * Insert the result of the comparison of two back-to-back time + * deltas. + */ + jent_apt_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 + * 1<<JENT_PERMANENT_FAILURE_SHIFT RCT permanent failure + * 2<<JENT_PERMANENT_FAILURE_SHIFT APT permanent failure + */ +static unsigned int jent_health_failure(struct rand_data *ec) +{ + /* Test is only enabled in FIPS mode */ + if (!fips_enabled) + return 0; + + return ec->health_failure; +} + +/*************************************************************************** + * Noise sources + ***************************************************************************/ + +/* * 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 __u64 jent_loop_shuffle(struct rand_data *ec, - unsigned int bits, unsigned int min) +static __u64 jent_loop_shuffle(unsigned int bits, unsigned int min) { __u64 time = 0; __u64 shuffle = 0; @@ -139,17 +389,12 @@ static __u64 jent_loop_shuffle(struct rand_data *ec, unsigned int mask = (1<<bits) - 1; jent_get_nstime(&time); + /* - * mix the current state of the random number into the shuffle - * calculation to balance that shuffle a bit more - */ - if (ec) - time ^= ec->data; - /* - * we fold the time value as much as possible to ensure that as many - * bits of the time stamp are included as possible + * 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++) { + for (i = 0; ((DATA_SIZE_BITS + bits - 1) / bits) > i; i++) { shuffle ^= time & mask; time = time >> bits; } @@ -161,75 +406,40 @@ static __u64 jent_loop_shuffle(struct rand_data *ec, return (shuffle + (1<<min)); } -/*************************************************************************** - * Noise sources - ***************************************************************************/ - -/** +/* * CPU Jitter noise source -- this is the noise source based on the CPU * execution time jitter * - * This function folds the time into one bit units by iterating - * through the DATA_SIZE_BITS bit time value as follows: assume our time value - * is 0xabcd - * 1st loop, 1st shift generates 0xd000 - * 1st loop, 2nd shift generates 0x000d - * 2nd loop, 1st shift generates 0xcd00 - * 2nd loop, 2nd shift generates 0x000c - * 3rd loop, 1st shift generates 0xbcd0 - * 3rd loop, 2nd shift generates 0x000b - * 4th loop, 1st shift generates 0xabcd - * 4th loop, 2nd shift generates 0x000a - * Now, the values at the end of the 2nd shifts are XORed together. - * - * The code is deliberately inefficient and shall stay that way. This function - * is the root cause why the code shall be compiled without optimization. This - * function not only acts as folding operation, but this function's execution - * is used to measure the CPU execution time jitter. Any change to the loop in - * this function implies that careful retesting must be done. + * This function injects the individual bits of the time value into the + * entropy pool using a hash. * - * Input: - * @ec entropy collector struct -- may be NULL - * @time time stamp to be folded - * @loop_cnt if a value not equal to 0 is set, use the given value as number of - * loops to perform the folding + * ec [in] entropy collector + * time [in] time stamp to be injected + * stuck [in] Is the time stamp identified as stuck? * * Output: - * @folded result of folding operation - * - * @return Number of loops the folding operation is performed + * updated hash context in the entropy collector or error code */ -static __u64 jent_fold_time(struct rand_data *ec, __u64 time, - __u64 *folded, __u64 loop_cnt) +static int jent_condition_data(struct rand_data *ec, __u64 time, int stuck) { - unsigned int i; - __u64 j = 0; - __u64 new = 0; -#define MAX_FOLD_LOOP_BIT 4 -#define MIN_FOLD_LOOP_BIT 0 - __u64 fold_loop_cnt = - jent_loop_shuffle(ec, MAX_FOLD_LOOP_BIT, MIN_FOLD_LOOP_BIT); +#define SHA3_HASH_LOOP (1<<3) + struct { + int rct_count; + unsigned int apt_observations; + unsigned int apt_count; + unsigned int apt_base; + } addtl = { + ec->rct_count, + ec->apt_observations, + ec->apt_count, + ec->apt_base + }; - /* - * 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 = 0; - for (i = 1; (DATA_SIZE_BITS) >= i; i++) { - __u64 tmp = time << (DATA_SIZE_BITS - i); - - tmp = tmp >> (DATA_SIZE_BITS - 1); - new ^= tmp; - } - } - *folded = new; - return fold_loop_cnt; + return jent_hash_time(ec->hash_state, time, (u8 *)&addtl, sizeof(addtl), + SHA3_HASH_LOOP, stuck); } -/** +/* * Memory Access noise source -- this is a noise source based on variations in * memory access times * @@ -247,27 +457,23 @@ static __u64 jent_fold_time(struct rand_data *ec, __u64 time, * 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 + * @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 + * number of loops to perform the LFSR */ -static unsigned int jent_memaccess(struct rand_data *ec, __u64 loop_cnt) +static void jent_memaccess(struct rand_data *ec, __u64 loop_cnt) { - unsigned char *tmpval = NULL; unsigned int wrap = 0; __u64 i = 0; #define MAX_ACC_LOOP_BIT 7 #define MIN_ACC_LOOP_BIT 0 __u64 acc_loop_cnt = - jent_loop_shuffle(ec, MAX_ACC_LOOP_BIT, MIN_ACC_LOOP_BIT); + jent_loop_shuffle(MAX_ACC_LOOP_BIT, MIN_ACC_LOOP_BIT); if (NULL == ec || NULL == ec->mem) - return 0; + return; wrap = ec->memblocksize * ec->memblocks; /* @@ -278,7 +484,7 @@ static unsigned int jent_memaccess(struct rand_data *ec, __u64 loop_cnt) acc_loop_cnt = loop_cnt; for (i = 0; i < (ec->memaccessloops + acc_loop_cnt); i++) { - tmpval = ec->mem + ec->memlocation; + unsigned char *tmpval = ec->mem + ec->memlocation; /* * memory access: just add 1 to one byte, * wrap at 255 -- memory access implies read @@ -293,61 +499,29 @@ static unsigned int jent_memaccess(struct rand_data *ec, __u64 loop_cnt) ec->memlocation = ec->memlocation + ec->memblocksize - 1; ec->memlocation = ec->memlocation % wrap; } - return i; } /*************************************************************************** * Start of entropy processing logic ***************************************************************************/ - -/** - * 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 void jent_stuck(struct rand_data *ec, __u64 current_delta) -{ - __s64 delta2 = ec->last_delta - current_delta; - __s64 delta3 = delta2 - ec->last_delta2; - - ec->last_delta = current_delta; - ec->last_delta2 = delta2; - - if (!current_delta || !delta2 || !delta3) - ec->stuck = 1; -} - -/** +/* * This is the heart of the entropy generation: calculate time deltas and - * use the CPU jitter in the time deltas. The jitter is folded into one - * bit. You can call this function the "random bit generator" as it - * produces one random bit per invocation. + * 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 + * @ec [in] Reference to entropy collector * - * @return One random bit + * @return result of stuck test */ -static __u64 jent_measure_jitter(struct rand_data *ec) +static int jent_measure_jitter(struct rand_data *ec, __u64 *ret_current_delta) { __u64 time = 0; - __u64 data = 0; __u64 current_delta = 0; + int stuck; /* Invoke one noise source before time measurement to add variations */ jent_memaccess(ec, 0); @@ -357,209 +531,54 @@ static __u64 jent_measure_jitter(struct rand_data *ec) * invocation to measure the timing variations */ jent_get_nstime(&time); - current_delta = time - ec->prev_time; + current_delta = jent_delta(ec->prev_time, time); ec->prev_time = time; - /* Now call the next noise sources which also folds the data */ - jent_fold_time(ec, current_delta, &data, 0); - - /* - * Check whether we have a stuck measurement. The enforcement - * is performed after the stuck value has been mixed into the - * entropy pool. - */ - jent_stuck(ec, current_delta); - - return data; -} - -/** - * Von Neuman unbias as explained in RFC 4086 section 4.2. As shown in the - * documentation of that RNG, the bits from jent_measure_jitter are considered - * independent which implies that the Von Neuman unbias operation is applicable. - * A proof of the Von-Neumann unbias operation to remove skews is given in the - * document "A proposal for: Functionality classes for random number - * generators", version 2.0 by Werner Schindler, section 5.4.1. - * - * Input: - * @entropy_collector Reference to entropy collector - * - * @return One random bit - */ -static __u64 jent_unbiased_bit(struct rand_data *entropy_collector) -{ - do { - __u64 a = jent_measure_jitter(entropy_collector); - __u64 b = jent_measure_jitter(entropy_collector); + /* Check whether we have a stuck measurement. */ + stuck = jent_stuck(ec, current_delta); - if (a == b) - continue; - if (1 == a) - return 1; - else - return 0; - } while (1); -} + /* Now call the next noise sources which also injects the data */ + if (jent_condition_data(ec, current_delta, stuck)) + stuck = 1; -/** - * 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 { - __u64 u64; - __u32 u32[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; + /* return the raw entropy value */ + if (ret_current_delta) + *ret_current_delta = current_delta; - /* - * 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.u32[1] = 0x67452301; - constant.u32[0] = 0xefcdab89; - mixer.u32[1] = 0x98badcfe; - mixer.u32[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.u64 ^= constant.u64; - mixer.u64 = jent_rol64(mixer.u64, 1); - } - entropy_collector->data ^= mixer.u64; + return stuck; } -/** +/* * Generator of one 64 bit random number - * Function fills rand_data->data + * Function fills rand_data->hash_state * - * Input: - * @ec Reference to entropy collector + * @ec [in] 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); + unsigned int k = 0, safety_factor = 0; - while (1) { - __u64 data = 0; + if (fips_enabled) + safety_factor = JENT_ENTROPY_SAFETY_FACTOR; - if (ec->disable_unbias == 1) - data = jent_measure_jitter(ec); - else - data = jent_unbiased_bit(ec); + /* priming of the ->prev_time value */ + jent_measure_jitter(ec, NULL); - /* enforcement of the jent_stuck test */ - if (ec->stuck) { - /* - * We only mix in the bit considered not appropriate - * without the LSFR. The reason is that if we apply - * the LSFR and we do not rotate, the 2nd bit with LSFR - * will cancel out the first LSFR application on the - * bad bit. - * - * And we do not rotate as we apply the next bit to the - * current bit location again. - */ - ec->data ^= data; - ec->stuck = 0; + while (!jent_health_failure(ec)) { + /* If a stuck measurement is received, repeat measurement */ + if (jent_measure_jitter(ec, NULL)) continue; - } - - /* - * Fibonacci LSFR with polynom 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 polynom values minus one - * due to counting bits from 0 to 63). As the current - * position is always the LSB, the polynom only needs - * to shift data in from the left without wrap. - */ - ec->data ^= data; - ec->data ^= ((ec->data >> 63) & 1); - ec->data ^= ((ec->data >> 60) & 1); - ec->data ^= ((ec->data >> 55) & 1); - ec->data ^= ((ec->data >> 30) & 1); - ec->data ^= ((ec->data >> 27) & 1); - ec->data ^= ((ec->data >> 22) & 1); - ec->data = jent_rol64(ec->data, 1); /* * We multiply the loop value with ->osr to obtain the * oversampling rate requested by the caller */ - if (++k >= (DATA_SIZE_BITS * ec->osr)) + if (++k >= ((DATA_SIZE_BITS + safety_factor) * 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 void jent_fips_test(struct rand_data *ec) -{ - if (!jent_fips_enabled()) - return; - - /* prime the FIPS test */ - if (!ec->old_data) { - ec->old_data = ec->data; - jent_gen_entropy(ec); - } - - if (ec->data == ec->old_data) - jent_panic("jitterentropy: Duplicate output detected\n"); - - ec->old_data = ec->data; -} - -/** +/* * Entry function: Obtain entropy for the caller. * * This function invokes the entropy gathering logic as often to generate @@ -569,17 +588,18 @@ static void jent_fips_test(struct rand_data *ec) * 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 [in] 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 0 when request is fulfilled or an error * * The following error codes can occur: - * -1 entropy_collector is NULL + * -1 entropy_collector is NULL or the generation failed + * -2 Intermittent health failure + * -3 Permanent health failure */ int jent_read_entropy(struct rand_data *ec, unsigned char *data, unsigned int len) @@ -589,16 +609,39 @@ int jent_read_entropy(struct rand_data *ec, unsigned char *data, if (!ec) return -1; - while (0 < len) { - unsigned int tocopy; + while (len > 0) { + unsigned int tocopy, health_test_result; jent_gen_entropy(ec); - jent_fips_test(ec); - if ((DATA_SIZE_BITS / 8) < len) - tocopy = (DATA_SIZE_BITS / 8); - else - tocopy = len; - jent_memcpy(p, &ec->data, tocopy); + + health_test_result = jent_health_failure(ec); + if (health_test_result > JENT_PERMANENT_FAILURE_SHIFT) { + /* + * At this point, the Jitter RNG instance is considered + * as a failed instance. There is no rerun of the + * startup test any more, because the caller + * is assumed to not further use this instance. + */ + return -3; + } else if (health_test_result) { + /* + * Perform startup health tests and return permanent + * error if it fails. + */ + if (jent_entropy_init(0, 0, NULL, ec)) { + /* Mark the permanent error */ + ec->health_failure &= + JENT_RCT_FAILURE_PERMANENT | + JENT_APT_FAILURE_PERMANENT; + return -3; + } + + return -2; + } + + tocopy = min(DATA_SIZE_BITS / 8, len); + if (jent_read_random_block(ec->hash_state, p, tocopy)) + return -1; len -= tocopy; p += tocopy; @@ -612,7 +655,8 @@ int jent_read_entropy(struct rand_data *ec, unsigned char *data, ***************************************************************************/ struct rand_data *jent_entropy_collector_alloc(unsigned int osr, - unsigned int flags) + unsigned int flags, + void *hash_state) { struct rand_data *entropy_collector; @@ -624,26 +668,28 @@ struct rand_data *jent_entropy_collector_alloc(unsigned int osr, /* Allocate memory for adding variations based on memory * access */ - entropy_collector->mem = jent_zalloc(JENT_MEMORY_SIZE); + entropy_collector->mem = jent_kvzalloc(JENT_MEMORY_SIZE); if (!entropy_collector->mem) { jent_zfree(entropy_collector); return NULL; } - entropy_collector->memblocksize = JENT_MEMORY_BLOCKSIZE; - entropy_collector->memblocks = JENT_MEMORY_BLOCKS; + entropy_collector->memblocksize = + CONFIG_CRYPTO_JITTERENTROPY_MEMORY_BLOCKSIZE; + entropy_collector->memblocks = + CONFIG_CRYPTO_JITTERENTROPY_MEMORY_BLOCKS; entropy_collector->memaccessloops = JENT_MEMORY_ACCESSLOOPS; } /* verify and set the oversampling rate */ - if (0 == osr) - osr = 1; /* minimum sampling rate is 1 */ + if (osr == 0) + osr = 1; /* H_submitter = 1 / 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; + entropy_collector->hash_state = hash_state; + + /* Initialize the APT */ + jent_apt_init(entropy_collector, osr); /* fill the data pad with non-zero values */ jent_gen_entropy(entropy_collector); @@ -653,20 +699,39 @@ struct rand_data *jent_entropy_collector_alloc(unsigned int osr, void jent_entropy_collector_free(struct rand_data *entropy_collector) { - jent_zfree(entropy_collector->mem); + jent_kvzfree(entropy_collector->mem, JENT_MEMORY_SIZE); entropy_collector->mem = NULL; jent_zfree(entropy_collector); - entropy_collector = NULL; } -int jent_entropy_init(void) +int jent_entropy_init(unsigned int osr, unsigned int flags, void *hash_state, + struct rand_data *p_ec) { - int i; - __u64 delta_sum = 0; - __u64 old_delta = 0; - int time_backwards = 0; - int count_var = 0; - int count_mod = 0; + /* + * If caller provides an allocated ec, reuse it which implies that the + * health test entropy data is used to further still the available + * entropy pool. + */ + struct rand_data *ec = p_ec; + int i, time_backwards = 0, ret = 0, ec_free = 0; + unsigned int health_test_result; + + if (!ec) { + ec = jent_entropy_collector_alloc(osr, flags, hash_state); + if (!ec) + return JENT_EMEM; + ec_free = 1; + } else { + /* Reset the APT */ + jent_apt_reset(ec, 0); + /* Ensure that a new APT base is obtained */ + ec->apt_base_set = 0; + /* Reset the RCT */ + ec->rct_count = 0; + /* Reset intermittent, leave permanent health test result */ + ec->health_failure &= (~JENT_RCT_FAILURE); + ec->health_failure &= (~JENT_APT_FAILURE); + } /* We could perform statistical tests here, but the problem is * that we only have a few loop counts to do testing. These @@ -689,31 +754,34 @@ int jent_entropy_init(void) /* * TESTLOOPCOUNT needs some loops to identify edge systems. 100 is * definitely too little. + * + * SP800-90B requires at least 1024 initial test cycles. */ -#define TESTLOOPCOUNT 300 +#define TESTLOOPCOUNT 1024 #define CLEARCACHE 100 for (i = 0; (TESTLOOPCOUNT + CLEARCACHE) > i; i++) { - __u64 time = 0; - __u64 time2 = 0; - __u64 folded = 0; - __u64 delta = 0; - unsigned int lowdelta = 0; + __u64 start_time = 0, end_time = 0, delta = 0; - jent_get_nstime(&time); - jent_fold_time(NULL, time, &folded, 1<<MIN_FOLD_LOOP_BIT); - jent_get_nstime(&time2); + /* Invoke core entropy collection logic */ + jent_measure_jitter(ec, &delta); + end_time = ec->prev_time; + start_time = ec->prev_time - delta; /* test whether timer works */ - if (!time || !time2) - return JENT_ENOTIME; - delta = time2 - time; + if (!start_time || !end_time) { + ret = JENT_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 JENT_ECOARSETIME; + if (!delta || (end_time == start_time)) { + ret = JENT_ECOARSETIME; + goto out; + } /* * up to here we did not modify any variable that will be @@ -722,36 +790,12 @@ int jent_entropy_init(void) * etc. with the goal to clear it to get the worst case * measurements. */ - if (CLEARCACHE > i) + if (i < CLEARCACHE) continue; /* test whether we have an increasing timer */ - if (!(time2 > time)) + if (!(end_time > start_time)) time_backwards++; - - /* - * Avoid modulo of 64 bit integer to allow code to compile - * on 32 bit architectures. - */ - 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 (i) { - if (delta != old_delta) - count_var++; - if (delta > old_delta) - delta_sum += (delta - old_delta); - else - delta_sum += (old_delta - delta); - } - old_delta = delta; } /* @@ -761,27 +805,22 @@ int jent_entropy_init(void) * should not fail. The value of 3 should cover the NTP case being * performed during our test run. */ - if (3 < time_backwards) - return JENT_ENOMONOTONIC; - /* Error if the time variances are always identical */ - if (!delta_sum) - return JENT_EVARVAR; + if (time_backwards > 3) { + ret = JENT_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 JENT_EMINVARVAR; + /* Did we encounter a health test failure? */ + health_test_result = jent_health_failure(ec); + if (health_test_result) { + ret = (health_test_result & JENT_RCT_FAILURE) ? JENT_ERCT : + JENT_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 JENT_ECOARSETIME; +out: + if (ec_free) + jent_entropy_collector_free(ec); - return 0; + return ret; } |