Schneier on Security

Clive Robinson • March 24, 2022 10:44 AM

@ Alex,

Is there a reason modern computer systems don’t come with built in hardware RNGs? Is there any reason HNGs couldn’t be put on the mainboard, or even in the CPU itself?

The short answers are,

1, Most modern computers even $10 SBC’s come with what are claimed to be RNG’s in hardware.

2, The majority of these hardware so called RNG’s are in the CPU chips.

A wise man would treat these so called RNG’s with a great deal od skepticism. Especially as most chip makers make it impossible to verify the RNG’s by hiding them behind various forms of crypto “magic pixie dust”.

The point being you can only be an observer to the output of the crypto algorithm. If the algorithm is any good, then it is impossible in human terms to determin from just observing the output, if the input to the ctypto algorithm is actually,

1, Truely Random
2, Chaotic
3, Of high Complexity
4, Pseudo Random
5, Purely Determanistic

Only the first on the list is of use as the “Root of Trust” in any security system, the last is actually desirable for running Monte Carlo type simulations in engineering where as the first would not be.

The first is actually so rare that it is at best a very very tiny fraction in any hardware circuit that claims to be an RNG. Even the bulk of “True Random Number Generator”(TRNG) sources when they are analysed show most of their output is from the second and third groups[1] often with a lot of the fifth thrown into the mix.

The fifth can be as simple as a counter incrementing by one each time. With the crypto algorithm turning it into a “stream generator”. Which is effctively what AES in Counter Mode is. All you need to break it is the “secret key” which might be secret to the observer, but not the designer of the hardware or anyone they might have told.

So… If you follow the logic you will realise that,

“If you can not see the raw source output directly you would be a fool to rely solely on on CPU chip RNGs for any kind of security application.”

Especially when the “raw sources” are at best extreamly “fragile” and highly susceptable to “influence”.

I could go on, but whilst it is often fine to use those CPU RNG’s as a “jiggler” in various ways to spread any real entropy you have across as many bits as you can. Security wise you still need that true entropy source being the “Master” secret otherwise “no secrecy == no security, just obscurity”.

[1] The old “flip the coin” process has been repeatedly shown to be highly linked to it’s input conditions and is thus at best “chaotic”. Even those “draw the ball” machines are very determanistic in nature, and their output is almost certainly a mix of narrow range chaotic behaviour and high complexity in the orbit arcs.

Clive Robinson • March 25, 2022 11:24 AM

@ fib, Alex, ALL,

One day there’s going to be a radioactive TRNG on a chip

There already are radioactive sources mounted on chips, as low power “power supplies” so the technology is already available.

But you can buy very very cheaply a radioactive source and detector all mounted up and ready to “play with”[1] at your local hardware store or similar. That is the detectors in smoke alarms are radioactive and can be used to make TRNG’s but just don’t do it.

Other sources that are now considered sufficiently hazardous to humans are pre-WWII green glaze potery like “Fiestaware collectables” certain uranium salts based glass, oh and do not forget all those “see in the dark” early paints used on instruments in aircraft cockpits and on wrist watches issued to military personnel etc back then.

As has recently been demonstrated even kicking dirt about can be detected hundreds and thousands of miles away (Chernobyl site).

And that lovely granite worktop or slate tile back you want in your kitchen… Yup they will make a Geiger Counter click like the meter in a taxi being used as a getaway vehicle…

Remember the NRPB has not indicated a “safe lower limit” so…

[1] Though I realy would suggest you don’t play with any radio isotope source (and that includes bananas[2]). Whilst we normaly think alpha emitters are “harmless” they are very much not. The reason we incorrectly assume they are safe is the alpha particles will not go through the layer of dead skincells you have… However if you ingest an alpha emitter, and you do it gets past the gut barrier, then your future will not look good, nor will you as the radiation.poisoning destroys you at the DNA and lower levels… So “smoke detectors are not toys” and should be treated with real caution… Oh and some radio isotopes are realy very very poisonous in their own right… Look up plutonium it’s about as poisonous as a metalic element as you can get[2].

