Common Criteria classifies the requirements for true Random Number Generators, and specifies how these should be tested against failures (these can occur accidentally, or following deliberate attack, e.g. by very low temperature). The relevant Application note and Interpretation of the Scheme is AIS 31 version 3.0 (in German), which basically endorses five references (in English) by decreasing precedence in case of conflict:
- [RNGEV] Evaluation of random number generators, version 0.10;
- [KS2011] A proposal for: Functionality classes for random number generators, version 2.0;
- [PTGDEV] Developer evidence for the evaluation of a physical true random number generator, Version 0.8;
- [PTGEV] Evaluation Report as part of the Evaluation Technical Report, Part B, ETR-Part, True Physical and Hybrid Random Number Generator, Version 0.7;
- [AIS31V1] A proposal for: Functionality classes and evaluation methodology for true (physical) random number generators, version 3.1.
Reference [KS2011] item 408 gives an example of a statistical test that could be applied to the physical source of random bits:
The internal random numbers are interpreted as bit strings and segmented into 4-bit words. $\chi^2$ goodness-of-fit tests on 128 bits (4-bit words) are applied. The online test fails if the test value exceeds $65.0$. According to ([Kanj95], pp. 69), the test variable is approximately $\chi^2$-distributed with 15 degrees of freedom, which gives rise to the significance level $3.8\cdot 10^{-7}$.
Reference [AIS31V1] example E.6 proposes something with many commonalities:
A $\chi^2$ modification test is applied to each 80 (4-bit words) (..) The null hypothesis is rejected if the test variable is $>65.0$. According to ([Ka], 69)), the test variable is approximately $\chi^2$-distributed with 15 degrees of freedom, which gives rise to the significance level $3.8\cdot 10^{-7}$.
From that I need to devise a mathematically sensible test that is also convincingly conforming to AIS 31. In my usage context, the test can be called a highly variable number of times in the lifetime of a device (including at least on each reset), with an upper range like $10^7$. With many thousands of devices deployed, and no way to upgrade them, I do have to account and tolerate some amount of failure. Thus it is critical that I have the right test and false error rate.
One easily fixed issue is that "128 bits (4-bit words)" should be understood as "128 four-bit words" in [KS2011] items 408, 412, 421 and 423. Fortunately, this is relatively clear in item 416 commenting on 408 and considering "128 (4-bit words)", and also clarifying that 128 samples are intended, not 80. Also, "128 bits (32 four-bit words)" would not match a condition stated by ([Kanj95], pp. 69): "The expected frequency in each class should be at least 5".
We are left with the two references drawing $n=128$ or $n=80$ four-bit samples from the physical source of random bits, counting the number $O_i$ of samples within each of the 16 possible values, rejecting the source as defective if $$65.0<\sum{(O_i-n/16)^2\over n/16}$$ and claiming a false error rate of $3.8\cdot10^{-7}$, with justification referring to an approximation by a $\chi^2$ distribution with 15 degrees of freedom.
But that approximation leads to a false error rate of $3.4\cdot 10^{-8}$ (computed as 1-CDF[ChiSquareDistribution[15],65.0] in Mathematica), rather than $3.8\cdot10^{-7}$. My explanation is that "the expected frequency in each class should be at least 5" is a rule of thumb valid for usual ranges of significance level like 1% or more, and when we get to lower error rates the approximation is no longer valid, as explained in [KS2011] item 416.
I think the $3.8\cdot 10^{-7}$ false error rate applies to $n=80$; at least that is given in item 416 with (self) reference to a peer-reviewed conference paper. I once wrote a hairy C program that gave me $3.8033\cdot10^{-7}$ for $n=80$ and $1.9858\cdot10^{-7}$ for $n=128$, but I'm uncertain about its correctness; I would appreciate a simple method to derive that error rate, much preferably with a reference.
Next issue is that when I apply that test in actual devices, the failure rate seems to be an order of magnitude higher than expected; that happens only when I test the unconditioned physical source of random bits, not at all when I test cryptographically post-conditioned output, which behaves just as expected. The problem may be worse with $n=128$ than it is with $n=80$. My theory is that this effect is mostly due to a slight bias of the unconditioned physical source of random bits. I have so far failed to derive the effect of such a bias on the false error rate, and would like to know that.
Beside the two statistical questions above, now asked at Stats.SE, I'm interested to know how the apparent error in [KS2011] is dealt with in certification practice.
