What is the Intel Random Number Generator silent about?

I have long wanted to kick the RNG from Intel, but I couldn’t find a free minute. I had to force myself. The result of kicking is the text below.
The format of the text is banter and criticism, with respect to the opponent.
I do not think that the post will be interesting to the developers of this RNG (they have already received a prize for it), but for someone else, for general development, it will probably be interesting.

What is the RNG silent about from Intel? And he is silent about a lot of things, but first you need to determine the terminology.
There is a common name for the Random Number Generator (RNG). They are divided into PRNG (Pseudo Random Number Generator) and TRNG - True RNG. Each self-respecting office that issues crypto IP, is well obliged to have True RNG in its arsenal.
Even better, if your True RNG is compact, fast and most importantly - digital (well, without analog troubles, such as Schottky diodes, noisy resistors, etc. of exotic animals, because it is difficult to "maintain" it).
In a word, there is no way without True RNG, since the real entropy in cryptography is also necessary.

If anyone was interested in True RNG, you should be aware of the material where the first Intel RNG was first described .
They use a “noise resistor” in combination with a pair of oscillators there as a source of entropy. This is the first True RNG from Intel and until recently (before the release of Ivy Bridge products) was the only one. In principle, the first Intel True RNG worked correctly (although it was not smart), but he was allergic to portability (between production technologies) (personal assumption), required special nutrition, etc. restrictions. Therefore, it was "kept" in the back of the chipset, which, for various reasons, lagged behind (by production technology) from processors by a year or two.
Intel decided to stop this masochism, and in 2008 gave the task to two development groups to make a new True RNG. To be digital, yes fast, and so that I wouldn’t eat valuable energy in vain, but I passed different certifications.

In the course of development, there were 2 publications on this subject, and I just have to dwell on them in detail. Unfortunately, they are not in the public domain (only IEEE), but the seeker will always find.
First, “A 4Gbps 0.57pJ / bit Process-Voltage-Temperature Variation Tolerant All-Digital True Random Number Generator in 45nm CMOS”
From the title and abstract to the material, it immediately became clear that Intel doesn’t like to joke, and “tear everyone”, without even asking for a last name. But when I read to the end, I laughed for a long time. Laughing Highlights:
  • We have all tested with the NIST STS test suite, and our RNG passes all the tests.
In fact, Intel researchers used only 5 out of 16 tests (there are 15 of them in the new version of the package (the tests themselves and the documentation are open here ). In addition, one test was used incorrectly, since Discrete Fourier Transform needs significantly more data for analysis than the proposed 500 bits, but researchers can be forgiven, because the received 4Gb / s performance, like all the data in the article, is just a simulation.
Well, okay, the first test is always a simulation, and you can agree with these, but not at all will agree that
  • The source of entropy, according to the developers, is completely digital.

In principle, the central element of the source of entropy is a bistable cell, which is essentially digital image, but the way it was processed with a file already goes beyond the definition of all-digital.
Here is an example of a used inverter (total 2), which has 8 specially selected taps for power and ground.
image
Turning them on / off, you can adjust the inverter switching level (in a real chip, the transistors will be all different). The goal of the developers was simple - to achieve the same level of switching a pair of used inverters in a bistable element; they probably reached their goals (compensated for the technological spread), but to call this ancient solution (older than me) - all-digital - it's just blasphemy, imho.
In addition to the “special-digital inverters”, which are clearly not available in the standard digital library for design, Intel researchers added another all-digital solution to compensate for the parasitic capacitance of the connecting connections (delay element), which works on the same principle of tuning / compensation. As a result, we got such and such “all-digital”
image
where CONF0-1 is 8-bit registers for adjusting the switching levels of inverters, and CONF2-3 are 4-bit registers for compensating for stray capacitance of trunk lines (delay settings). In general, CONF0-3 is used to balance the system, because without it - how lucky (the chip will differ from the chip): either it will not work if the noise is less than the difference between the inverters switching, or it will work but badly - the distribution of zeros and ones will not be uniform , although possible and working options (all according to Gauss).
There is still much to complain about (how they simulated technological variation, evaluated the results of passing statistical tests, about a "low-energy" solution, etc.), but it’s better to go to the second publication.

Second"2.4GHz 7mW All-Digital PVT-Variation Tolerant True Random Number Generator in 45nm CMOS" , for all the main points, repeats the first, even adds some "controversial points of assessment", and only moderated appetite in performance - from 4Gb / s to 2.4Gb /with
  • the same inferior set of statistical tests, the source of entropy, etc.
  • self-calibration mechanism has been added, which should be considered in more detail;

image

The self-calibration system operates as follows: the system checks the generated bit and, depending on its value, rebuilds the source of entropy in order to receive an inverse value the next time. For example, if the current (generated) value is '0', then the source of entropy (using a new combination of loads on the parts of the inverters and connecting lines) will be “nudged” in the opposite direction to generate '1' with a higher probability.
Yes, the above example is quite simplified, because, according to the developers, the self-calibration system evaluates 1, 2 and 4 consecutive bits when making a decision (details are not given). In total, I can agree that this solution will allow achieving Uniformity (a uniform distribution of values ​​of type '1' and '0') at the output, but what about Unpredictability and Independence? But even Mr. Jesse Walker mentioned such important parameters as Unpredictability and Independence for Random Number Generators.
Another reasonable question arises on tests - how long and how many samples are tested?
As a result, there is a table with 5 tests (Frequency, Block Frequency, Runs, Cumulative Sums and FFT), although there are 15 in the package. If in the first article they received data from an analog simulation, then in the second, they clearly announce that RNG is implemented hardware (fabricated), and from this it follows that there should not be reasonable reasons for an inferior check (in the sense - it is difficult to generate).
On this science-like campaign ended and almost only advertising remained.
At IDF 2011, the RNG in Ivy Bridge was casually announced, but in more detail only in the IEEE Spectrum publication on this topic.
The translation of this article for a long time on Habré here, where in the comments we thoroughly went over the double whitening using AES of these very “almost random” data from the source of entropy.

image

The same picture (only more details) and at IDF 2012.
I would like to note in this article the phrase "It starts by collecting the mostly random output of the two inverters 512 bits at a time .". I couldn’t unambiguously present the implementation of this solution. Anyway.

What was it all about?
In any case, the Intel developers have done well, were able to release such a "digital solution" on 22nm technology and it is very cool.

PS If the presentation of the material seemed to be confused for some people or questions arose, I will gladly clarify or answer.

PS 2. thanks for the edits

Also popular now: