2
$\begingroup$

Some assert that a theoretical model of the unconditioned source must be created when building any TRNG. It's believed to be a fundamental requirement. So a few related questions arise:-

  1. What is a "model"? For example, are we talking a simple histogram of the raw output distribution, or something like $ \sigma^2_{quantum} = \frac{\gamma}{\gamma + 1} \langle V(t)^2 \rangle $ thus $ \sim H_{Shannon} $ in laser phase interference? More generally, do they mean a posteriori (empirical summary statistics, probability density function, $V_{RMS}$ , $\delta^2_{signal}$) , or a priori (predictive) modelling like the $ V \sim -C_1(1 - e^{-\frac{t - t_a}{C_2}}) $ capacitive charge curve that governs the shape of Zener diode breakdown and the earlier laser equation? The major difference being that an empirical/a posteriori model is agnostic to any physics. Yet underlying physical processes are often mentioned.

  2. Is there any original theoretical work justifying this modelling requirement? I'm asking about any works underpinning or justifying what one might read in a NIST/BSI AIS document.

  3. What to do if the empirically measured entropy rate does not agree with a priori (predictive) modelling? Say a very significant error. A measured noise signal can easily increase 100% between two generic component types from different manufacturers (eg. BZX85C24 Zener diode).

Update:

There is now a hot network question - Is a model fitted to data or is data fitted to a model? Currently answers are leaning towards the empirical data taking priority over the theory. So you'd start with the oscilloscope and work upstream to the physicsing[sic]. As a philosophical empiricist, this seems more intuitive to me but there does seem to be a portion of members here that give precedence to math over measurement. It's a Plato v Aristotle question and I'm trying to be open minded on this one.

$\endgroup$
  • $\begingroup$ Is this in general? Or is it in reference to some document? $\endgroup$ – Future Security Mar 20 at 23:40
  • $\begingroup$ @FutureSecurity Well I was finally prompted by bullet point 1 of crypto.stackexchange.com/a/68155/23115, but it's been brewing for a long time. The need for modelling is often repeated here, and is mentioned in the FIPS/AIS 31 documents. But I'm really struggling to understand why, and why commercial vendors don't as you'll see in my comments and silly examples to fgrieu et al. UK ERNIE is a good example example. I'm most interested though in the answer to #3. $\endgroup$ – Paul Uszak Mar 21 at 0:00
  • $\begingroup$ @FutureSecurity The equation in #1 is real, from "68 Gbps quantum random number generation by measuring laser phase fluctuations". I don't have a URL. If the equation was wrong or had confounding variables, would we modify it to suit the empirical data, or would we ignore what (might be) a £100,000 Keysight oscilloscope is telling us? And therefore philosophically, if one paradigm has primacy over the other, is the less important needed at all? I also wonder if I've just misunderstood the whole concept of a "model". $\endgroup$ – Paul Uszak Mar 21 at 0:15
  • 2
    $\begingroup$ I did not "assert that a theoretical model of the unconditioned source must be created when building any TRNG". Much to the contrary: feed 400 bytes of any about working source (without any model of that) as seed to SHA-256 and you have a working TRNG.What I do assert (there) is that a model of the entropy source is needed to build a TRNG that won't deliver insecure output in case of failure of its entropy source. That's a hell of an important distinction. $\endgroup$ – fgrieu Mar 21 at 8:20
  • 1
    $\begingroup$ Indeed, your What is a "model"? is a legitimate question, and not an easy one. That's discussed by example in items 450 to 452 of Wolfgang Killmann and Werner Schindler's AIS-31 proposal, which reference their A Design for a Physical RNG with Robust Entropy Estimators, in proceedings of CHES 2008. $\endgroup$ – fgrieu Mar 21 at 16:00
4
$\begingroup$

Why use a model?

The utility of a scientific model is the ability to make predictions. An example of a simple model is one describing the motion of projectiles based on Newton's laws of motion and gravity.

You could use two strategies on a battlefield to make a cannonball land where you want it to.

You could point the cannon in the general direction of a castle and fire. If the projectile flies over the target you try again, aiming lower. If it still overshoots the castle you aim a little lower again. (Or if it falls short aim a little higher.) You try and make adjustments until you get the result you want.

Alternatively you could determine the distance between you and the target, how much higher the target is than the cannon, the initial speed of the cannonball. You model the cannonball as a point mass. You ignore the effect of drag. (It might be fine depending on how dense the cannonball is, how thin the atmosphere, how far it needs to travel.) In such an environment, a consequence of Newton's laws is that the relative position of a projectile can be determined from its initial velocity. You use the numbers and formulas to determine where to aim. Not your eyes.

The first method does not use a formal model. It is not preferable because it will waste resources and because any mistakes will put you in danger. The second method (potentially) enables you to hit your target on the first try.

Science is full of models. You want to find one that is sufficiently accurate in order to have confidence that things will work out right. You want a simple enough model for it to be practical. The Newtonian cannonball model does not describe exactly how the real world works. It simplifies things while remaining useful. For some applications you need something more complex. All models are like that.


