Truly Random Numbers at Scale - Overloaded memory chips generate truly random numbers for encryption

Question

For years, truly random numbers at scale has been elusive. Thus I read this recent research https://www.newscientist.com/article/2303984-overloaded-memory-chips-generate-truly-random-numbers-for-encryption/ and https://cacm.acm.org/news/257835-overloaded-memory-chips-generate-truly-random-numbers-for-encryption with great intrigue, anticipation and excitement.

My first question: What are the difficulties associated with generating true random numbers? Cost, practicalities such as power consumption?

Second question: What and who can be an arbiter on true randomness? i.e., who decides this particular number is truly randomly generated?

Answer 1

For years, truly random numbers at scale has been elusive.

No, this is 100% hype. Generating random numbers is easy. There are plenty of known techniques to do it. “Scale” is not a problem with respect to the quantity of random numbers, because “true” randomness is only needed so seed a cryptographically secure pseudorandom generator (CSPRNG). The output of a CSPRNG is indistinguishable from true random.

My first question: What are the difficulties associated with generating true random numbers? Cost, practicalities such as power consumption?

One difficulty with random generation is that it requires dedicated hardware which costs a significant fraction of a cent to mass-produce. This is a concern for devices whose price is of the order of magnitude of a cent per unit. This difficulty is largely solved nowadays: price have come down compared to a decade or so ago, and many cheap microcontrollers include a TRNG.

Incidentally, generating random numbers through processor and memory jitter is a well-known technique which cannot be employed in very cheap devices because they're too slow and stable. And it's not a very useful technique on larger devices because for those the incremental cost of a dedicated TRNG is negligible. All modern PC and smartphone processors include a dedicated TRNG, for example.

Power consumption is not much of an issue since the TRNG only needs to run for a very short amount of time. Latency can be an issue when the processor boots.

As a designer of embedded systems who doesn't know much about how the hardware works (my work is firmly at the software and system levels), the improvements I'd like to see in hardware random generation are to be cheaper to mass-produce (so that they're in every device), to have less latency and to be more reliable to environmental perturbations (e.g. temperature and power variations).

But in practice, the biggest problem with random generation is not in the hardware. It's in the software ecosystem which has trouble bridging all the steps between the hardware design and the application design. The problem is the operating systems and programming language interfaces where getting insecure random numbers is easy but getting secure random numbers is hard. The problem is misconfigured systems and applications that pass functional tests but have not had a proper security review.

Second question: What and who can be an arbiter on true randomness? i.e., who decides this particular number is truly randomly generated?

Since you can't tell how random a number is by looking at the number, you have to look at the process by which the number is generated.

Answer 2

1. The main difficulty is to find a good source of entropy. It is a measure of "randomness". Well, if we have a value $seed$ such that $H(seed)=n$, we cannot produce a sequence $x, |x|\geq|seed|$ with greater entropy, i.e. $\forall x : x=f(seed)\land|x|\geq|seed|\implies H(x)\leq H(seed)$, where $f$ is some deterministic algorithm (PRNG). Entropy is defined as follows: $$ H(X)=-\sum_{x\ \in\ \text{Dom}(X)}\text{Pr}(x)\cdot\text{log}_2\text{Pr}(x) $$ where $X$ is a random variable. <removed>
   In other words in the best case we get a longer sequence with the same amount of "randomness" in it as in the shortest one. There's no way to generate a potentially unbounded truly random sequence using some algorithm from a finite sequence without any additional entropy source.
   UPD: it's not quite correct to use the formula for sequences. But the sense of this paragraph remains valid: you cannot create "randomness" from nothing.

2. Well, that's a good question, because we can say, that whether some sequence is random or not with a certain probability. The only way is to use statistical tests. An ideal (or truly) random sequence is defined as follows: $$ X_\to=\{\zeta_1, \zeta_2, ..., \zeta_n,...\} $$ where $\zeta_i, i\in\{1,2,...\}$ are uniformly distributed on some set $X$ random variables and in each subset $\{\zeta_{i_1},...,\zeta_{i_k}\}$ all variables are independent. Having an arbitrary sequence the only we can do is to test its statistical properties and to say that with a high (or low) probability these requirements hold for these variables <redacted to make it more clear>.
   <removed>
   In all articles I've read about truly random generators are tested statistically. Unfortunately I can't read article, that you mentioned in the question, but I think, that there will be the same sort of research.

---

Well, I suppose, that there could be a potential method to prove, that some generator produces a sequence with the maximum possible entropy, but I haven't seen it yet. But maybe it's impossible to have such method. If there's one, I'm interested to read about it :)

UPD: maximum entropy isn't required for true randomness. Here is some citations of @Paul Uszak:

Such a sequence [truly random] only needs a monotonically increasing amount of Kolmogorov complexity. Bias/correlation is irrelevant.

TRNGs aren’t tested for true randomness. Their ‘truth’ comes from an understanding of the non deterministic physical processes that create the output Kolmogorov complexity.

UPD: in a nutshell: TRNGs use some physical unpredictable events to yield a sequence, PRNGs use computer algorithms.

Answer 3

What are the difficulties associated with generating true random numbers?

There are no tangible difficulties with generating shed loads of true random numbers. The Haveged daemon claims to generate megabits/s of true entropy without any external hardware. I’m not sure what ‘at scale’ realistically means though. Cycling an AES key per every minute is a Kolmogorov rate of <3 bits/s. With respect, that’s child’s play even for DIYers. Look at those night time party pics on your smartphone and wonder what all that image noise is. If you have ~3000 Euros you can buy a 240 Mbps TRNG that uses beam splitting technology. If your life depended on it, is $2600 too much? And the yeolde /dev/random would do >30 kB/hr just checking email. Double that if you're researching PornHub.

The most likely intangible reason I mustn’t go into is reflected in the following; Athletes are being advised to use burner phones in Beijing.

What and who can be an arbiter on true randomness?

Only you.

There’s a very famous web site strap line that says ”Secure entropy? Your entropy.” The concept of computational indistinguishability means that the output of the Mersenne Twister looks pretty much like the output of /dev/random. This is the take away from here.

The Intel on-chip hardware random number generator looks random but nobody in the *nix community trusts it. And so they shouldn’t given the publicly confirmed NOBUS2 policy. And unfortunately for you/us it’s impossible to reverse engineer a multilayer silicon die with billions of transistors.

This part of my answer could go on for thousands of mouse downs, so I’ll end with trying to persuade you to build an entropy source yourself with a little diode (£2.08 + VAT/20).

---

2 Get a tin hat. The really thick Christmas turkey type. The NOBUS entry has been deleted from Wikipedia. Draw your own conclusions. So I direct you to the WAPO article with the head of the CIA/NSA (same guy).