Torvalds shoots down call to yank 'backdoored' Intel RdRand in Linux crypto Linux supremo Linus Torvalds has snubbed a petition calling for his open-source kernel to spurn the Intel processor instruction RdRand - used for generating random numbers and feared to be nobbled by US spooks to produce cryptographically weak values. Torvalds branded Kyle Condon, the England-based bloke who created the …
Randomness is a remarkably complex mathematical topic. It seems easy enough but is remarkably easy for the layman (like me sadly) to screw up and misunderstand. Still my guess is he means it might spit out verifiable random numbers today but if some magic date(s) (such as around 9/11 every year for example) is hit it suddenly by a slight bit doesn't for example. Just trusting a black box and verifying outputs has more than once in science been accepted as dogma and held things back.
This post has been deleted by its author
There is no such thing as "random", at least according to some researchers who tested the statement. "Random" is only our human inability to view a large enough sample of the event in order to perceive the pattern - there is always a pattern it is simply that we do not understand it (Pi is from the universal ratio of a circle's circumference to its diameter, and therefore the source of the mathematical construct is the universal presence of the circle in life itself). "Unpredictability", as Wiki's entry for "random", is truly what we humans interact with: our (distinctly) human inability to understand where an event will lead in the future.
If you understand that humans simply cannot see the "Big Picture" to break the code of "randomness", then you'll also accept the fact that events like the NSA breaking codes is inevitable: they used a large enough sample (enough computing power) to discern the patterns.
@Anonymous Coward,
What "there is not such thing as random"? Have you read professor Chaitin's work on algorithmic information theory where they define the very concept of randomness? Read it and then come back.
(I apologize, but it is funny how similar you sound like a Linux kernel developer, who thinks he knows everything, when in fact he has not studied the subject or know nothing on the subject. Hybris all Linux kernel developers display. But I am not accusing you of this, I am just saying it sounds a bit funny)
This statement is fundamentally false. Even if we would happen to live in a completely deterministic universe, the laws of quantum physics would only allow us probabilistic statements about the presence and the future. In other words, it is impossible to tell from within the universe if the universe is deterministic and it is therefore impossible to predict the future.
As we cannot predict the future, any measurement is probabilistic and contains true randomness in the sense of unpredictable outcomes or fluctuations. This randomness can be very small if we move towards the realm of classical physics, but the uncertainty is still there, it's just very small.
So if you want true randomness, use a quantum-mechanical measurement, such as described here or here. I'd have to look into it, but I would guess that a random number generator based on a UV LED, a beamsplitter, and two avalanche photodiodes should be quite simple and cheap.
So if you want true randomness, use a quantum-mechanical measurement, such as described here or here. I'd have to look into it, but I would guess that a random number generator based on a UV LED, a beamsplitter, and two avalanche photodiodes should be quite simple and cheap.
No need for such complexity: A simple forward-biased BJT will amplify the noise from inside its junction, which is a quantum-mechanical device. All you have to do is quantize it and remove any bias. Lots of examples on the web. One would hope that it is something like this drives the random number generator in the Intel chips, but who knows.
>There is no such thing as "random", at least according to some researchers who tested the statement.
Incorrect, try quantum fluctuation. Quantum mechanics runs on randomness.
The quantum noise from a diode is random and is used in random number generators. I don't know exactly what the intel engineers used, but basing it on the random quantum noise from a semi conductor junction would appear to be the easiest method.
However, if there is any post processing of the random number...
@Dagg: "The quantum noise from a diode is random and is used in random number generators. I don't know exactly what the intel engineers used, but basing it on the random quantum noise from a semi conductor junction would appear to be the easiest method."
Noise from a reverse-biased diode in breakdown is analog, not digital. Typically, the better it is, the tinier it is, and so harder to distinguish from amplifier noise, sampling, and a-to-d conversion. It is also not random, in that it has both an uneven statistical value distribution and long-term correlations between values. Indeed, the closer one looks, the worse the situation is. In theory it should work, but in practice requires deep understanding for serious results.
The investigation of a randomness device needs an unusual mindset, in the sense that simply claiming the sequence to be random is not enough, and statistical measures also are not enough. We know this because we could record any "random" sequence, and any test which would certify those results would be wrong when we re-use the sequence. But most designers will claim that their result "must" be random and stop, as they eventually must, simply to get on with life. For there is no natural end to this investigation. And the moment problems are found, and the device fixed, the investigation starts again.
Given a physically-random RNG device which passes basic tests, the only recourse is for someone other than the designers to invest extraordinary and unrewarding effort to expose pattern in the results. And if the results actually do cause change in the design, the only recourse is to do it all over again.
All of cryptography suffers from this. No cipher is proven secure in use. Generally speaking, all past ciphers have failed. Yet the only way to get a better cipher is to somehow, after years of work and as pure public service, find a problem in the current one. Nowadays, that would be the one approved by the US government, for why would insurance cover using anything else? And the end result would be yet another government-approved cipher.
The way around this is to not have a standard cipher, but instead have a standard cipher INTERFACE. Allow people to use whatever cipher they want. The more ciphers the better. Do not protect all knowledge in society with a single cipher!
Then require that 3 ciphers be used in sequence, each with an independent key, and one of the ciphers would be the current standard. This is multiciphering, with a result at least as strong as the standard cipher. Is "costly" multiciphering actually "needed"? Obviously it is, because we never should have trusted any single cipher, and certainly no longer can.
Note that all data ciphering should take a long random value or "nonce" (n-sub-once), encrypt it under that channel key, and then use the random value as a message key for the actual ciphering. By making the random value very long, we can reduce the impact of non-randomness from a randomness generation system we inherently cannot certify.
Realistically, though, ciphers start with plaintext and end with plaintext. It is unnecessary to "break" the cipher if one can access the plaintext, and malware bots do exactly that. Once again no tools exist for a normal computer which guarantee to detect a hiding bot. Obviously a prior-instrumented machine can see malware run and hide, but our problem is the normal machines we have, after the fact, and their problem is more about "infection" than malware running. While malware itself is encountered rarely, an infected machine runs malware on every session.
To address infection, we need to make the equipment not accept infection. That means no current hard drives (including USB flash and SSD), because they are easily written by malware. That also means no video card, because that BIOS could be infected. And it means re-flashing the motherboard and router BIOS periodically. But all of this could be avoided with proper hardware design, and the fact that it is not, is, frankly, suspicious. My guess is that certain organizations appreciate the fact that virtually every machine in the world can be infected, and that the users can do almost nothing about it.
"However, if there is any post processing of the random number..."
Because physical quantum noise is tiny, it must be detected by sensitive and error-prone physical processes. A common conceit is that randomness is the goal so "random" errors in detection can be ignored. That is false.
It is almost universal that the physics and detection mechanics combine to produce a non-flat or uneven statistical distribution from a physical RNG. If we want flat, post processing is not optional.
>Decent pseudo random generators will look like true random, but they aren't.
As do (rather topically) decent ciphertexts... but they also aren't... but they are what Intel openly admits to using to obfuscate the true nature of this "random" stream. If *the source* was *random* it couldn't benefit from obfuscation with the NIST/NSA's own AES. Yet AES ciphertext it is. Obfuscation = snake oil.
In my view, by far the most interesting, revealing and scandalous piece of this article was this snippet of TT's quote: "I am so glad I resisted pressure from Intel engineers to let /dev/random rely only on the RDRAND instruction..."
So Intel/NSA is actively going around "pressuring" projects to use its propitiatory "random" data, and only its propitiatory "random" data, to the exclusion of all else! Nothing remotely spooky about that. :O
"So Intel/NSA is actively going around "pressuring" projects to use its propitiatory "random" data, and only its propitiatory "random" data, to the exclusion of all else! Nothing remotely spooky about that. :O"
Any evidence, other than the quote? Interesting how some people so worried about security will take things at face value when it says what they want to hear..
As I explain further below, Netscape(?) mixed different random sources (current millisecond, space left on hard disk, etc) with a random number generator - and researchers broke it.
As Donald Knuth explains in his Art of Computer Programming: mixing random sources is never a good idea. His own home brewn random generator which mixed lot of stuff, had a remarkably short period before repeating itself. Read his book on random number generators. It is obvious that Linux kernel developers have not, nor have they studied the subject of cryptography. Donald Knuth says it is better to rely on a proven mathematically strong system, than making your own. Read my post further down.
"statistical tests for randomness."
You are such a cute little boy. Have a cookie poisoned by NSA.
They will make sure the statistical imbalance is of such a high order you can look for aeons to find out what they did, if you don't inspect the circuit.
Think of the following scheme:
On CPU power-up, one of 120000 different keys is used to start an RC4 keystream cipher. The output of that generator is then used in the RDRAND instruction and sold as "physical randomness".
The nice men of the gubbermint build a machine for a few million dollars to iterate said 120k possibilities.
Want to compromise https? Just get a CA or two in your pocket to give you a root cert, or a bank's signed key or sign your own key for the same domain, or bribe a highly placed employee to do the same, or just plain old fashioned steal the signing certs. Then you can do man in the middle attacks to your heart's content.
Compromising randomness is likely a far harder proposition.
Remember when they were planning this feature the NSA presumably thought the enemy might be Russia or China, or Iran, or Belgium. It's difficult to persuade the KGB to use Google for it's root CA.
Although nowadays it's probable that both the NSA and KGB outsource to Booz-Allen
However, a fake certificate will have to use a fake public key and that can be detected by anyone who knows the correct public key. So it's more likely that stealthy listening is done with knowledge of the private key and then the spooks don't have to bother the CA chaps.
How to get the private key? Well Google probably just gives it to them. Otherwise, there's legal pressure, side-channel attacks, or hacking.
How to get the private key? Well Google probably just gives it to them. Otherwise, there's legal pressure, side-channel attacks, or hacking.
You've obviously never actually applied for a cert then. You generate your own keys and give the public key to the CA for signing. They never see your private key.
Yes. I noticed the original article was very careful to say 'circumvented or broken' (or words to that effect). And all the articles since then have, umm, edited for shortness. Yeah, that the ticket! Edited for shortness, not edited to enflame and/or mislead.
Using AES256, I think you'll need 2**256 iterations before the pseudo random sequence repeats itself which is large in relation to the number of atoms and time quanta in the universe and its expected lifetime. Of course if you know block X in the system you also know block X+1, but if blocks X .... X+n are used as key material e.g. in a stream cypher where attacker doesn't get to see any X, the sequence of key material will be unknowable by viewing ciphertext created by XORing plaintext and the key which effectively becomes the one-time pad generated once Alice and Bob share secret X e.g. using Diffie Hellman.
No, the easiest way to compromise a pseudo random number generator (a truly random number generator can never be compromised, except by perverting its correct operation) is to know both the algo and the seed. Unless you're just talking about hunting for skew and similar design failings - in which case, yes, people test for that stuff now. it's precisely what the statistical tests are designed to catch.
For example, suppose this Intel TPM output was actually a pseudo random number generated by adapting AES to function as a stream cipher (just as Intel's documentation describes it as being). Then it would certainly LOOK random. It would pass any statistical analyses you might care to throw at it (as it does). But would it be random? That would depend on upon what it's being applied. If it's just an exercise in futility applied to a true random stream for the sheer hell of it (just as Intel's documentation describes it as being) then it too can be considered truly random. If it was the naked stream cipher seeded perhaps buy a uuid and simple on-chip counter/clock (for example) then it would still look random, pass all the tests, differ from everyone else's, etc but be totally predictable and derived from a vanishingly small set of data.
So what is it? Unless you're one of a handful of trusted engineers at NSA/Intel, then your only way to know is either:
1) Crack open a TPM chip and indulge in a spot of etching, microscopy and logic analysis while, no doubt, pitting your wits against the best obfuscation that NSA/Intel can contrive.
2) Crack AES. Assuming it really is AES as documented.
In this case I simply don't know if he's right or wrong, and quite frankly I also don't quite care any more.
But I do think Torvalds is really losing it. Some websites even seem to start recollections of Torvalds' outbursts and the one I came across on Paritynews also mentioned another recent outburst regarding ARM/Soc developers:
"Ok. I still really despise the absolute incredible sh*t that is
non-discoverable buses, and I hope that ARM SoC hardware designers all
die in some incredibly painful accident. DT only does so much.
So if you see any, send them my love, and possibly puncture the
brake-lines on their car and put a little surprise in their coffee,
ok?".
At first I thought this comment to be fake(d). The article I mentioned above linked to this entry on the Indiana LKML archive and being unfamiliar with all the LKML archives I started digging on lkml.org. And sure enough; the same message is present.
I think comments like these are crossing borders, not to mention being dangerous.
One of the reasons Torvalds bursts out in the way he does is because he feels there's no other way to get his point across. Apparently, according to him, there are a bunch of "stupid people" subscribed to the mailing list and the only way to get his point across is to be blunt and direct.
I can see that, I don't agree, but each to his own.
But if people are so "stupid" that you have to yell and rant to get your point across, then why can you trust them to understand that what is being said here is just "an opinion" or maybe even a "joke"?
That doesn't quite add up for me. Now all of a sudden people are smart enough to understand the "subtleties"?
As said at the top I don't really care that much any more, but I have to wonder how long before this is really getting out of control. I hope for Torvald's sake that no ARM/Soc developer gets himself in a car accident.
I guess we should just be glad one of the world's great coders (speed he got git up and running proved that) only has some sociopath tendencies. He could be in jail for murder like that idiot Reiser. Lol as almost all on here know computer skillz != people skillz.
Yeah, but it still doesn't make it acceptable to behave in this way. Calling for someone to kill people on the Internet is pretty poor, even if "it's a joke". We wouldn't put up with this behaviour in a pop star, it's not ok in a programmer, especially if he runs a high profile project.
There's no doubt that Torvalds suffers from a severe lack of both social skills and tact, but the man is a very talented coder and has done a very good job as the chief maintainer of what has become the most common kernel in the world.
That said, I've never gotten involved with kernel development partially (and only partially) because of the way he treats people. Much as I respect him as a coder and love Linux I do not and would not tolerate being spoken to in the manner that Torvalds usually speaks to people with whom he has disagreements. I've put people on my ignore lists in several forums for that sort of nonsense. It's one thing to disagree, even to disagree forcefully, but it's entirely another to start hurling insults at the first sign that you might be smarter than the person on the other side of the debate.
Meh, the IT industry really isn't known for satisfying bruised egos with fisticuffs. People get even in different ways; a good example is that picture El Reg uses of Torvalds where he looks like an angry toilet paper salesman flipping you off for choosing a different brand. The industry has a long memory too. I kind of think it is worse than getting belted in the gob, which you get over quickly. Bruised egos take a lot longer to heal.
Every industry has a way of dealing with assholes and to be honest, Torvalds just happens to be 'famous' and have a shitty attitude. There are many, many people in the IT industry who are nameless faces but they're known for being raging dickheads. I don't know why, but piss poor attitudes are quite prevalent in this industry.
There are four welders in our machine shop though and I'm pretty sure they'd put a cigarette out in your eye if you talked to one of them like that. But that's their industry, they electrocute each other for fun...
"But that's their industry, they electrocute each other for fun..."
Which conversely a lot of office workers or programmers would try to do them for assault for. :D Different people have different ways of communicating. I kind of resent this insufferable choking culture of tissue paper softness that is being forced down from above. I'd far rather Linus's transparent position than a lot of the nicey-nicey double-dealing I've had to put up with from others.
"Does Torvals actually speak to people like this face-to-face or is it only behind the safety of a keyboard"
I've seen him present (on GIT and the failings of the CVS / Subversion model). He began the presentation by saying "You can disagree with me if you want, but if you do then you're stupid and you're ugly". And you know what? It got a good laugh from the crowd. He's not only very smart, he's also quite funny. I think he may be wrong on this, but I have no problem with the way he communicates.
@h4rm0ny
"...I've seen Torvalds present (on GIT and the failings of the CVS / Subversion model). He began the presentation by saying "You can disagree with me if you want, but if you do then you're stupid and you're ugly". And you know what? It got a good laugh from the crowd...."
You know, they would laugh at anything he would say. They are his worshippers, and he is their God. He is flawless in their eyes. Even if Torvalds insulted and humiliated them, they would gladly accept being peed upon. They are brain washed, a sect.
No sane person would accept Torvalds behavior, as we can see in this thread.
"but it's entirely another to start hurling insults at the first sign that you might be smarter than the person on the other side of the debate."
In his case I'd say it's more a case of the moment he thinks he's smarter. I would respect his coding skills, but his being a monumental dick tends to eclipse them. Since one of the most touted benefits of open source is that open collaboration leads to good software (in my opinion it should be "can lead to",) maybe a bunch of more level-headed people should be looking at ways to reduce dependence on him and his approval.
If he is tired of idiots on the mailing list, then why not just set up a white-list for who can send to it? A lot of projects do this where only a small group is allowed to post to the mailing list but anyone can subscribe to it, in this case, limit the people who can post to it to just the kernel devs themselves and maybe one or two exceptions. And if these idiots are kernel devs, what is he doing letting people like that do such critical work?
But what do I know? I'm just a 'Masturbating Monkey'. http://article.gmane.org/gmane.linux.kernel/706950
Torvalds' current pattern of actions is all too typical of men who see themselves as "successful" - it is simply called THE GOD COMPLEX. It is all too common in today's society - I am successful, so I know more about everything than you do - and it is what has poisoned society for the rest of us.
In a nutshell: it is male egotism, multiplied by an exponent of money and/or social acknowledgement. From bankers to lawyers to politicians to businessmen to coders, we live in the shadow that it cast across the land.
We are truly doomed.
What you are talking about is called "Management by Intellectual Intimidation". It requires the 'manager' to be put on a pedestal by others who consider him to be intellectually superior to themselves. It is a form of hero worship/veneration.
By exploding in a fit of temper you cause your 'subordinates' to carry your torch for you. The person you're exploding at is obviously so inferior you can't be bothered to stoop to his level and explain things. So your private assault force takes care of it for you. It is an effective form of management. I don't like it but it does make things easier on the 'manager'. His people do all the work.
As an interesting note: This practice, or rather attempts at it, runs rampant in IT. The big difference is that others must place you on the intellectual pedestal for it to be considered a management style. If a person puts themselves on the pedestal and does this they're just being arrogant dicks. Either way it is not an accurate measure of intelligence, just people's perception of intelligence.
RDRand contribution is diluted quite a bit on a modern system. So from that perspective Torvalds is right.
From the perspective of TinFoil Assurance... When you read the architecture for RDRand implementation it is quite clearly specified that it is "postprocessed" to ensure that it can deliver a high rate random stream compliant to a set of particular FIPS-es. It is not a raw entropy source which is the significant difference between it and for example Via C7 implementation or some of the older hardware random generators (these you have to feed into a pseudorandom generator to produce a high rate stream).
In any case, I am not going to take Linus judgement on this - I will wait and see what Theo De Raadt Tinfoil brigade will do in the OpenBSD random number generator. This will say all that needs to be said about the quality of that instruction's random numbers.
I hunch that what DeRaadt does will not just be motivated by the technical aspects but also by his ideology.
Very few people would be able to access the inner workings of the instruction to make an informed decision on how it works. Those that reject the instruction just because they don't know how it works are acting "on principle" and likely not with a sound technical analysis.
Where Kyle Condon's argument falls down is thinking that the magic instruction can undo entropy. Even if it was hardwired to emit 0, it would not compromise the additional entropy sources.
I'm no C programmer but even I can read comments and verify a function does as it says. This is the header for the "arch" RNG access function. This is not the function that is used for /dev/random and is probably relegated as a last resort for /dev/urandom which doesn't block when it runs out of entropy as /dev/random will.
I think the point is clear.
/*
* This function will use the architecture-specific hardware random
* number generator if it is available. The arch-specific hw RNG will
* almost certainly be faster than what we can do in software, but it
* is impossible to verify that it is implemented securely (as
* opposed, to, say, the AES encryption of a sequence number using a
* key known by the NSA). So it's useful if we need the speed, but
* only if we're willing to trust the hardware manufacturer not to
* have put in a back door.
*/
Cheers
Jon
The Register 
Biting the hand that feeds IT
Copyright. All rights reserved © 1998–2024
