Merging upstream version 6.7.7.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 195 insertions, 149 deletions

diff --git a/crypto/jitterentropy.c b/crypto/jitterentropy.c
index fe9c233ec7..26a9048bc8 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;
 }