[RFC PATCH 37/41] random: implement the "Repetition Count" NIST SP800-90B health test

[Nicolai Stange]

The "Repetition Count Test" (RCT) as specified by NIST SP800-90B simply
counts the number of times the same sample value has been observed and
reports failure if an highly unlikely threshold is exceeded. The exact
values of the latter depend on the estimated per-IRQ min-entropy H as well
as on the upper bounds set on the probability of false positives. For the
latter, a maximum value of 2^-20 is recommended and with this value the
threshold can be calculated as 1 + ceil(20 / H). It should be noted that
the RCT has very poor statistical power and is only intended to detect
catastrophic noise source failures, like the get_cycles() in
add_interrupt_randomness() always returning the same constant.

Add the fields needed for maintaining the RCT state to struct health_test:
->rct_previous_delta for storing the previous sample value and ->rct_count
for keeping track of how many times this value has been observed in a row
so far.

Implement the RCT and wrap it in a new function, health_test_rct().

Make the health test entry point, health_test_process(), call it early
before invoking the APT and forward failure reports to the caller. All
other return codes from the RCT are ignored, because
- as said, the statistical power is weak and a positive outcome wouldn't
  tell anything and
- it's not desirable to make the caller, i.e. add_interrupt_randomness(),
  to further queue any entropy once the concurrently running APT has
  signaled a successful completion.

Signed-off-by: Nicolai Stange <nstange@xxxxxxx>
---
 drivers/char/random.c | 55 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 55 insertions(+)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 2c744d2a9b26..54ee082ca4a8 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -890,6 +890,9 @@ struct health_test {
 	};
 
 	u8 previous_sample;
+
+	u8 rct_previous_delta;
+	unsigned short rct_count;
 };
 
 enum health_result {
@@ -899,6 +902,43 @@ enum health_result {
 	health_discard,
 };
 
+/* Repetition count test. */
+static enum health_result
+health_test_rct(struct health_test *h, unsigned int event_entropy_shift,
+		u8 sample_delta)
+{
+	unsigned int c;
+
+	if (likely(sample_delta != h->rct_previous_delta)) {
+		h->rct_previous_delta = sample_delta;
+		h->rct_count = 0;
+		return health_dispatch;
+	}
+
+	h->rct_count++;
+	if (!h->rct_count) {
+		/* Overflow. */
+		h->rct_count = -1;
+	}
+
+	/*
+	 * With a min-entropy of H = 2^-event_entropy_shift bits per
+	 * event, the maximum probability of seing any particular
+	 * sample value (i.e. delta) is bounded by 2^-H. Thus, the
+	 * probability to observe the same events C times in a row is
+	 * less than 2^-((C - 1) * H). Limit the false positive rate
+	 * of the repetition count test to 2^-20, which yields a
+	 * cut-off value of C = 1 + 20/H. Note that the actual number
+	 * of repetitions equals ->rct_count + 1, so this offset by
+	 * one must be accounted for in the comparison below.
+	 */
+	c = 20 << event_entropy_shift;
+	if (h->rct_count >= c)
+		return health_discard;
+
+	return health_queue;
+}
+
 /* Adaptive Proportion Test */
 #define HEALTH_APT_PRESEARCH_EVENT_COUNT 7
 
@@ -1027,6 +1067,7 @@ health_test_process(struct health_test *h, unsigned int event_entropy_shift,
 		    u8 sample)
 {
 	u8 sample_delta;
+	enum health_result rct;
 
 	/*
 	 * The min-entropy estimate has been made for the lower eight
@@ -1036,6 +1077,20 @@ health_test_process(struct health_test *h, unsigned int event_entropy_shift,
 	sample_delta = sample - h->previous_sample;
 	h->previous_sample = sample;
 
+	rct = health_test_rct(h, event_entropy_shift, sample_delta);
+	if (rct == health_discard) {
+		/*
+		 * Something is really off, get_cycles() has become
+		 * (or always been) a constant.
+		 */
+		return health_discard;
+	}
+
+	/*
+	 * Otherwise return whatever the APT returns. In particular,
+	 * don't care about whether the RCT needs to consume more
+	 * samples to complete.
+	 */
 	return health_test_apt(h, event_entropy_shift, sample_delta);
 }
 
-- 
2.26.2