Schneier on Security

Clive Robinson • September 9, 2013 8:28 AM

@ ATN,

… is there a way to recover the private key from the public key if you have the last month worth of random data generated by the PC?

Your question is lacking in what you mean by random data.

However the answer to “is there a way to recover the private key from the public key” is yes in theory but currently impracticle in practice. What we do know is there is no proof that it can not be done extreamly quickly, just that nobody has published either a proof or a method, so the game is open either way currently (as far as we know publicaly).

What we also know with keys using PQ primes as the base, is if you know one you know the other, and that there are very fast tests that show if a public key shares a prime with another public key. So if your pubkey is tested against all the other pub keys on the internet it can quickly be found if your key has a prime in common. This would not realy matter if we had good random number generators but invariably we don’t thus with embedded systems that generate pubkeys on first start up the amount of entropy is often less than desired by a very large margin. Tests have shown that there are a lot of pubkeys out there that do share common primes so much so that it defies probability of it happening unless the random generator is crocked. Further investigation has indicated that the source of these improbable pubkeys tends to be common to the same software used…

Whilst pubkeys with common primes is bad enough on it’s own it raises another issue which is “limited search space”. For the same prime to be selected by two different bits of kit the probability of it happening is related to the range of random numbers produced. The smaller the range the greater the probability of it occuring, thus the greater the odds of tailoring a simple search to match other pubkeys.

It’s an odds on bet that the NSA know of every weak random number generator there is in commercial equipment and have charecterised their limitations and in some cases built systems to exploit this.

Worse is the fact that the systems most likely to have crocked random number generators are those that are embedded devices such as network devices such as firewalls, switches and routers, which is exactly the sort of gear the NSA are beleived to target…

But there is another issue which is kleptography [1] which is especialy bad in generating public keys due to the very high level of redundancy possible. Basicaly you can write a program to generate public keys that using a hidden public key in the software of about a third of the length of the public key being generated, can hide the starting point of the search for the first prime used in the users generated public key. The problem is even if the software prints out the two primes and the generated public and private keys, there is no way the user can analyse them to find the use of the hidden public key. However as the software writer you (may) have access to the private key coresponding to the hidden public key and you can use this to decipher the search start point, you then feed this into the rest of your prime search algorithm and out pops the first of the primes used to generate the public key pair in a matter of a few seconds or minutes, you then use this to find the second prime from the users public key and thus have their private key…

[1] The idea originated from Adam Young and his academic supervisor Moti Yung, http://www.en.wikipedia.org/wiki/Kleptography

Clive Robinson • September 9, 2013 6:49 PM

@ Randell Jesup,

Yup many RNGs were quite bad (and many still are). I’ve been designing TRNGs and CS-PRNGs off and on for over a third of a century mainly on the hardware side using individual components for the noise sources and limited functionality IC’s (analog OP-Amps and 74xx TTL chips) to provide a sufficiently usable source for a micro controler to do the software bits.

I’ve learnt a lot in that time, mainly just how badly other people do it and how they don’t take the time to lift real entropy out of the faux entropy…

But it’s somewhat surprising to reflect that most programers don’t know even today the advantages and disadvantages of various RNGs and which one is most appropriate for their application and why, even some quite famous programers…

@ Dirk Praet,

I was vaguly aware that Linus had thrown the toys out of the pram over the RNG in the linux kernel.

I only had to hear the words “Intel onboard…” to get a shudder down the spine and a queasy feeling.

To put it simply I’ve said repeatedly for something like fifteen years that the Intel “on chip” RNG went about things all wrong ( search this blog for my name and “magic pixie dust” to see some of them) and thus no confidence should be held about the quality of output.

Clive Robinson • September 10, 2013 7:26 PM

@ RobertT,

I’ve not attributed much to Intel’s RNG design team after I realised that accepted custom and practice was not on their objectives list, thus it appears that common sense was likewise not on their list.

As you know entropy sources tend to be “delicate flowers” and need much “care and attention” if they are to “give of their best”.

