Score:4

Weak physical random number generator/source - what is this?

tf flag
Tom

Why physical random number source can be weak? I see two kinds of problems:

  • it is hard to control it and make it resistant to some unwanted bias, but also deliberate attacks,
  • it has normal distributuon, while we usually want to have uniform distribution (that's why we use randomness extractors or KDFs).

Can anyone elaborate on this topic? What is weak physical random number generator/source and why we consider it as weak? Some physicists say that the randomness obtained in radioactive decay or thermal noise, and especially in quantum phenomena, is perfect, unquestionable (and this is also indicated by experiments with Bell's inequalities). Meanwhile, in practical applications such sources are referred to as weak.

b degnan avatar
ca flag
I've gone over this a bunch. Search for "shot noise", an example: https://crypto.stackexchange.com/questions/60297/differences-between-methods-of-hardware-random-number-generators/60309#60309 It's the only provably random process that is available when you have semiconductors (it's not actually johnson noise, to that end, if any channel noise is mentioned as johnson noise, they've missed the driver of the randomness)
Score:5
us flag

Can anyone elaborate on this topic? What is weak physical random number generator/source and why we consider it as weak? Some physicists say that the randomness obtained in radioactive decay or thermal noise, and especially in quantum phenomena, is perfect, unquestionable (and this is also indicated by experiments with Bell's inequalities). Meanwhile, in practical applications such sources are referred to as weak.

If one has some practical experience on electronic circuit design, one would immediately realize that: it's easy to find many unpredictable sources of randomness, but building an unbiased random bit generator on top of these randomness sources is not a trivial task. In fact it's fairly difficult to build a perfect electronic "coin flipper". In most cryptography textbooks, it's given for granted that there exists a true random number generator that produces an unbiased binary output, but this abstraction hides an enormous amount of implementation details and complexities.

For example, radioactive decay in principle is purely a quantum mechanical process on a microscopic scale. However, it's impractical to generate a random bit by measuring the radioactive decay of a single atom and selecting an unit time with a 50% chance for it to occur. Instead, practical devices only measure radioactivity on a macroscopic scale. For example, counting the number of pulses from a Geiger counter in 60 seconds. In this case, obtaining a straightforward binary output is no longer possible. While the output of the detector is certainly unpredictable due to its physical nature, but the degree of randomness of the detector's output is only a "weak", highly-biased, and low-entropy form. You might be able to see 20 ± 5 pulses per minutes. It's not even clear on how one could map the numbers to a binary sequence. Even if the probability distribution of the radioactive source can be modeled with infinite precision, any background noise still biases the output.

Zener diodes and avalanche diodes are another standard noise source in electronics engineering, the simplest circuit can be built by reverse biasing the base-emitter junction of a generic bipolar transistor (note: but as pointed out by Paul Uszak, Zener-connected BJTs are subject to degradation and has questionable long-term reliability, do use a real diode if you need a serious TRNG). The physical origin of the diode noise is the unpredictable movement of electrons during an avalanche breakdown, ultimately also quantum mechanical. Unfortunately, this noise can only be measured on a macroscopic scale, and all we can see is a fuzzy analog signal on an oscilloscope, not unlike an analog radio or TV tuned to a dead channel. Worse, it's not a perfect white noise source. At low frequency, semiconductor devices have a 1/f noise spectrum. Most practical electronics components also generate "excess noise" above its theoretical level due to physical imperfection.

How to convert these raw voltages to an unbiased binary sequence is not obvious. The simplest solution is comparing the voltages with an arbitrary threshold. Because the physical process is unpredictable, we know the output bitstream has some randomness. Again, it's a weak form of randomness: highly-biased, and low-entropy.

Other sources of randomness include:

  1. Thermal noise from resistors, also known as Johnson-Nyquist noise. It's produced by random thermal movement of electrons within a resistor at a temperature above absolute zero.

  2. Radio noise in the shortwave band from the atmosphere, mainly a result of lightning strikes, but is also influenced by solar activities, seasons, and man-made interference. This noise source is famously used by random.org.

  3. The jitter (phase noise) of an oscillator. For example, relaxation oscillators are notoriously unstable, with significant cycle-to-cycle jitter. Another idea is starting two different crystal oscillators at the same frequency, and see if the first oscillator is leading or lagging than the second oscillator due to jitter. The "truerand" algorithm from some old IBM PC programs was based on this idea - counting the number of CPU clock cycles between a fixed RTC timer interval.

  4. The output waveform of a chaotic circuit, such as a Chua's circuit, essentially an unstable oscillator.

  5. The metastable resolution time of a flip-flop. A digital logic circuit is just a nonlinear analog amplifier that pushes a signal strongly towards the direction of the "1" or "0" level, but one can always construct a special input to make it output "1/2", like balancing a knife on its edge. This metastable state eventually collapses to a binary output, and the time it takes is only known statistically, and thus unpredictable. This is allegedly used in Intel CPUs to implement the RDRAND instruction.

  6. Your idea here.

But all of these methods have the same problem. Not only the exact probability distribution is unknown, it's not even clear how to convert these signals into an unbiased binary sequence. In some special cases, it may be possible to create a physical model of the system, but other times it can be impractical.

Therefore, in practice, instead of trying to obtain perfect random numbers from first principles, we simply collect a large list of the heavily-biased raw output, often generated by a somewhat arbitrary method. When enough raw output is collected, the output is plugged into a hash function to obtain unbiased binary sequences, this process is usually called "whitening" or "randomness extraction". Even if the raw output is biased, as long as it contains sufficient entropy (which can be determined statistically during the design process), it's a secure system.

Peter Cordes avatar
us flag
My first thought for generating randomness from a geiger counter would be to sample (the low bits of) a high-resolution clock at each event. Total count over a fixed interval throws away a huge amount of timing information. Sampling a clock might even be a good example of a "weak" entropy source, as your counter might have too many bits and tend to be monotonically increasing if you look at the whole value. i.e. less randomness in the high bits. But with a fast enough counter, the low bits should all be uncorrelated from each other. And there's a soft boundary where there's some entropy.
Peter Cordes avatar
us flag
Re: Intel's RDRAND: https://www.electronicdesign.com/resources/article/21796238/understanding-intels-ivy-bridge-random-number-generator discusses the metastable flip-flop which settles due to thermal noise. Interesting, I'd just seen it described as "thermal noise" before, without mention of the metastable flip-flop. The article also discusses how the entropy is "conditioned" or "whitened" by feeding it through AES.
Paul Uszak avatar
cn flag
Err, please see [Are reverse biased transistors stable?](https://electronics.stackexchange.com/q/289058/56469). It's a common error for DIY TRNG makers.
比尔盖子 avatar
us flag
@PaulUszak Interesting. So reverse-biased BJTs actually have questionable long-term reliability. I'll definitely use a real Zener diode if I'm going to build this circuit one day... Updated answer with your warning.
Paul Uszak avatar
cn flag
Yes, also see http://robseward.com/misc/RNG2/#new_design for the effect. And http://www.reallyreallyrandom.com/zener/breadboard/ if you want to have a bash. It's easy...
Score:4
sa flag

Well, physical processes are not necessarily easy to control or to model; This is with respect to independence and uniformity of their output.

Both your points are correct, and in fact it's not just a matter of being gaussian vs uniform. And these need to be processed as you pointed out, by extractors etc.

It doesn't matter if the decay is quantum, the output is still not ideal and ready to use. And how confident can you be that there are no environmental processes that can interfere with a quantum generator?

Just as an example, radioactive decay is normally measured by an exponential process assuming environment parameters are constant. This means that the average time between decays assuming stationarity is an exponential random variable, with $$ Pr[T_i>t]=\exp(-\lambda t) $$ for a constant $\lambda.$

If you know $\lambda$ you can divide time into intervals of length $T_0$ such that $$\exp(-\lambda T_0)=1/2$$ and output a one if there is a decay zero otherwise.

There are many reasons this is probably too simplistic, plus the issue of the environmental interference (natural or malicious) with the source statistics, as mentioned above.

So it may be better to treat $\lambda$ as unknown pick some $T_0$ by observing the source decay rate, and apply an unbiasing algorithm and then pass blocks of long enough output strings through a secure hash function to be sure.

If the source decay rate changes significantly you can adjust $T_0.$

Score:0
cn flag

I don't recognize the characterization of an entropy source as weak. Rinivasan AND Zuckerman say "Thus we model a weak random source as outputting bits that are slightly random but not perfectly random". I don't know what that means - no bias? Unlikely in reality as unacceptable biases are typically $> 2^{-64}$. Bias is de rigueur and so to be expected. If they were 'perfectly' random , they'd be TRNGs and not entropy sources requiring extractors.

Entropy sources are what entropy sources are, but don't forget that no entropy source generates any sort of entropy. At all. Nada. Entropy is created by the observer sampling the source at a certain resolution $(\epsilon)$ and rate $(\tau^{-1})$. This gives rise to the notion of $ (\epsilon, \tau) $ per unit time entropy rates.

Individual sample distributions are pretty much irrelevant. Source and sample regime combinations can produce all sorts of distributions like gamma, log normal, bath tub e.t.c

I suggest that if you're going to use the word "weak", then use it as a metaphor for "unstable". The worst form of entropy source is one that is unstable. And by stability I exclude thermal variability. It is said that all electronic equipment is first and foremost a temperature sensor. We can allow for that though by measuring the $ (\epsilon, \tau)_{H_{\infty}} $ rate appropriately and subtracting $ n \sigma_{H_{\infty}} $. 0.05 bits /sample is not weak for a typical ring oscillator. Nor is 2 bits /sample when photon counting.

So by weak, I mean non steady sources, e.g. meta-stability, the inputs to the Linux RNG and Chau circuits. They are definitely hard to control, and you can see the extensive mitigations within the Linux RNG and its driver. I would avoid if at all possible.

I also exclude RNG attacks from the notion of weakness. No TRNG is fully attack resistant, and resistance diminishes the further downstream you look. A source resistant to power supply blipping or EMI signal injection may sound strong, but isn't if the computer it's running on has a root kit installed.

Therefore in summary, I offer: source strength $ \propto $ source stability.

Tom avatar
tf flag
Tom
I found name "weak" here: https://en.wikipedia.org/wiki/Randomness_extractor. And here: https://arxiv.org/abs/1402.4797. And here: https://www.cs.utexas.edu/~diz/Sub%20Websites/Research/Computing_with_very_weak_random_sources.pdf, ad vocem leftover hash lemma. And here: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.29.1715&rep=rep1&type=pdf. There is much about "weak" sources in literature about randomness extractors. But maybe they usually mean just low entropy, not some weakness in physical sources (except Wikipedia, they for sure named concrete physical sources "weak").
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.