Schneier on Security

Clive Robinson • November 5, 2022 7:39 PM

@ iAPX,

Re : When random might be…

“This is NOT bulletproof, but this make it really complex and incredibly resource-consuming to find the pseudo-random generators internal status, and thus to be able to predict the nexts outputs.”

The problem with RNG’s is,

“What happens at Boot time?”

It’s all very well having a well stired entropy pool, after a large uptime, but the NSA did rather well on breaking PKcert Keys on embedded devices…

Basically way way to many embedded network devices, especially low cost IoT devices, start up with a known entropy pool, and do not update it before they generate the PKcert for it… Thus the reality is maybe 50-100 actual primes go into the certs, thus a fast search to factor is very cheap…

I’ve been developing RNG’s since the late 1970’s, and even now into five decades later I’m still shocked at just how little people developing such ICTsec products know…

It’s not as though it’s a barely discussed subject, our host @Bruce has written not just essays but effectively a book on the subject…

Do you remember Linus Torvalds and his now infamous comment about just using the Intel OnChip Hardware RNG?

I’m glad he realized –with a little prompting– why that was not a good idea…

Anyway, enough reminising from me today…

In the UK Nov 5th is known as “bonfire night” or “Guy Forks Night” when loud fireworks are for some people a must… I however suffer from tinitus due to the use of a 7.62mm rifle amoungst other weapons in a regimental shooting team. Needless to say I’m glad about the legal impediment / prohibition to the use after midnight of fireworks, as they make my ears ring like I’ve had my head stuffed in a church bell… Which makes thinking or sleeping a challenge at best. How peoples pet cats and dogs do not go mad I realy don’t know.

Clive Robinson • November 7, 2022 7:45 PM

@ keiner,

“Any ideas why there should be a maximum entropy hardcoded in the linux kernel”

It’s not “hardcoded” in the kernel. That limit is due to the size of the hash used (Blake) being reported. With a hash you can not get anymore output from it than you put in.

That said if you want to play “silly numbers games” there is nothing to stop you taking multiple draws via the hash algorithm. So get an increased level of what you might think of as “entropy” but the reality is it’s just a form of complexity gained via a “One Way Function”(OWF) that might or might not be “Cryptographicaly Secure”(CS).

It’s a matter of open debate as to if OWFs actually exist, as for CS-OWFs well lets just say history has a habit of showing anything claimed by some proof as being “CS” frequently turns out not to be in a quater of a century or less.

But look at things realistically just how much “True Entropy” do you think a Linux box actially gets over say 24hours?

You might be shocked to find out just how little it realy is.

So the question to ask is not about “entropy” but about how determanistic and guessable it is both in the mechanical and mathmatical senses.

What you are mostly looking for is,

“A ball drawn from a stirred urn”

Where the number of balls is many trillions of trillions times the number of atoms in the universe. With each ball having the same odds of being drawn.

Where that is “insufficient” then you look at drawing more balls, for which you need a further constraint which is an awkward one of,

“Each ball drawn is fully independent of those drawn before or to be drawn in the future”

We can not do this with a hash and entropy pool driven by a low ammount of “True Entropy”. But mostly it does not matter as long as an attacker can not get at the sequence state, the numbers remain unguessable so appear to have “True Entropy”.

People get the wrong idea about entropy pools followed by crypto algorithms. They do not in any way create “True entropy” as many think. All they do is, the pool smears or spreads the tiny amount of True Entropy across all the bits in the pool in a way that is unpredictable and the “state” of the pool at any one time remains hidden by the strength of the crypto algorithm.

I call the use of such crypto algorithms “Magic Pixie Dust Thinking” for a whole heap of valid reasons.

Clive Robinson • November 8, 2022 6:02 AM

@ keiner,

Re : is the entropy strong enough.

“let’s say, a 2048 bit openvpn key or a wireguard key generated on a system up for 1 week?”

The “true entropy” is very probably insufficient, but that probably does not matter…

To see why you have to take a sideways view at things as a black-box process where there are two players,

1, The generator.
2, The observer.

The generator can see both the inputs to and the outputs from the black box. The observer can only see the output. The idea of the black box is two fold,

1, To prevent the observer seeing either the black box state or black box inputs.
2, To prevent the generator from being able to correlate inputs to outputs.

It’s the correlation argument which gives rise to the need for “One Way Function”(OWF) crypto algorithms.

So as a very rough rule of thumb you can say the output from the black box the observer sees is atleast as strong as the crypto used.

That is consider it equivalent to say AES256 in CTR mode. When he the observer does not know either the AES key, or the Counter or state value.

The big problem is the generator will know both the starting values of the key and the count, as well as see the inputs to the black box. So can as easily “play along” with a simulation of the black box. Now consider Eve, who knows when the system was started, and can also see the external network inputs to the system the black box is usesd on. She is in effect closer to being the generator than the observer… Which means that it is possible for her to run a search to work out the blackbox internal state close enough to have a much reduced range of blackbox output thus get a much higher degree of predictability. This is an attack senario that works with “embedded systems” where in effect the only source of entropy is visable to Eve network events. Worse provided Eve gets to see blackbox output frequently she effectively has a heartbeat so she can assume blackbox input and track the probable state within a small but searchable range.

So a lot does depend on the effectiveness of “stiring the pool” from the inputs to the blackbox.

So what is the input to the blackbox? Well it’s in part mechanical –from system clock crystall– and part determanistic from the actions of algorithms but it is also in part chaotic due to the way those algorithms can interact (think of the system as being equivalent to a multiple jointed pendulum).

Or to look at it in a more analytical way, assume a spectrum line or plane edge going from determanistic at one end to truely random at the other.

The scale goes from simple determanistic through various grades of complex, likewise into chaotic and then into various grades of random.

Whilst you can view it as a spectrum line for mathmatical / informational objects it is better to view it as a plane for mechanical / physical objects.

That is in every physical object that does work there is inefficiency that by various transducer effects steps down to some form of noise, eventually heat. Some small part of that noise is truely unpredictable for various reasons to do with the physics of measurment and it’s hete that true unpredictability resides.

So there are three questions that arise from this observation,

1, What % is truely unpredictable?
2, How much contamination that is predictable can be removed?
3, Does such contamination actually matter?

Supprisingly to many the answers to the questions are,

1, Almost to small to measure.
2, Not a great deal.
3, Not that much if corelation synchronization can be avoided.

The important point to note is “synchronization”. For a future value to be predictable to an observer they have to be synchronized to past events by past values from the blackbox.

I’ll stop at this point for now, because in the past the subject of synchronization and the resulting search attacks got quite involved.

The simplest advice at this point is,

1, Have lots of blackbox input.
2, Issolate the system with the blackbox on it as much as possible from any observer.

Clive Robinson • November 9, 2022 5:46 AM

@ SpaceLifeForm, keiner

Re : Roll your own random.

“A CPU with a kernel that is Bicycling in it’s idle loop, is not going to generate any entropy because there are no events, no interrupts. It is just wasting energy. You can not trust any CPU to give you good Random.”

As I noted above all “physical events” have some small sometimes exceptionaly small measure of “True Random” attached to them. This includes all physical objects “doing work” even if it’s just a CPU in the OS idle loop work thus inefficiency come into play.

However determanistic mathmatical / informational events do not “do work” in the physical sense, so do not genetate even small amounts of “True Random” but they can do both complexity and chaotic.

The problem is when trying to define things is that mathmatical / informational events do not exist in issolation in a CPU as they cause physical events thus work to be done…

A CPU by it’s self has two sources of True Random you can identify by inspection and test. The first is the “mechanical resonator” that is the quartz crystal of the “XTAL” that drives the CPU “clock cycle”. The second is the indeterminacy of the threshold used in logic gates and the soft errors arising in various ways, it’s called “meta-stability”.

The effects of meta-stability in logic gates can be increased, which is where “On Chip TRNG’s” come from usually via two or more “Ring oscillators”

The history behind on chip TRNG’s is such that it has more “rabbit holes” than all the warens in “Watership Down”.

One of the particular on chip rabbit holes I’ve always cautioned about is “Magic Pixie Dust Thinking” of using crypto algorithms to hide just how small the true random is. Intel pioneered this “hide the junk” behaviour back when they were using “thermal noise” (4KTBR) from an on chip resistor as their random source… So I’ve cautioned against Intel from almost day one and continue to do so.

It would appear from this fairly recent (2019) paper I was wise to do so,

https://eprint.iacr.org/2019/198.pdf

But as I’ve also indicated the topic is as twisty and more complex than all those rabbit holes especially on the engineering side of things.

After more than four decades of being involved with the design of RNGs often at the sharp end, the one thing I realy do know with certainty, is that I know a lot less about the subject than I would like to know, and in this I am far from alone, hence we see occasional papers pop up on the subject of Hardware RNGs.

On some of my more thoughtful days I consider that “random is a gift” from the intangible information universe, down to the tangible physical universe in which we corporeal beings are condemned to live. That is it could simply be the issue of transitioning information from a continuous universe to a discrete universe that will be for ever more fundementally granular.

Clive Robinson • November 11, 2022 2:53 AM

@ ALL,

Re : Is DIY random generation garbage?

Short answer “Yes and No”.

As @SpaceLifeForm has pointed out “crypto” is an overloaded word…

But nowhere as badly as “random”.

So you have to ask the question,

“What am I trying to achieve?”

Then and only when you actually understand the full implications can you make the good/bad decision.

For instance is a close in photo of a spilled out “box of matches” random?

Both No and Yes.

Is it an “unguessable bag of bits” well that depends… on how you extract the bits, and how you “post process” them.

Take the photo turn it to black and white and a simple uncompressed format and crop out the “matches” from the plain back ground then pull out the bits. You are likely to get between 1/4 and 3/4 of the bits ones and only have predictability in higher order patterns.

Take two entirely unrelated match pile photos and run them sequentially through a suitable cryptographic algorithm (CS-Hash) and the chances are good you will have a “bag of bits” suitable to use as an AES key, but not for an RSA cert prime search.

Knowing why the above is correct will get you one edge on the good/bad problem understanding. But… could also lead you down a rabbit hole, right into the mouth of a ferret[1]…

Good sources of “True Randomness” are actually quite hard to find, and are “physical” devices. With even the best of them all have bias, and predictability in their outputs that needs to be dealt with[3]. And as they say,

“That’s not the half of it by a long way”.

[1] Ferret is a term once used by Allied WWII PoW’s in the likes of Colditz[2] for the German “intelligence operatives” used amoungst other things to stop escape attempts by finding tunnels and escape equipment. It is less than humorously derived from two things. Firstly the expression “To ferret out” bassed on the thoroughness actuall ferrets search for rabbits in warrens, secondly the unmerciful way ferrets drag baby rabbits out into the light, and then kill them (nature in all it’s violent tooth and claw).

[2] I actually knew a Colditz PoW who was “my boss” for a year or so. He cycled all across Europe in “cricket whites” and was turned in by a Quisling whilst trying to find a boat to get him across the North Sea. One of his little quirks was that he had kept many of the “Condemed to Death” notices he had been given and had them framed on his office walls. He spoke supprisingly warmly about the regular millitary personnel of the PoW camps he had been in, his view being most were just doing a guarding job without any malice. His view on others such as the non military but uniformed which included those who directed the ferrets was not as forgiving.

[3] The oft quoted source of “True Randomness” is a radioactive source, but that is a bit of a limited point of view. Whilst it is true we have no way of predicting how individual radioactive atoms will decay, we do know that for any given type of atom in bulk they have a “half life” that is good to many decimal places. The half life curve is a simple 1/n curve where n decreses at a rate of qc/S where “q” is the quantity of atoms, “c” is a constant for the atom and S is a second. That is if you have a thoisand atoms each decay takes the number down so the number of decays left likewise goes down. If q or c is large then the number of decays per second is quite predictable and goes down almost linearly over short periods of time (see Newton’s infitesimals as to why that is). This is both an advantage and a disadvantage depending on how and what you measure. But the measurment process via a GM tube or similar generates electrical noise, that appears on both signal and supply lines, and without care gets out of the generator via many inadvertant side channels. Worse the decreasing count pulses when integrated / low pass filtered provide a decreasing bias voltage in the analog circuitry which too can without care effect the generator output. But other gotchers that exist “down the chain” are the likes of “de-biasers”. If you take two output bits from a generator and XOR them you get a von Newman de-bias circuit. Whilst it will remove “value bias” and give equal zero/one probilities it does not remove “time bias” and infact makes it worse. Likewise the circuit produces pulses of current thus electrical noise. Both the time and noise will appear at the output if care is not taken, and they noise pulses especially can be synchronous down the chain.