Example

If you want to build an RNG that uses radioactive decay as it's source of unpredictability, then first you model the process of decay using the half life model. It lets you treat the physical phenomenon as a clean mathematical abstraction.

Next we figure out how much of the material you have and what fraction of the decay events we can detect. Then we use our knowledge that the half life decay model can be described as a Poisson process to create a statistical model.

The model will tell use how likely we are to detect an event in any given time slice of a certain length. If the half life is long enough and we have enough material this probability should remain accurate for a long time.

Now we have a Bernoulli process. The samples are binary (detection or non-detection), independent, and will have effectively constant probabilities.

We can look at the probabilities of the two possible outcomes. From that we can easily determine the min entropy. That number can tell us how many samples we need to take to ensure we have sufficient entropy. (And therefore also a lower limit on how long we need to wait to generate a key.)

Multiply the number of samples you need by 2 or 2000 just be conservative and paranoid. Now you know how many samples to process through a cryptographic hash before you can use the output to generate a key.

We could have stopped once we knew we could model detection as a Poisson process and not calculate probabilities. Two non-overlapping time slices are statistically independent in a Poisson process model. We could use von-Neumann's debiasing algorithm for that reason without needing to know the detection probability because (assuming the hardware is working correctly) the kind of samples we have are independent and identically distributed.

But calculating the probability gives us the opportunity to test if things are working as intended. (Use a better model to build a safer HWRNG.) If the CPU sees detections far more frequently than expected, then maybe someone is using another radioactive source to try to bias our RNG. If we see too few detections or too many identical consecutive samples then maybe a circuit has been damaged.

Note: I'm confident that I don't know how every real world radioactivity-based HWRNGs work with 100% accuracy. There could be different designs with different design justifications. Physics is not something I plan on studying further. And I'm definitely not going to bother with reverse engineering proprietary things.


Other questions

Use a histogram?

No. Don't use a histogram. Use a probability mass function.

Creating a histogram requires sampling. A histogram can only be used to estimate probabilities. If you don't know what to look for then you definitely can't tell the difference between a working system and a broken one.

You also don't want to calibrate the system based only on empirical results. It's important to know how likely components are to fail, to know whether or not aging of components will render the calibration invalid.

Calibrating to lab conditions is dangerous because the characteristics of the entropy source you use might be different at different temperatures, in different environments, as the components age, when exposed to different strengths and frequencies of electromagnetic noise, on different power supplies.

It's a better idea to use a design based on knowledge of a physical process that will be robust enough to still be unpredictable (and predictably unpredictable) in the future under different conditions.

Theoretical necessity?

Theories for why you don't need theories? Maybe. I don't know how many theoretical researchers have an interest in that niche.

Results don't match theory?

You're model is wrong or your hardware is broken. If a device isn't working the way it's expected to and there are any safety implications if it's broken, then why not fix it or use a different device? If your model is wrong and your hardware is fine, then why not find a model that does explain things?

50% error?

I don't know what metric you're using. That sounds really high.

$\endgroup$
3
$\begingroup$

Why should one model an entropy source in order to build a TRNG?

I sell two black boxes with a crank and an output display on it in my cryptography shop. You can pick one to take home for use in cryptography.

  • One box contains a gremlin who dutifully computes the bits of $\operatorname{AES}_0(0) \mathbin\| \operatorname{AES}_0(1) \mathbin\| \operatorname{AES}_0(2) \mathbin\| \cdots$ to display on the output when you turn the crank.
  • One box contains a gremlin who tosses a coin and displays the outcome when you turn the crank.

The boxes are labeled AES GREMLIN and COIN-FLIPPING GREMLIN, so the adversary, who is watching the shop through the window, knows which box you picked. You, however, deliberately ignore the labels, pick one arbitrarily, and feed the output to a generic statistical test like the NIST suite. It returns a happy result in either case, so you take it and go on your merry way.

If you took the AES GREMLIN box, you would lose against the adversary no matter what fancy cryptography you use it to generate keys for. If you took the COIN-FLIPPING GREMLIN box, well, whether you win against the adversary depends on what cryptography you use it for—and only on what cryptography you use it for, because this gremlin is as unpredictable as they get.

This is why you should pay attention to the information you have about the world, instead of deliberately ignoring it!

  1. What is a "model"? For example, are we talking a simple histogram of the raw output distribution, or something like $ \sigma^2_{quantum} = \frac{\gamma}{\gamma + 1} \langle V(t)^2 \rangle $ thus $ \sim H_{Shannon} $ in laser phase interference?

A model is a description of a probability distribution on outputs that represents your state of knowledge about what they might be. In the AES GREMLIN model, after a short computation anyone knows exactly with no uncertainty what the output will be. In the COIN-FLIPPING GREMLIN model, every possible outcome is equally probable: nobody has any reason to suspect that the next output will be 0 rather than 1 or vice versa. It might be a family of models with parameters, or it might be a composite model with Bayesian model selection, etc.