Accepted custom and practice back last century was to provide direct access to the entropy source buffer output so you could “test” it whilst in operation to see if it was failing or comming under undue influance etc as well as being able to use your own de-bias and filtering etc.

For whatever reason Intel’s team decided to only let you get at the output from a hash function thus only limited tests at best could be carried out. As I’ve said a few times befor a hash function does not magicaly create entropy thus it’s “magic pixie dust” thinking which at best only obsficates poor design.

Others however have pointed out that it could easily hide a fully determanistic generator. And they have a point even a simple counter xored with a constant will look random on the other side of a hash function.

If they don’t have a good analog team then I dread to think what is actualy comming off their “thermal noise” source and how they get it up to logic levels without it suffering “undue influance”.

As you say “complex but it’s not white noise”[1], and as Hanlon’s razor has it, “Never attribute to malice that which is adequately explained by stupidity”.

@ AC2

As I said I’d only heard that Linus had throw the toys out of the pram, and decided to “only use” the Intel RNG. The piece you quote aludes to other entropy sources which is thus not “only use” but “also use”, which is a whole different can of worms.

However his statment makes me pause for thought on his knowledge, True RNG’s are not CS-PRNGs thus cryptography has little to do with their design and use. Further from an entropy point of view a fully determanistic generator effectivly has zero entropy, thus cann’t be used to improve the entropy in the pool, just stir what’s there, which can actually be a problem that reduces the entropy in the final output.

To see why you have to consider how the safe guards on the entropy pool work. Obviously each time you read from the pool you leak a little bit of information about it’s state, and part of this leak is some of the entropy in the pool. Thus each time you read from the pool you decrease the entropy there, no matter how much you stir the pool the entropy does not go up. What makes the entropy go up is the real entropy hidden in the faux entropy of the entropy sources entering the pool. Now obviously you need to somehow “rate limit” the number of reads so that the loss of entropy is less than or equal to the gain of real entropy from the sources. But how do you do this, well theres three basic ways,

1, Cap the number of reads per unit of time.
2, Cap the number of reads to a fraction of the input bandwidth.
3, Estimate the entropy in the pool by some measure of the pool or sources.

The first is very easy and the second only marginaly harder, however neither is actually connected to the actual change in entropy in the pool, thus have to be set conservativly to avoid draining the pool of entropy. The third method is difficult at best because it requires seperation and measurment of real entropy from the faux entropy that just stirs the pool. One reason it is difficult is there is no reliable measurment that can tell between real and faux entropy, there are just measurments that can show one aspect of faux entropy being present to a certain probability. So you end up with a whole battery of tests that almost invariably cannot give real time results.

So most safe guards will be set to the first method with a few using the second method. Often they will be set far to optomisticaly due to not being able to measure the real entropy even remotly reliably.

So having a determanistic input which has no real entropy but produces faux entropy that passes tests will have the side effect of setting the safe guards way to optomisticaly.

Does this matter? Ordinarily it would be considered an almost philosophical question, however when it comes to security it’s very real as lives have been lost to poor security. Thus we take a leaf out of the crypto play book to get some assurance, we don’t use the raw output from the pool, we instead put it through one or more crypto primatives such as a block cipher or hash and use their output. This gives us, as an assurance, the percieved strength of the crypto primative we use.

Thus what we realy end up with is a tweakable CS-PRNG where the tweaking comes from a mixture of real and faux entropy. In most but not all cases this is acceptable.

[1] For those that don’t know what “white noise” is welcome to the world of engineers where there are more types of noise than you can shake a stick at. Noise is generaly considered an undesireable side effect of basic physics which interfears with a wanted signal. In general engineers classify noise by it’s statistical properties or by the physical effect that causes it. For use in TRNGs the most desired property in white noise is “independance” and it is this that distinquishes real from faux entropy. Faux entropy always lacks independance in some way, the question though is can it be detected or eliminated. For more info have a look at http://en.wikipedia.org/wiki/White_noise