[2] Whilst radio isotopes turn up in all sorts of odd places like bananas, and exhaled breath (potasium and cardon isotopes respectively)

https://www.mcgill.ca/oss/article/you-asked/it-true-banana-radioactive

It’s not the radiation that should be of a worry but the poisoning effects… Potasium Chloride is the leathal component in the leathal injection and well, I think most know about the letality of both carbon monoxide and carbon dioxide.

There are similar issues with other radioisotopes the man made element Plutonium is just about as bad as it gets as far as being a poisonous metal. How it gets into body cells has for quite some time been a bit of a mystery. However,

https://blogs.scientificamerican.com/observations/fukushima-absorbed-how-plutonium-poisons-the-body/

Clive Robinson • March 25, 2022 5:48 PM

@ David Leppik, lurker, Quantry, All,

I’m not saying “entropy” because it has a different meaning in physics, which in this case could be misleading.

Yup, the actual term is “meta-stability” and it’s a whole diferent bag of snakes. I’ve talked about it and the issues with “Ring Oscilators” of CMOS inverters[1], “injection locking” from any kind of noise, and the unfortunate “mixing effect” of D-Type latches etc.

A week or so back I posted refrences to quite detailed technical knowledge. If people are interested I can dig it out again.

[1] Contrary to what many think, logic gates like CMOS inverters are not “digital” they are actually very high gain analog amplifiers with poorly defind transition (just like Op-Amps). You can turn such inverters into analog amplifiers of more controled gain and transition with just a couple of resistors (just as you can with Op-Amps).

Clive Robinson • March 26, 2022 12:44 PM

@ Denton Scratch, David Leppick, ALL,

I don’t know how one could make the output from a free-running inverter loop predictable without interfering with the hardware,

It’s actually all to easy and depends on how you define “interfering with the hardware”.

As I indicated above a CMOS inverter is just a high gain analog amplifier. Which means it is highly sensitive to injected signals at it’s “cross over point”.

It’s fairly well known that a few centuries ago back in the 17th Century the Dutch mechanical inventor with a significant interest in pedulum clocks Christiaan Huygens discovered an intetesting phenom which he wrote about in a letter to the Royal Society in London in Feb 1665, it was perhaps unsurprisingly to do with pendulums as he was at the time trying to solve one of the greatest issues of the time “navigation at sea” (something he failed to do and fell to the English clock maker Harrison who was cheated by the English Government).

But the supprise Huygens wrote about appeared to be almost magic, in that if you placed two or more pendulums close to each other they have a habit of falling into synchronicity but of opposit phase.

Over three and a half centuries later the issues behind the synchronous behaviour is still not fully understood and it still throws up a few interesting bits of research,

https://physicsworld.com/a/the-secret-of-the-synchronized-pendulums/

Simplistically the pendulums and their driving mechanism are oscillators. Important to understand is that the driving mechanism that keeps the energy topped up in the “tuned circuit” the pendulum forms, has to be,

1, In phase with the oscillation
2, Provide only sufficient energy to make up for the losses.

If neither is true two effects can be observed,

1, The oscillation phase and frequency will change.
2, The chaotic process behind the oscillation will become dominant.

In the second case the oscillation phase and frequency become eratic, and can cause both pendulums to stop.

So there has to be an energy transfer from one pendulum to the other. This is a physical implementation of an Shanon Information Channel.

We know from thermodynamics that energy only moves in one direction “down hill” or from the dominant to the subordinate. But as we are dealing wirh “cyclic” behaviour what is dominant or not and when is somewhat difficult to figure out.

However as a first aproximation the oscillator that is not crossing zero when the other oscillator is can be viewed as dominant and energy will be transfered from the dominant oscillator slowing it, into the subordinate oscillator either speeding it or slowing it depending on the phase at the zero crossing.

The tiny movments of energy result in the oscilators always effecting each other.

But how tiny?

The answer appears to be “below the measurable noise floor” on any given measurment…

Now consider other oscillators, like tuning forks, it can be shown that if you have two very lightly coupled tuning forks, if you strike one the other will build up a measurable resonance…

