I was wondering what the known metrics are for studying the randomness of TRNG (besides NIST tests).
For example, for PUFs, there are known metrics such as uniformity, uniqueness, BER, etc.
$\begingroup$
$\endgroup$
10
-
1$\begingroup$ Aren't the metrics independent of the physical device? $\endgroup$– ShannonFeb 19, 2019 at 18:26
-
2$\begingroup$ Nope! It depends entirely on the physical device. You should assume the adversary knows exactly what your physical device is; they win if they can predict the output it produces, using that knowledge. The NIST tests are just a collection of very simple-minded models for how a TRNG might work, aggregated into software that fits parameters for the model and computes the resulting entropy of the model. More details on how ‘entropy tests’ work: crypto.stackexchange.com/a/58164 $\endgroup$– Squeamish OssifrageFeb 19, 2019 at 18:30
-
1$\begingroup$ This question is probably going to get a bad answer from Cnhy Hfmnx. Now isn't a good time for me to write a full answer. There are no methods to determine if RNG output is good. Only methods to determine the output is almost certainly bad. Such "metrics" are just results from ordinary statistical hypothesis testing. $\endgroup$– Future SecurityFeb 19, 2019 at 18:54
-
1$\begingroup$ The reason I asked this question is that I was studying PUF before. There are some known metrics for PUF hardwares such as uniformity. I thought, similarly, there exists metrics for TRNG. $\endgroup$– ShannonFeb 19, 2019 at 18:56
-
1$\begingroup$ There isn't a single metric of ‘uniformity’. There's min-entropy, there's total variation distance from uniform, there's KL divergence from uniform, etc. As far as cryptography is concerned, all you need is a sample with, say, >=256 bits of min-entropy: maximizing min-entropy for fixed output length or minimizing your favorite statistical distance from uniform is just a matter of performance, but once you have 256 bits of min-entropy you have enough for any cryptography you want; e.g., you can expand it into many keys with HKDF. $\endgroup$– Squeamish OssifrageFeb 19, 2019 at 19:01
|
Show 5 more comments
2 Answers
$\begingroup$
$\endgroup$
5
There are two common documents that pertain to TRNGs. There's US NIST Special Publication 800-90C, Recommendation for Random Bit Generator (RBG) Constructions, and the less sanctimonious German BSI A proposal for: Functionality classes for random number generators.
There are all sorts of stochastic measures listed therein, but they boil down to two essential ones:-
- The next bit that emerges from the TRNG has a 50.0% chance of being a "1" when measured in the long run. This determination is made via tests such as ent, diehard and dieharder, TestU01 and others. The appropriate test suite is often indicated by the output rate as some TRNGs only run at 2kbps or even less. And each of those tests are composed of smaller individual tests like counting runs and frequencies. The 50.0% value automatically infers each output value be independent from one another.
- That the output sequence doesn't repeat itself when the TRNG is restarted. This is kinda subsumed into (1) above in the most general case if you think about it.
If you accept that random is random, it clearly follows that the output of any working TRNG has to be entirely independent of the internal processes, other than speed. Some people get confused with the distinctions between an entropy source and a TRNG. The entropy source is the internal circuit that generates a non deterministic (random but often auto correlated) signal. This is then processed and independent uniformly distributed bytes are output from the TRNG. At this point, one cannot identify how the bytes were made. They're just plain bytes. You would not be able to differentiate any particular TRNG by even the most detailed inspections of their outputs.
As a couple of metrics examples, see the test certificates for the online bet365 casino ComScire TRNG using some custom tests and diehard, and the Quantis TRNG using diehard.
answered Feb 19, 2019 at 23:34
-
4$\begingroup$ Runs tests do not even imply that each subsequent bit appears independent. Even an LFSR will typically pass runs tests. Its point is only to spot specific kinds of biases. $\endgroup$– forest ♦Feb 20, 2019 at 3:34
-
$\begingroup$ @forest Not really sure why you're focusing specifically on runs tests. That's simply an example test like the parking, compression or crushing etc. $\endgroup$ Feb 21, 2019 at 16:17
-
$\begingroup$ I suspect forest was commenting on runs testing because you explicitly listed it in your answer. But forests comment would apply to any kind of such testing. $\endgroup$ Feb 21, 2019 at 16:25
-
$\begingroup$ @EllaRose Well that's not quite right is it? The "standardised" randomness tests specifically but sometimes indirectly detect bias and independence. Otherwise they wouldn't be any good at detecting randomness and no one would use them. The simplest direct independence test is the correlation metric in ent or "convolve/FFT" if you roll your own tests. All compression tests pick up non independence as that's their forte. It's entirely my personal failing, but I'm often confused with forest's tangential comments :-( $\endgroup$ Feb 21, 2019 at 17:40
-
$\begingroup$ @PaulUszak Pointing out a factual mistake in an answer is far from tangential. $\endgroup$– forest ♦Feb 23, 2019 at 4:06
$\begingroup$
$\endgroup$
The one metric that generically matters in cryptography for a physical entropy source is the min-entropy: the exponent of the most probable outcome, in bits. This depends on the physics of the entropy source. As long as it exceeds 256, you can feed a sample through a typical preimage-resistant hash function such as SHAKE256, a conditioner, and you will have what is effectively a uniform random string fit for use as cryptographic key material.
(Sometimes the physical device is called a TRNG; sometimes the composition of the physical device and the conditioner like SHAKE256 is called a TRNG.)
If your device can't produce a sample with that much min-entropy at once, but it can produce a sequence of IID samples, then you can concatenate them. The result may be much longer than 256 bits—even if it is very far from uniform in whatever is your favorite measure of statistical distance, what matters for cryptography is only that its min-entropy be at least 256 bits.
The NIST tests hypothesize various families of probabilistic models for the entropy source, fit parameters based on a sample, and then print the entropy of the models with the fitted parameters. These models are very simple-minded and were designed without knowledge of your device, so they are at best a way to spot-check particularly obvious predictable distributions—so obvious an engineer thought of them without even knowing what your device is. (More details on how ‘entropy tests’ work.)
Generic measures computed on samples from your device, designed without reference to any model of the physics of your device, have very little value in studying the security of the system. The min-entropy you advertise must be computed from a specific probabilistic model of the physics of the system to give any meaningful confidence in it.
answered Feb 20, 2019 at 5:49