Messages in this thread
Patch in this message
 From Nicolai Stange <> Subject [RFC PATCH 34/41] random: implement the "Adaptive Proportion" NIST SP800-90B health test Date Mon, 21 Sep 2020 09:58:50 +0200
`NIST SP800-90B requires an implementation of the "Adaptive Proportion"health test (APT) or similar for detecting noise source entropydegradations.This tests works by counting how many times the first sample value in asequence of n events occurs among the remaining n-1 samples. The test willreject if this number exceeds a certain threshold.With a min-entropy estimate of H=2^-event_entropy_shift per IRQ event, theprobability of observing any particular sample value is bounded byp <= 2^-H. Assuming i.i.d., the number of occurences of such a samplevalue among n - 1 events follows the binomial distribution with parametersn - 1 and p. The probability to observe up to k occurences of a givensample value is not less than that distribution's CDF F(n - 1, p, k) atpoint k, per the definition of CDFs and the fact thatF(n - 1, p1, k) >= F(n - 1, p2, k) for p1 <= p2 in the particular case ofBinomial distributions. It follows that an upper bound on the probabilityof observing the same value c or more times among n - 1 consecutive samplesis given by 1 - F(n - 1, p, c - 1). In conclusion, the probability of falsepositives is <= p * (1 - F(n - 1, p, c - 1)) for the Adaptive Proportiontest.NIST SP800-90B recommends to set n to either 512 or 1024 and to choose acut-off value c such that the probability of false positives is <= 2^-20.However, assuming an estimated per-IRQ entropy of 1 bit, it would take1024/128 == 8 minimum crng seed sizes worth of entropy before the APTeventually completes and the accumulated entropy may get released to theglobal reserve. Thus, it is desirable to set n such that the APT willcomplete within 128 bits worth of entropy, i.e. to n = 128 / H. However,for such relatively small values of n, an upper bound as small as 2^-20for the false positives probability would make the test's statisticalpower, i.e. the capability to detect degraded noise sources, plummet touselessness. Note that add_interrupt_randomness() will continue tounconditionally mix all events into the fast_pools, independent of theAPT's outcome. Thus, allowing for a higher probability of false positivescannot change the output distribution, but only potentially affect theentropy accounting. Choose an upper bound of 2^-16 for the probability offalse positives.The resulting cut-off values for the different supported values of per-IRQentropy estimates are tabulated below. The "power" column lists theprobabilities (again for i.i.d.) that the APT would report a failure incase the actual entropy has degraded to one half of the assumed estimate.   H     n   c    power   --------------------      1  128   87 52.5%    1/2  256  210 67.5%    1/4  512  463 76.7%    1/8 1024  973 82.8%   1/16 2048 1997 82.6%   1/32 4096 4044 85.8%   1/64 8192 8140 85.8%Add a couple of new fields to struct health_test for storing the requiredAPT state to struct health_test: - ->apt_event_count: total number of samples processed by the currently     pending APT, - ->apt_candidate: the sample value whose number of occurences the     currently pending APT is counting, - ->apt_candidate_count: the number of occurences of ->apt_candidate     the currently pending APT has encountered so far.Implement the APT logic and wrap it in a new function, health_test_apt().Invoke it from health_test_process().Signed-off-by: Nicolai Stange <nstange@suse.de>--- drivers/char/random.c | 56 +++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 54 insertions(+), 2 deletions(-)diff --git a/drivers/char/random.c b/drivers/char/random.cindex 33f9b7b59f92..131302cbc495 100644--- a/drivers/char/random.c+++ b/drivers/char/random.c@@ -880,6 +880,10 @@ static void discard_queued_entropy(struct entropy_store *r, }  struct health_test {+	unsigned short apt_event_count;+	unsigned short apt_candidate_count;+	u8 apt_candidate;+ 	u8 previous_sample; }; @@ -890,8 +894,56 @@ enum health_result { 	health_discard, }; +/* Adaptive Proportion Test */+static void health_apt_reset(struct health_test *h)+{+	h->apt_event_count = 0;+}++static enum health_result+health_test_apt(struct health_test *h, unsigned int event_entropy_shift,+		u8 sample_delta)+{+	unsigned int n = 128 << event_entropy_shift;+	/*+	 * Observing some particular sample value more often than+	 * these thresholds, specified for the different possible+	 * values of event_entropy_shift each, should have probability+	 * <= 2^-16.+	 */+	static const unsigned int c[] = {87, 210, 463, 973, 1997, 4044, 8140};++	if (!h->apt_event_count) {+		h->apt_event_count = 1;+		h->apt_candidate = sample_delta;+		h->apt_candidate_count = 0;+		return health_queue;+	}++	++h->apt_event_count;+	if (unlikely(h->apt_candidate == sample_delta &&+		     ++h->apt_candidate_count == c[event_entropy_shift])) {+		health_apt_reset(h);+		return health_discard;+	} else if (c[event_entropy_shift] - h->apt_candidate_count >+		   n - h->apt_event_count) {+		/*+		 * The currently pending APT might not have seen all n+		 * events yet, but it's already known by now that it+		 * can't fail anymore. Note that the above condition+		 * also coverts the case h->apt_event_count == n.+		 */+		health_apt_reset(h);+		return health_dispatch;+	}++	return health_queue;+}+ static void health_test_reset(struct health_test *h)-{}+{+	health_apt_reset(h);+}  static enum health_result health_test_process(struct health_test *h, unsigned int event_entropy_shift,@@ -907,7 +959,7 @@ health_test_process(struct health_test *h, unsigned int event_entropy_shift, 	sample_delta = sample - h->previous_sample; 	h->previous_sample = sample; -	return health_none;+	return health_test_apt(h, event_entropy_shift, sample_delta); }  struct fast_pool {-- 2.26.2`

Last update: 2020-09-21 10:01    [W:0.261 / U:7.072 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site