The same is true for every other resonant circuit that has ever been studied in sufficient detail. Including biological processes in individuals like humans (found out by sanitation engineers where RMS figures were not the ones to use for the sizing of waste pipes in high density accomodation).

But the waveforms do not have to be sinusoidal but they do have to be cyclic. They also do not have to be at or near the tuned circuits resonant frequency, a harmonic or subharmonic will do. In fact the waveform can appear to the human eye to be totally random, as long as there is a net transfer of energy at some harmonic relationship. And as previously noted it can be very very small and effectively unmesurable to most test instruments…

So a ring oscillator of CMOS inverters, has very high susceptability to energy being coupled in at any and all the inverters as their inputs transition from one state to the other. And the phase thus frequency will be “pulled” in a fairly well known process called “injection locking” that is in most First World Homes as standard (analog Colour TV and Stereo Radio).

It is further guarenteed that there is more than sufficient energy from the surounding logic circuits for energy to get into the ring oscillator. Be it via direct electrical coupling in the power supply traces, capacitive and inductive coupling between traces, or by radiation from other oscilators be it mechanical/acoustic or Electro Magnetic.

So… That WiFi chip on the motherboard can in practice not just theory effect the CMOS inverter ring oscillators used in those supposadly “Truely Random” generators pulling them into synchronisation.

It has been demonstrated that a very expensive very carefully designed TRNG for high security applications, designed by IBM can have it’s output “randomness” pulled from over 2^32 to under 2^7 just by illuminating it with an RF CW signal in the microwave region sufficiently small in wavelength that it could get through ventilation grills and the joints between metal plates[1].

So we know without any doubt what so ever that without very significant precautions –which the chip makers do not take– that all those “On Chip” RNG’s using CMOS Inveryers in Ring Oscillators are most definately not “Truly Random”.

If you want to dig in further there are a couple of books that are reasonably aproachable by some one who has engineering degree level knowled on the subject of CMOS logic and their use in Ring Oscilators. Both are written by Prof Behzad Razavi,

1, Design of Analog CMOS Integrated Circuits

2, Design of CMOS Phase-Locked Loops

Oh and another of his books,

3, RF Microelectronics

Will help bring non RF engineers upto speed.

But as a last note, if you hear some muppet calling those who distrust thos On Chip RNG’s “tin foil hatters” or equivalent, you have my permission to send them off to a proctologist to have your boot surgically removed by “three sixty resection” or similar 😉

[1] I’ve talked about this before, if you want to know more about it look up “slot antennas”, but briefly if you have an antenna designed of wires in an insulated environment, you can replace the wires with slots in a conductive environment such as a metal plate.

Clive Robinson • March 28, 2022 1:44 PM

@ Quantry,

A perfect chore for gate logic, no?

Yes you can make a John von Neumann “debiaser” with at most three TTL chips. I was doing this back last century and have described it before on this blog and otherplaces. I was using a “roulette wheel” Entropy source[1] that made life easier interfacing wise.

You need a two stage shift register, the Q outputs of which drive the inputs of an XOR gate which you can make in various ways with four NAND gates. You might also need to latch the result for slow read out by a computer via a serial port.

IMPORTANTLY you need to clock two bits in each time… Then after testing discard both. Otherwise it will not debias correctly. How you do this is rather dependent on your entropy source circuit. But you can make a simple state machine with logic gates.

Importantly these days small micro controlers are more easily available and way less costly than even individual logic chips. They also enable you to provide a real Serial or Parallel data signal (RS232/Centronics) to a PC via direct port or USB port… Spend an extra 50 Cents and the Microcontroler will have all the USB 2.0 or higher hardware built in, and you can download most of the code you need to drive it from the Chip manufacturers “Tech Sup” web site.

Yes the John von neumann debiaser is ineficient… you get around one debiased bit for every four bits in from the alleged entropy source. You can up the efficiency by pipelining more bits and coming up with a more complex debias algorithm. Then send the bits by parallel reading rather than serial. But it only gets you more bits of “maybe” entropy, that is in reality they are “complex” or “chaotic” not “True Random” in origin.

