4 files changed, 241 insertions, 2 deletions

diff --git a/sys/dev/random/fortuna.c b/sys/dev/random/fortuna.c
index c4282c723a44..8363de99a60a 100644
--- a/sys/dev/random/fortuna.c
+++ b/sys/dev/random/fortuna.c
@@ -341,6 +341,13 @@ random_fortuna_process_event(struct harvest_event *event)
 	u_int pl;
 
 	RANDOM_RESEED_LOCK();
+	/*
+	 * Run SP 800-90B health tests on the source if so configured.
+	 */
+	if (!random_harvest_healthtest(event)) {
+		RANDOM_RESEED_UNLOCK();
+		return;
+	}
 	/*-
 	 * FS&K - P_i = P_i|<harvested stuff>
 	 * Accumulate the event into the appropriate pool
diff --git a/sys/dev/random/random_harvestq.c b/sys/dev/random/random_harvestq.c
index 395310b115fb..c7762967c4fb 100644
--- a/sys/dev/random/random_harvestq.c
+++ b/sys/dev/random/random_harvestq.c
@@ -88,6 +88,8 @@ static void random_sources_feed(void);
 static __read_mostly bool epoch_inited;
 static __read_mostly epoch_t rs_epoch;
 
+static const char *random_source_descr[ENTROPYSOURCE];
+
 /*
  * How many events to queue up. We create this many items in
  * an 'empty' queue, then transfer them to the 'harvest' queue with
@@ -299,6 +301,230 @@ random_sources_feed(void)
 	explicit_bzero(entropy, sizeof(entropy));
 }
 
+/*
+ * State used for conducting NIST SP 800-90B health tests on entropy sources.
+ */
+static struct health_test_softc {
+	uint32_t ht_rct_value[HARVESTSIZE + 1];
+	u_int ht_rct_count;	/* number of samples with the same value */
+	u_int ht_rct_limit;	/* constant after init */
+
+	uint32_t ht_apt_value[HARVESTSIZE + 1];
+	u_int ht_apt_count;	/* number of samples with the same value */
+	u_int ht_apt_seq;	/* sequence number of the last sample */
+	u_int ht_apt_cutoff;	/* constant after init */
+
+	uint64_t ht_total_samples;
+	bool ondemand;		/* Set to true to restart the state machine */
+	enum {
+		INIT = 0,	/* initial state */
+		DISABLED,	/* health checking is disabled */
+		STARTUP,	/* doing startup tests, samples are discarded */
+		STEADY,		/* steady-state operation */
+		FAILED,		/* health check failed, discard samples */
+	} ht_state;
+} healthtest[ENTROPYSOURCE];
+
+#define	RANDOM_SELFTEST_STARTUP_SAMPLES	1024	/* 4.3, requirement 4 */
+#define	RANDOM_SELFTEST_APT_WINDOW	512	/* 4.4.2 */
+
+static void
+copy_event(uint32_t dst[static HARVESTSIZE + 1],
+    const struct harvest_event *event)
+{
+	memset(dst, 0, sizeof(uint32_t) * (HARVESTSIZE + 1));
+	memcpy(dst, event->he_entropy, event->he_size);
+	dst[HARVESTSIZE] = event->he_somecounter;
+}
+
+static void
+random_healthtest_rct_init(struct health_test_softc *ht,
+    const struct harvest_event *event)
+{
+	ht->ht_rct_count = 1;
+	copy_event(ht->ht_rct_value, event);
+}
+
+/*
+ * Apply the repitition count test to a sample.
+ *
+ * Return false if the test failed, i.e., we observed >= C consecutive samples
+ * with the same value, and true otherwise.
+ */
+static bool
+random_healthtest_rct_next(struct health_test_softc *ht,
+    const struct harvest_event *event)
+{
+	uint32_t val[HARVESTSIZE + 1];
+
+	copy_event(val, event);
+	if (memcmp(val, ht->ht_rct_value, sizeof(ht->ht_rct_value)) != 0) {
+		ht->ht_rct_count = 1;
+		memcpy(ht->ht_rct_value, val, sizeof(ht->ht_rct_value));
+		return (true);
+	} else {
+		ht->ht_rct_count++;
+		return (ht->ht_rct_count < ht->ht_rct_limit);
+	}
+}
+
+static void
+random_healthtest_apt_init(struct health_test_softc *ht,
+    const struct harvest_event *event)
+{
+	ht->ht_apt_count = 1;
+	ht->ht_apt_seq = 1;
+	copy_event(ht->ht_apt_value, event);
+}
+
+static bool
+random_healthtest_apt_next(struct health_test_softc *ht,
+    const struct harvest_event *event)
+{
+	uint32_t val[HARVESTSIZE + 1];
+
+	if (ht->ht_apt_seq == 0) {
+		random_healthtest_apt_init(ht, event);
+		return (true);
+	}
+
+	copy_event(val, event);
+	if (memcmp(val, ht->ht_apt_value, sizeof(ht->ht_apt_value)) == 0) {
+		ht->ht_apt_count++;
+		if (ht->ht_apt_count >= ht->ht_apt_cutoff)
+			return (false);
+	}
+
+	ht->ht_apt_seq++;
+	if (ht->ht_apt_seq == RANDOM_SELFTEST_APT_WINDOW)
+		ht->ht_apt_seq = 0;
+
+	return (true);
+}
+
+/*
+ * Run the health tests for the given event.  This is assumed to be called from
+ * a serialized context.
+ */
+bool
+random_harvest_healthtest(const struct harvest_event *event)
+{
+	struct health_test_softc *ht;
+
+	ht = &healthtest[event->he_source];
+
+	/*
+	 * Was on-demand testing requested?  Restart the state machine if so,
+	 * restarting the startup tests.
+	 */
+	if (atomic_load_bool(&ht->ondemand)) {
+		atomic_store_bool(&ht->ondemand, false);
+		ht->ht_state = INIT;
+	}
+
+	switch (ht->ht_state) {
+	case __predict_false(INIT):
+		/* Store the first sample and initialize test state. */
+		random_healthtest_rct_init(ht, event);
+		random_healthtest_apt_init(ht, event);
+		ht->ht_total_samples = 0;
+		ht->ht_state = STARTUP;
+		return (false);
+	case DISABLED:
+		/* No health testing for this source. */
+		return (true);
+	case STEADY:
+	case STARTUP:
+		ht->ht_total_samples++;
+		if (random_healthtest_rct_next(ht, event) &&
+		    random_healthtest_apt_next(ht, event)) {
+			if (ht->ht_state == STARTUP &&
+			    ht->ht_total_samples >=
+			    RANDOM_SELFTEST_STARTUP_SAMPLES) {
+				printf(
+			    "random: health test passed for source %s\n",
+				    random_source_descr[event->he_source]);
+				ht->ht_state = STEADY;
+			}
+			return (ht->ht_state == STEADY);
+		}
+		ht->ht_state = FAILED;
+		printf(
+	    "random: health test failed for source %s, discarding samples\n",
+		    random_source_descr[event->he_source]);
+		/* FALLTHROUGH */
+	case FAILED:
+		return (false);
+	}
+}
+
+static bool nist_healthtest_enabled = false;
+SYSCTL_BOOL(_kern_random, OID_AUTO, nist_healthtest_enabled,
+    CTLFLAG_RDTUN, &nist_healthtest_enabled, 0,
+    "Enable NIST SP 800-90B health tests for noise sources");
+
+static void
+random_healthtest_init(enum random_entropy_source source)
+{
+	struct health_test_softc *ht;
+
+	ht = &healthtest[source];
+	KASSERT(ht->ht_state == INIT,
+	    ("%s: health test state is %d for source %d",
+	    __func__, ht->ht_state, source));
+
+	/*
+	 * If health-testing is enabled, validate all sources except CACHED and
+	 * VMGENID: they are deterministic sources used only a small, fixed
+	 * number of times, so statistical testing is not applicable.
+	 */
+	if (!nist_healthtest_enabled ||
+	    source == RANDOM_CACHED || source == RANDOM_PURE_VMGENID) {
+		ht->ht_state = DISABLED;
+		return;
+	}
+
+	/*
+	 * Set cutoff values for the two tests, assuming that each sample has
+	 * min-entropy of 1 bit and allowing for an error rate of 1 in 2^{34}.
+	 * With a sample rate of RANDOM_KTHREAD_HZ, we expect to see an false
+	 * positive once in ~54.5 years.
+	 *
+	 * The RCT limit comes from the formula in section 4.4.1.
+	 *
+	 * The APT cutoff is calculated using the formula in section 4.4.2
+	 * footnote 10 with the window size changed from 512 to 511, since the
+	 * test as written counts the number of samples equal to the first
+	 * sample in the window, and thus tests W-1 samples.
+	 */
+	ht->ht_rct_limit = 35;
+	ht->ht_apt_cutoff = 330;
+}
+
+static int
+random_healthtest_ondemand(SYSCTL_HANDLER_ARGS)
+{
+	u_int mask, source;
+	int error;
+
+	mask = 0;
+	error = sysctl_handle_int(oidp, &mask, 0, req);
+	if (error != 0 || req->newptr == NULL)
+		return (error);
+
+	while (mask != 0) {
+		source = ffs(mask) - 1;
+		if (source < nitems(healthtest))
+			atomic_store_bool(&healthtest[source].ondemand, true);
+		mask &= ~(1u << source);
+	}
+	return (0);
+}
+SYSCTL_PROC(_kern_random, OID_AUTO, nist_healthtest_ondemand,
+    CTLTYPE_INT | CTLFLAG_RW | CTLFLAG_MPSAFE, NULL, 0,
+    random_healthtest_ondemand, "I",
+    "Re-run NIST SP 800-90B startup health tests for a noise source");
+
 static int
 random_check_uint_harvestmask(SYSCTL_HANDLER_ARGS)
 {
@@ -362,7 +588,8 @@ static const char *random_source_descr[ENTROPYSOURCE] = {
 	[RANDOM_SWI] = "SWI",
 	[RANDOM_FS_ATIME] = "FS_ATIME",
 	[RANDOM_UMA] = "UMA",
-	[RANDOM_CALLOUT] = "CALLOUT", /* ENVIRONMENTAL_END */
+	[RANDOM_CALLOUT] = "CALLOUT",
+	[RANDOM_RANDOMDEV] = "RANDOMDEV", /* ENVIRONMENTAL_END */
 	[RANDOM_PURE_OCTEON] = "PURE_OCTEON", /* PURE_START */
 	[RANDOM_PURE_SAFE] = "PURE_SAFE",
 	[RANDOM_PURE_GLXSB] = "PURE_GLXSB",
@@ -424,6 +651,9 @@ random_harvestq_init(void *unused __unused)
 	hc_source_mask = almost_everything_mask;
 	RANDOM_HARVEST_INIT_LOCK();
 	harvest_context.hc_active_buf = 0;
+
+	for (int i = 0; i < ENTROPYSOURCE; i++)
+		random_healthtest_init(i);
 }
 SYSINIT(random_device_h_init, SI_SUB_RANDOM, SI_ORDER_THIRD, random_harvestq_init, NULL);
 
diff --git a/sys/dev/random/random_harvestq.h b/sys/dev/random/random_harvestq.h
index 7804bf52aa4f..1d462500df85 100644
--- a/sys/dev/random/random_harvestq.h
+++ b/sys/dev/random/random_harvestq.h
@@ -49,4 +49,6 @@ random_get_cyclecount(void)
 	return ((uint32_t)get_cyclecount());
 }
 
+bool random_harvest_healthtest(const struct harvest_event *event);
+
 #endif /* SYS_DEV_RANDOM_RANDOM_HARVESTQ_H_INCLUDED */
diff --git a/sys/dev/random/randomdev.c b/sys/dev/random/randomdev.c
index 9d1c7b1167c8..ced4dd8067d9 100644
--- a/sys/dev/random/randomdev.c
+++ b/sys/dev/random/randomdev.c
@@ -312,7 +312,7 @@ randomdev_accumulate(uint8_t *buf, u_int count)
 	for (i = 0; i < RANDOM_KEYSIZE_WORDS; i += sizeof(event.he_entropy)/sizeof(event.he_entropy[0])) {
 		event.he_somecounter = random_get_cyclecount();
 		event.he_size = sizeof(event.he_entropy);
-		event.he_source = RANDOM_CACHED;
+		event.he_source = RANDOM_RANDOMDEV;
 		event.he_destination = destination++; /* Harmless cheating */
 		memcpy(event.he_entropy, entropy_data + i, sizeof(event.he_entropy));
 		p_random_alg_context->ra_event_processor(&event);