From 6252d96b0de2001b29596715c8f3345cc93324f7 Mon Sep 17 00:00:00 2001 From: Mounir IDRASSI Date: Wed, 30 Oct 2019 12:18:20 +0100 Subject: Update Jitterentropy Library to version 2.2.0 --- src/Crypto/jitterentropy-base.c | 457 ++++++++++++++++++++++++++-------------- 1 file changed, 295 insertions(+), 162 deletions(-) (limited to 'src/Crypto/jitterentropy-base.c') diff --git a/src/Crypto/jitterentropy-base.c b/src/Crypto/jitterentropy-base.c index 50544acb..241ea304 100644 --- a/src/Crypto/jitterentropy-base.c +++ b/src/Crypto/jitterentropy-base.c @@ -1,7 +1,7 @@ /* * Non-physical true random number generator based on timing jitter. * - * Copyright Stephan Mueller , 2014 - 2018 + * Copyright Stephan Mueller , 2014 - 2019 * * Design * ====== @@ -11,7 +11,7 @@ * Interface * ========= * - * See documentation in doc/ folder. + * See documentation in jitterentropy(3) man page. * * License * ======= @@ -51,6 +51,8 @@ /* Adapted for VeraCrypt */ +#include + #undef _FORTIFY_SOURCE #ifdef _MSC_VER @@ -66,23 +68,22 @@ #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 +#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 #define MAJVERSION 2 /* 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 2 /* API compatible, ABI may change, functional * enhancements only, consumer can be left unchanged if * enhancements are not considered */ -#define PATCHLEVEL 2 /* API / ABI compatible, no functional changes, no +#define PATCHLEVEL 0 /* API / ABI compatible, no functional changes, no * enhancements, bug fixes only */ +#define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0])) + /** * jent_version() - Return machine-usable version number of jent library * @@ -94,7 +95,7 @@ * 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 jitterentropy library + * @return Version number of jitterentropy library */ JENT_PRIVATE_STATIC unsigned int jent_version(void) @@ -108,15 +109,206 @@ unsigned int jent_version(void) return version; } +/*************************************************************************** + * Adaptive Proportion Test + * + * This test complies with SP800-90B section 4.4.2. + ***************************************************************************/ + +/** + * 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++; + + if (ec->apt_count >= JENT_APT_CUTOFF) + ec->health_failure = 1; + } + + 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 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 64 * OSR deltas for inserting them into + * the entropy pool which should then have (close to) 64 bits + * of entropy. + * + * 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. + */ + if ((unsigned int)ec->rct_count >= (30 * ec->osr)) { + ec->rct_count = -1; + ec->health_failure = 1; + } + } else { + ec->rct_count = 0; + } +} + +/** + * Is there an RCT health test failure? + * + * @ec [in] Reference to entropy collector + * + * @return + * 0 No health test failure + * 1 Permanent health test failure + */ +static int jent_rct_failure(struct rand_data *ec) +{ + if (ec->rct_count < 0) + return 1; + return 0; +} + +#ifdef _MSC_VER +static +#endif +VC_INLINE uint64_t jent_delta(uint64_t prev, uint64_t next) +{ + return (prev < next) ? (next - prev) : (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, uint64_t current_delta) +{ + uint64_t delta2 = jent_delta(ec->last_delta, current_delta); + uint64_t delta3 = jent_delta(ec->last_delta2, delta2); + unsigned int delta_masked = current_delta & JENT_APT_WORD_MASK; + + 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, delta_masked); + + 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 + * 0 No health test failure + * 1 Permanent health test failure + */ +static 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; +} + +/*************************************************************************** + * 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 + * @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 */ @@ -151,10 +343,6 @@ static uint64_t jent_loop_shuffle(struct rand_data *ec, 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) +static void jent_lfsr_time(struct rand_data *ec, uint64_t time, + uint64_t loop_cnt, int stuck) { 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 = + uint64_t lfsr_loop_cnt = jent_loop_shuffle(ec, MAX_FOLD_LOOP_BIT, MIN_FOLD_LOOP_BIT); /* @@ -196,8 +381,8 @@ static uint64_t jent_lfsr_time(struct rand_data *ec, uint64_t time, * needed during runtime */ if (loop_cnt) - fold_loop_cnt = loop_cnt; - for (j = 0; j < fold_loop_cnt; j++) { + lfsr_loop_cnt = loop_cnt; + for (j = 0; j < lfsr_loop_cnt; j++) { new = ec->data; for (i = 1; (DATA_SIZE_BITS) >= i; i++) { uint64_t tmp = time << (DATA_SIZE_BITS - i); @@ -224,9 +409,17 @@ static uint64_t jent_lfsr_time(struct rand_data *ec, uint64_t time, new ^= tmp; } } - ec->data = new; - return fold_loop_cnt; + /* + * 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 (SP800-90B considers the LFSR to be a + * conditioning operation) to have an identical amount of input + * data according to section 3.1.5. + */ + if (!stuck) + ec->data = new; } /** @@ -247,16 +440,13 @@ static uint64_t jent_lfsr_time(struct rand_data *ec, uint64_t 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 as + * number of loops to perform the folding */ -static unsigned int jent_memaccess(struct rand_data *ec, uint64_t loop_cnt) +static void jent_memaccess(struct rand_data *ec, uint64_t loop_cnt) { unsigned int wrap = 0; uint64_t i = 0; @@ -266,7 +456,7 @@ static unsigned int jent_memaccess(struct rand_data *ec, uint64_t loop_cnt) jent_loop_shuffle(ec, MAX_ACC_LOOP_BIT, MIN_ACC_LOOP_BIT); if (NULL == ec || NULL == ec->mem) - return 0; + return; wrap = ec->memblocksize * ec->memblocks; /* @@ -292,43 +482,11 @@ static unsigned int jent_memaccess(struct rand_data *ec, uint64_t 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 int jent_stuck(struct rand_data *ec, uint64_t current_delta) -{ - int64_t delta2 = ec->last_delta - current_delta; - int64_t delta3 = delta2 - ec->last_delta2; - - ec->last_delta = current_delta; - ec->last_delta2 = delta2; - - if (!current_delta || !delta2 || !delta3) - return 1; - - return 0; -} - /** * 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 @@ -338,8 +496,7 @@ static int jent_stuck(struct rand_data *ec, uint64_t current_delta) * 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: result of stuck test */ @@ -347,6 +504,7 @@ 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); @@ -356,22 +514,23 @@ static int 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; + /* 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_lfsr_time(ec, current_delta, 0); + jent_lfsr_time(ec, current_delta, 0, stuck); - /* Check whether we have a stuck measurement. */ - return jent_stuck(ec, current_delta); + return stuck; } /** * Generator of one 64 bit random number * Function fills rand_data->data * - * Input: - * @ec Reference to entropy collector + * @ec [in] Reference to entropy collector */ static void jent_gen_entropy(struct rand_data *ec) { @@ -394,41 +553,6 @@ static void jent_gen_entropy(struct rand_data *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; -} - /** * Entry function: Obtain entropy for the caller. * @@ -439,18 +563,18 @@ static int 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 [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 Chi-Squared test failed */ JENT_PRIVATE_STATIC ssize_t jent_read_entropy(struct rand_data *ec, char *data, size_t len) @@ -465,8 +589,13 @@ ssize_t jent_read_entropy(struct rand_data *ec, char *data, size_t len) size_t tocopy; jent_gen_entropy(ec); - if (jent_fips_test(ec)) - return -2; + + if (jent_health_failure(ec)) { + if (jent_rct_failure(ec)) + return -2; + else + return -3; + } if ((DATA_SIZE_BITS / 8) < len) tocopy = (DATA_SIZE_BITS / 8); @@ -533,11 +662,8 @@ struct rand_data *jent_entropy_collector_alloc(unsigned int osr, osr = 1; /* minimum sampling rate is 1 */ entropy_collector->osr = osr; - 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()) + entropy_collector->fips_enabled = 1; /* fill the data pad with non-zero values */ jent_gen_entropy(entropy_collector); @@ -563,6 +689,7 @@ int jent_entropy_init(void) int i; uint64_t delta_sum = 0; uint64_t old_delta = 0; + unsigned int nonstuck = 0; int time_backwards = 0; int count_mod = 0; int count_stuck = 0; @@ -570,6 +697,11 @@ int jent_entropy_init(void) memset(&ec, 0, sizeof(ec)); + /* Required for RCT */ + ec.osr = 1; + if (jent_fips_enabled()) + ec.fips_enabled = 1; + /* 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 @@ -591,8 +723,10 @@ 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++) { uint64_t time = 0; @@ -604,13 +738,14 @@ int jent_entropy_init(void) /* Invoke core entropy collection logic */ jent_get_nstime(&time); ec.prev_time = time; - jent_lfsr_time(&ec, time, 0); + jent_memaccess(&ec, 0); + jent_lfsr_time(&ec, time, 0, 0); jent_get_nstime(&time2); /* test whether timer works */ if (!time || !time2) return ENOTIME; - delta = time2 - time; + delta = jent_delta(time, time2); /* * test whether timer is fine grained enough to provide * delta even when called shortly after each other -- this @@ -633,13 +768,35 @@ int jent_entropy_init(void) if (stuck) count_stuck++; + else { + nonstuck++; + + /* + * Ensure that the APT succeeded. + * + * With the check below that count_stuck must be less + * than 10% of the overall generated raw entropy values + * it is guaranteed that the APT is invoked at + * floor((TESTLOOPCOUNT * 0.9) / 64) == 14 times. + */ + if ((nonstuck % JENT_APT_WINDOW_SIZE) == 0) { + jent_apt_reset(&ec, + delta & JENT_APT_WORD_MASK); + if (jent_health_failure(&ec)) + return EHEALTH; + } + } + + /* Validate RCT */ + if (jent_rct_failure(&ec)) + return ERCT; /* test whether we have an increasing timer */ if (!(time2 > time)) time_backwards++; /* use 32 bit value to ensure compilation on 32 bit arches */ - lowdelta = time2 - time; + lowdelta = (uint64_t)time2 - (uint64_t)time; if (!(lowdelta % 100)) count_mod++; @@ -686,32 +843,8 @@ int jent_entropy_init(void) * 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) + if ((TESTLOOPCOUNT/10 * 9) < count_stuck) return ESTUCK; return 0; } - -/*************************************************************************** - * Statistical test logic not compiled for regular operation - ***************************************************************************/ - -#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) -{ - 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)); -} -#endif /* CONFIG_CRYPTO_CPU_JITTERENTROPY_STAT */ -- cgit v1.2.3