The problem is whilst the bits are provably debiased[1], that does not mean you are getting real entropy. Because the circuit actually gives output on a pure sinewave or other cyclic waveform… So the debiased signal is not of necesity actually “entropy”…

[1] You can find the proof of debias in loads of places on the Internet, the easiest one to see intuitively is by the use of a square of the two probabilities… However coming up first on a quick search today is,

https://mathoverflow.net/questions/152107/proof-of-von-neumanns-debiasing-algorithm

[2] A roulette wheel or waggon wheel entropy source uses two oscillators one mostly stable, the other definitly not. You use the stable oscillator to “strobe”, “clock” or “sample” the unstable oscillator, which mathmatically is a simple sampling process. If you’ve ever seen an old cowboy movie where the waggon wheels appear to go backwards slowly, what you are seeing is the strob effect caused by the movie cameras shutter, likewise if your dad or school “motor shop” showed you how to adjust the timing on an internal combustion engine with a strobe light.

Whilst designing a stable enough oscillator is easy, you just buy a TTL Xtal Osc package for a dollar or what ever the rapidly rising price is these days… Designing a suitable unstable oscillator is actually nowhere near as easy… My solution back last century was to use an OpAmp as a VCO by moving it’s bias point with an amplified, semiconductor noise source. It sounds easy, but due to the nature of sampling and injection locking, it can take quite a few goes to get it right (those software CAD systems usually let you down so you have to build a number of actual prototypes and know how to test them properly…).

Clive Robinson • March 29, 2022 8:07 AM

@ Denton Scratch,

Correct me if I’m wrong, but I think if you apply the VN debiaser to a perfectly random input stream, you get one bit of “debiased” output for every twwo bits of unbiased input, no?

Err no, “perfectly random” is not in anyway an implication that it is dibiased in “any given period”.

Have a careful think about that… That is “random” is not equivalent to “debiased” it just “tends towards being true” when you start averaging things out for long enough.

To see why look at the John von Neumann circuit a bit more closely. It has two bits at it’s input from the entropy source that in a perfect world would be fully independent (but are not in the real world). The circuit had One output bit –call it valid– which says “the two input bits are different” the other two output bits are the input bits, that are indicated as “valid” thus debiased, call them Q0 and Q1. However they are also the inverse of each other when valid. So you can use either of them as the “Data Out” bit just as long as you always use the same one.

So yoy have two input bits for each test they and they form the following set,

{00,01,10,11}

Of which only the subset {01,10} give valid output bits. So eight input bits give you two valid output bits on a long enough average.

On to,

But if the input is heavily biased to zeroes, you’ll need much more than 4 bits of input for each bit of debiased output.

But remember “Each member” of the test set can be “randomly selected” for any test. So it’s posible to get,

[01,11,10], [11,11,00], [00,11,11],
[10,00,01], [00,00,11], [11,00,00],

Which are clearly biased as triples, but can and will result from random selection at some point and will continue to do so with some small probability.

But you can also see, that for those 36 input bits you would only get 4 output bits or ‘1 for 9’ even though in total you have 18 ones and 18 zeros so the input over 36 bits is not actually biased…

But onwards, you say,

That is, the output bitrate of the VN debiaser is variable, and depends on the amount of bias in the input.

True and true, but it says nothing about how random it is or is not.

So for further fun… How about inputs of,

[01,01,01,01,01,01] or,
[10,10,10,10,10,10]

Both can be seen to be NOT random but cyclic but as they are as far as the circuit is concerned “debiased” thus valid, you get [000000] and [111111] output respectively at a rate of two bits in for one valid bit out… But as can be seen over the length considered most would say “not” random.

Which tells you a couple of things.

Firstly you need to count the number of “raw bits” out of your entropy “source” and the number of bits out of the debias circuit and keep an eye on their relative values.

Secondly and importantly over various lengths of time as well as raw bit rate…

It’s one of the reasons why I say you MUST have access to the raw physical source output to see if the source is possibly working or in some limited cases “definately not working” or probably not working as well as you would like for some reason (ie it could be going faulty or it is subject to some kind of influance).

I hope that helps spur your thinking onwards, to what other tests you might want to consider.