diff options
Diffstat (limited to 'crypto/jitterentropy.c')
| -rw-r--r-- | crypto/jitterentropy.c | 344 |
1 files changed, 195 insertions, 149 deletions
diff --git a/crypto/jitterentropy.c b/crypto/jitterentropy.c index fe9c233ec7693..26a9048bc893d 100644 --- a/crypto/jitterentropy.c +++ b/crypto/jitterentropy.c @@ -72,11 +72,13 @@ struct rand_data { __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_BLOCKS 64 -#define JENT_MEMORY_BLOCKSIZE 32 #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 */ @@ -88,16 +90,9 @@ struct rand_data { /* Repetition Count Test */ unsigned int rct_count; /* Number of stuck values */ - /* Intermittent health test failure threshold of 2^-30 */ - /* From an SP800-90B perspective, this RCT cutoff value is equal to 31. */ - /* However, our RCT implementation starts at 1, so we subtract 1 here. */ -#define JENT_RCT_CUTOFF (31 - 1) /* Taken from SP800-90B sec 4.4.1 */ -#define JENT_APT_CUTOFF 325 /* Taken from SP800-90B sec 4.4.2 */ - /* Permanent health test failure threshold of 2^-60 */ - /* From an SP800-90B perspective, this RCT cutoff value is equal to 61. */ - /* However, our RCT implementation starts at 1, so we subtract 1 here. */ -#define JENT_RCT_CUTOFF_PERMANENT (61 - 1) -#define JENT_APT_CUTOFF_PERMANENT 355 + /* 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 @@ -105,6 +100,8 @@ struct rand_data { 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? */ }; @@ -122,6 +119,16 @@ struct rand_data { * zero). */ #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, @@ -148,6 +155,48 @@ struct rand_data { ***************************************************************************/ /* + * 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 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 }; +#define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0])) + +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 @@ -175,26 +224,22 @@ static void jent_apt_insert(struct rand_data *ec, unsigned int delta_masked) return; } - if (delta_masked == ec->apt_base) + 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); } -/* APT health test failure detection */ -static int jent_apt_permanent_failure(struct rand_data *ec) -{ - return (ec->apt_count >= JENT_APT_CUTOFF_PERMANENT) ? 1 : 0; -} - -static int jent_apt_failure(struct rand_data *ec) -{ - return (ec->apt_count >= JENT_APT_CUTOFF) ? 1 : 0; -} - /*************************************************************************** * Stuck Test and its use as Repetition Count Test * @@ -221,6 +266,30 @@ 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; @@ -275,26 +344,25 @@ static int jent_stuck(struct rand_data *ec, __u64 current_delta) return 0; } -/* RCT health test failure detection */ -static int jent_rct_permanent_failure(struct rand_data *ec) -{ - return (ec->rct_count >= JENT_RCT_CUTOFF_PERMANENT) ? 1 : 0; -} - -static int jent_rct_failure(struct rand_data *ec) -{ - return (ec->rct_count >= JENT_RCT_CUTOFF) ? 1 : 0; -} - -/* Report of health test failures */ -static int jent_health_failure(struct rand_data *ec) +/* + * 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) { - return jent_rct_failure(ec) | jent_apt_failure(ec); -} + /* Test is only enabled in FIPS mode */ + if (!fips_enabled) + return 0; -static int jent_permanent_health_failure(struct rand_data *ec) -{ - return jent_rct_permanent_failure(ec) | jent_apt_permanent_failure(ec); + return ec->health_failure; } /*************************************************************************** @@ -448,7 +516,7 @@ static void jent_memaccess(struct rand_data *ec, __u64 loop_cnt) * * @return result of stuck test */ -static int jent_measure_jitter(struct rand_data *ec) +static int jent_measure_jitter(struct rand_data *ec, __u64 *ret_current_delta) { __u64 time = 0; __u64 current_delta = 0; @@ -472,6 +540,10 @@ static int jent_measure_jitter(struct rand_data *ec) if (jent_condition_data(ec, current_delta, stuck)) stuck = 1; + /* return the raw entropy value */ + if (ret_current_delta) + *ret_current_delta = current_delta; + return stuck; } @@ -489,11 +561,11 @@ static void jent_gen_entropy(struct rand_data *ec) safety_factor = JENT_ENTROPY_SAFETY_FACTOR; /* priming of the ->prev_time value */ - jent_measure_jitter(ec); + jent_measure_jitter(ec, NULL); while (!jent_health_failure(ec)) { /* If a stuck measurement is received, repeat measurement */ - if (jent_measure_jitter(ec)) + if (jent_measure_jitter(ec, NULL)) continue; /* @@ -537,11 +609,12 @@ int jent_read_entropy(struct rand_data *ec, unsigned char *data, return -1; while (len > 0) { - unsigned int tocopy; + unsigned int tocopy, health_test_result; jent_gen_entropy(ec); - if (jent_permanent_health_failure(ec)) { + 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 @@ -549,13 +622,18 @@ int jent_read_entropy(struct rand_data *ec, unsigned char *data, * is assumed to not further use this instance. */ return -3; - } else if (jent_health_failure(ec)) { + } else if (health_test_result) { /* * Perform startup health tests and return permanent * error if it fails. */ - if (jent_entropy_init(ec->hash_state)) + 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; } @@ -592,23 +670,29 @@ 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 (osr == 0) - osr = 1; /* minimum sampling rate is 1 */ + osr = 1; /* H_submitter = 1 / osr */ entropy_collector->osr = osr; + entropy_collector->flags = flags; 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); @@ -617,25 +701,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); } -int jent_entropy_init(void *hash_state) +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; - unsigned int nonstuck = 0; - int time_backwards = 0; - int count_mod = 0; - int count_stuck = 0; - struct rand_data ec = { 0 }; - - /* Required for RCT */ - ec.osr = 1; - ec.hash_state = hash_state; + /* + * 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 @@ -664,31 +762,28 @@ int jent_entropy_init(void *hash_state) #define TESTLOOPCOUNT 1024 #define CLEARCACHE 100 for (i = 0; (TESTLOOPCOUNT + CLEARCACHE) > i; i++) { - __u64 time = 0; - __u64 time2 = 0; - __u64 delta = 0; - unsigned int lowdelta = 0; - int stuck; + __u64 start_time = 0, end_time = 0, delta = 0; /* Invoke core entropy collection logic */ - jent_get_nstime(&time); - ec.prev_time = time; - jent_condition_data(&ec, time, 0); - jent_get_nstime(&time2); + 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 = jent_delta(time, time2); + 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; - - stuck = jent_stuck(&ec, delta); + if (!delta || (end_time == start_time)) { + ret = JENT_ECOARSETIME; + goto out; + } /* * up to here we did not modify any variable that will be @@ -700,49 +795,9 @@ int jent_entropy_init(void *hash_state) if (i < CLEARCACHE) continue; - 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); - } - } - - /* Validate health test result */ - if (jent_health_failure(&ec)) - return JENT_EHEALTH; - /* 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; } /* @@ -752,31 +807,22 @@ int jent_entropy_init(void *hash_state) * should not fail. The value of 3 should cover the NTP case being * performed during our test run. */ - if (time_backwards > 3) - return JENT_ENOMONOTONIC; - - /* - * 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_EVARVAR; + if (time_backwards > 3) { + ret = JENT_ENOMONOTONIC; + 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; + /* 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; + } - /* - * If we have more than 90% stuck results, then this Jitter RNG is - * likely to not work well. - */ - if ((TESTLOOPCOUNT/10 * 9) < count_stuck) - return JENT_ESTUCK; +out: + if (ec_free) + jent_entropy_collector_free(ec); - return 0; + return ret; } |