Other models include:

  • Counting the number of ionizing events in a duration of one second from a radiation source. In a short period of time, each such number will have Poisson distribution for some fixed rate $\lambda$ depending on the radiation source. Over time, the radiation source will decay, so the Poisson rate $\lambda_t$ at time $t$ will dwindle—fast, if it has a short half-life; slowly, if not.
  • Reporting 0 or 1 depending on which side of a beam-splitting polarizer a photon from an unpolarized single-photon emitter passed through. The probability of 0 or 1 from each sample depends on the structure and aberrations of the beam splitter, and on the characteristics of the emitter. If the cat disturbs the setup by jumping on the experiment table and pointing the emitter away from the splitter, the probability of 0 might go to 100%.
  1. Is there any original theoretical work justifying this modelling requirement? I'm asking about any works underpinning what one might read in a FIPS/BSI AIS document.

First principles.

The more you know about the physical device, the better you can make predictions about it, like the half-life and purity of the radiation source, or the aberrations of the beam splitter and distribution of polarizations of the emitter. If you plug up your ears and cover your eyes, that doesn't make it less predictable to an intelligent adversary!

Your job, as a designer or implementer or cryptographer, is to do the best you possibly can with the state of the art and physics and engineering to predict the outcome of the device. Then an adversary—who is at least as good at physics as you are, and who is smart enough not to ignore relevant information—might not have a much better chance at predicting it.

Further, as an engineer, you know systems break down: the uranium decays, the cat jumps on the table and knocks the beam splitter over, the silicon crystals degrade under stress of avalanche breakdown, the adversary shines a bright light on your photon detector, etc. Knowledge of the engineering enables you to predict plausible failure modes, and write tests that have a high probability of raising an alarm in all the failure modes, but low probability of false alarms when the device is working as intended.

  1. What to do if the empirically measured entropy rate does not agree with that predicted by said model? Say an error of >50%.

Background: Every model has a definite entropy. Sometimes families of models are related. For example, the following describes many related models in terms of a parameter $p$:

  • A box containing a gremlin who makes independent but biased coin tosses, coming up heads with probability $p$, and displays the outcomes, when you turn the crank.

The min-entropy of a single outcome from this model is $-\log_2 p$. Generic ‘entropy estimators’ posit really simple families of models like this; empirically guess the value of $p$ based on samples of data; and then analytically compute the entropy of the model with their guess for $p$.

Suppose you compute the entropy for your model involving a Rube Goldberg machine of a radiation source, a photon emitter, a beam splitter, an avalanche diode, and a parrot, based on your understanding of the physics and engineering and ornithology of the system. It doesn't matter that this system give the highest possible entropy per bit of output; what matters is that you do a good job computing what the entropy per bit of output is, even if it's only 0.1 bits of entropy per bit of output.

Suppose a stupid entropy estimator, which was designed without knowledge of your system because someone at NIST wrote it a decade before you even met the parrot, guesses lower entropy than you computed. This suggests that a stupid adversary, who doesn't even know how the device works, can do a better job at predicting the output than you can.

What this means is that you are bad at physicsing, and you should try harder.

There is now a hot network question - Is a model fitted to data or is data fitted to a model? Currently answers are leaning towards the empirical data taking priority over the theory. So you'd start with the oscilloscope and work upstream to the physicsing[sic]. As a philosophical empiricist, this seems more intuitive to me but there does seem to be a portion of members here that give precedence to math over measurement. It's a Plato v Aristotle question and I'm trying to be open minded on this one.

The HNQ is about a rather mundane question of phrasing, not of what the phrase means; there's nothing profound there. The asker found an article from Wolfram that described the standard process of using a set of data to find parameters in a family of models (like estimating $p$ in the above $p$-weighted gremlin); the Wolfram article said ‘fitting data to a model’ even though the observed data are fixed and the model parameters are variable, while other articles say ‘fitting models to data’; the asker asked about the discrepancy in phrasing.

Obviously when studying an ill-understood physical system to learn about it, a sensible scientist will consider many possible models and use tests to decide which ones to prefer, and hypothesize new ones on the basis of patterns seen in empirical observations.

This question is not about how to science your way into a grand unified theory of quantum gravity. There is arbitrarily much to be said about the practical and philosophical underpinnings of empirical reasoning and the formal frameworks for doing it, like frequentist statistics and hypothesis testing or Bayesian inference—of which some has been said already, but the broader topic of which is far outside the scope of crypto.se.

Rather, this question is about how to build a TRNG. For that, there is plenty of already well-understood science out there which you can use as building blocks. If you consciously ignore it all, and sit on the laurels of a dieharder run, you're doing a bad job of engineering. Will the radiation source decay? Will the silicon degrade? Will temperature, pressure, and humidity affect the result? Dieharder can't tell you about any of these.

$\endgroup$
  • $\begingroup$ Would the downvoter care to elaborate on what specifically you disagreed with? $\endgroup$ – Squeamish Ossifrage Mar 24 at 15:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.