Torvalds' response to whether RdRand could be compromised in the Linux kernel(change.org)
change.org
Torvalds' response to whether RdRand could be compromised in the Linux kernel
http://www.change.org/en-GB/petitions/linus-torvalds-remove-rdrand-from-dev-random-4/responses/9066
21 comments
Thanks for the excellent answer. As a non-cryptographer who can't read crypto code and also can't be bothered to download the Linux sources and find the part where random numbers are generated, this is a much better response than Linus'. "Read the source" isn't a suitable answer even for most technical people. For regular people, it is completely out of the question.
Respectfully, if you can't read the code, you're not really entitled to have opinions about it. Instead, try asking people you trust who can read code what they think.
Although, I should add that there's this API which uses the output of RdRand straight up:
/*
* Get a random word for internal kernel use only. Similar to urandom but
* with the goal of minimal entropy pool depletion. As a result, the random
* value is not cryptographically secure but for several uses the cost of
* depleting entropy is too high
*/
static DEFINE_PER_CPU(__u32 [MD5_DIGEST_WORDS], get_random_int_hash);
unsigned int get_random_int(void)
{
__u32 *hash;
unsigned int ret;
if (arch_get_random_int(&ret))
return ret;
[...]
As I understood it, TCP sequence numbers also got the direct output of rdrand. In neither case do I think that's meaningful; the needs of both are sub-cryptographic, due to environmental constraints (ie, no matter how high-quality the randomness you feed it, TCP seqnos and executable address space aren't going to be cryptographically random anyways.)
The only use of randomized address space I know is to mitigate other attack vectors (stack smashing and other arbitrary code execution exploits). So it would just make exploiting an other vulnerability easier, it wouldn't be a vulnerability on its own. So it's still a bit far fetched conspiracy-wise as far as I'm concerned.
I think it would be a justified move (in an evil kind of way). Most of the interesting exploits these days need to leverage more than one vulnerability. This kind of thing would give you a marked advantage in penetrating systems, and do so in a non-obvious way without exposing the targets to other attackers. The advantage would be something like 10x, or whatever the difficulty factor is that ASLR adds to the average exploit. It would also be a good match for probabilistic/big picture kind of approach that a big organization can afford to take.
But will owning RdRand give you good enough control over ASLR, that's another question.
But will owning RdRand give you good enough control over ASLR, that's another question.
>Respectfully, if you can't read the code, you're not really entitled to have opinions about it.
I disagree. That is like saying if you can't read or write English, you shouldn't have a say in a law that affects you. I bet 90% of the users here don't know how MD5 or SHA1 works but when asked they can still recommend you a better cryptographic hash. I think everyone should be entitled to opinions and proper response because there is no such thing as a dumb question when it comes to security.
I disagree. That is like saying if you can't read or write English, you shouldn't have a say in a law that affects you. I bet 90% of the users here don't know how MD5 or SHA1 works but when asked they can still recommend you a better cryptographic hash. I think everyone should be entitled to opinions and proper response because there is no such thing as a dumb question when it comes to security.
The law is imposed upon you whether you want it or not. With the kernel you're free to take it or leave it. The core of kernel development is free to listen to people, or not. They do seem to want a pretty deep understanding.
You're free to just fork the kernel and make it work however you wish. In practice nobody does this. When you're sophisticated enough to explain what you want to the high standards team, it is easier to just make your case to that team.
You're free to just fork the kernel and make it work however you wish. In practice nobody does this. When you're sophisticated enough to explain what you want to the high standards team, it is easier to just make your case to that team.
> The law is imposed upon you whether you want it or not. With the kernel you're free to take it or leave it.
Its not always as black and white. There are times when you are forced to use the kernel, maybe a default on your shared hosting that cannot be changed or a restriction put by your team's Administrator for security.
Forking is not the effective answer either, its just not practical, its too complex to maintain and upkeep with the new changes. Like you said, in practice nobody does this. Had this not been the case, we would have seen less whining about PHP's problems and more forks to fix it.
Its not always as black and white. There are times when you are forced to use the kernel, maybe a default on your shared hosting that cannot be changed or a restriction put by your team's Administrator for security.
Forking is not the effective answer either, its just not practical, its too complex to maintain and upkeep with the new changes. Like you said, in practice nobody does this. Had this not been the case, we would have seen less whining about PHP's problems and more forks to fix it.
Whether you can follow all the code in random.c (few can), you can probably get through the comments and have a better understanding of how random number generation works in a Linux environment. Start right after the line:
> (now, with legal B.S. out of the way.....)
and continue until your brain hurts, rinse, and repeat. Peck away at a couple functions here and there. This is a really good exercise for most developers.
> (now, with legal B.S. out of the way.....)
and continue until your brain hurts, rinse, and repeat. Peck away at a couple functions here and there. This is a really good exercise for most developers.
No need to download anything, the Linux kernel has a web interface to Git, of course.
The relevant code is here: http://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.g....
The relevant code is here: http://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.g....
Interesting comment...
/*
* 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.
*/
void get_random_bytes_arch(void *buf, int nbytes)Of course if RdRand is aware of how it is to be used and looks at the place it is supposed to be XORed with, then including it would hurt.
But it would need to be actively aware of what is where in memory to do this.
But it would need to be actively aware of what is where in memory to do this.
Yes, sure, that's a possibility. You could imagine a situation where a microcode update to the Intel processor is written to modify RdRand in the knowledge of specific Linux versions and it would alter the values being returned because it would be aware of where it is used. You might even imagine some cleverness that actually alters the surrounding program's execution.
In a past life I did stuff like this where a device driver actually modified a running program to patch it to fix bugs/compatibility. It's not a complete fantasy to imagine that this might be possible.
But, hey, it's software. Anything possible; with computers it's best to look for what's likely, not what's possible.
In a past life I did stuff like this where a device driver actually modified a running program to patch it to fix bugs/compatibility. It's not a complete fantasy to imagine that this might be possible.
But, hey, it's software. Anything possible; with computers it's best to look for what's likely, not what's possible.
But, hey, it's software. Anything possible; with computers it's best to look for what's likely, not what's possible.
When it comes to security, this is a horrible assumption.
It is the nature of the game that an attacker should be expected to use whatever piece that they control in the most malicious way possible. Thus if it is possible, and they are motivated, then you should never assume that they wouldn't do that. Because push comes to shove, why wouldn't they?
And if you're wrong, well, a little paranoia never hurt anyone. Particularly since in this case exercising paranoia is a simple matter of mixing in hardware randomness BEFORE doing all of the other complicating stuff, as opposed to the current order of doing all of the other complicating stuff AND THEN grabbing from potentially untrustworthy hardware that could be playing tricks.
When it comes to security, this is a horrible assumption.
It is the nature of the game that an attacker should be expected to use whatever piece that they control in the most malicious way possible. Thus if it is possible, and they are motivated, then you should never assume that they wouldn't do that. Because push comes to shove, why wouldn't they?
And if you're wrong, well, a little paranoia never hurt anyone. Particularly since in this case exercising paranoia is a simple matter of mixing in hardware randomness BEFORE doing all of the other complicating stuff, as opposed to the current order of doing all of the other complicating stuff AND THEN grabbing from potentially untrustworthy hardware that could be playing tricks.
Thus if it is possible, and they are motivated, then you should never assume that they wouldn't do that. Because push comes to shove, why wouldn't they?
That's sort of my point. "Push comes to shove" -> they'll do the easy thing first.
That's sort of my point. "Push comes to shove" -> they'll do the easy thing first.
And when the easy thing does not work, they go one step farther.
If their goal is to target Linux, and they know what Linux code looks like, why not take it one step farther?
If their goal is to target Linux, and they know what Linux code looks like, why not take it one step farther?
This can be done far more simply in hardware. Simply look at the instruction decode pipeline, and XOR with the operand of the next instruction that consumes your return value to bias the result.
Backdooring the XOR instruction would be far more useful.
For every person with the seriousness and capability to actually understand the crypto risks of an implementation there seem to be about 50 "I think" people that most often than not are "too paranoid with the wrong things", think they know crypto but don't know basic math, etc
Like using 1 as the e in RSA instead of 65537. (This discussion happened in a encrypted chat app, can't remember). And then blam, first comment when this was detected, is by an "expert" saying how it should be 1 instead of 65537. Zero knowledge of how RSA works and how 1 makes absolutely no sense there.
One of the biggest risks of encryption now is noise. And clueless developers (including API developers), but hopefully we'll find out that there are obscure interests between leaving APIs with ECB encryption available.
Like using 1 as the e in RSA instead of 65537. (This discussion happened in a encrypted chat app, can't remember). And then blam, first comment when this was detected, is by an "expert" saying how it should be 1 instead of 65537. Zero knowledge of how RSA works and how 1 makes absolutely no sense there.
One of the biggest risks of encryption now is noise. And clueless developers (including API developers), but hopefully we'll find out that there are obscure interests between leaving APIs with ECB encryption available.
I kind of worry about that, too. Up until now, it has been NSA pretty much the ones establishing the new security standards, since they have the best minds on it.
But now we can't trust them, or even anyone who's "worked" for them, but now quit because of it was revealed that they are doing with their work (at least I like to imagine there are people who think like that at the NSA).
So what now? I guess my hope is more math and cryptography professors from around the world (not just US), will put their minds to work on this, in the interest of the whole Internet community. If that happens, in the end would be for the best.
But now we can't trust them, or even anyone who's "worked" for them, but now quit because of it was revealed that they are doing with their work (at least I like to imagine there are people who think like that at the NSA).
So what now? I guess my hope is more math and cryptography professors from around the world (not just US), will put their minds to work on this, in the interest of the whole Internet community. If that happens, in the end would be for the best.
Here's an idea for one of those "We The People" petitions: split up the NSA's COMSEC and SIGINT/MASINT divisions into two-or-more agencies. The COMSEC one can keep being the "National Security Agency"; the SIGINT one can be the "Central Signals Agency" or something[1]. Now add a law stating that:
- the CSA can't do any SIGINT that works at cross-purposes to the NSA's mission (e.g. putting backdoors in crypto libraries so widely-used that government secrets are likely riding over lines relying on those libraries somewhere), and that
- any time the CSA discovers a problem with crypto the NSA relies on, they have to immediately communicate that fact to the NSA, and that communication has to go through public channels.
With that in place, I'd feel safe (in fact, safer than ever before) trusting the NSA's crypto. They'd have one pure incentive-structure: good crypto for securing gov/mil communications; and the CSA, though wreaking havoc everywhere else, would be locked out of hindering them in it.
---
[1] not "Foreign Signals Agency", since they don't seem to plan on relinquishing their Domestic Signals.
- the CSA can't do any SIGINT that works at cross-purposes to the NSA's mission (e.g. putting backdoors in crypto libraries so widely-used that government secrets are likely riding over lines relying on those libraries somewhere), and that
- any time the CSA discovers a problem with crypto the NSA relies on, they have to immediately communicate that fact to the NSA, and that communication has to go through public channels.
With that in place, I'd feel safe (in fact, safer than ever before) trusting the NSA's crypto. They'd have one pure incentive-structure: good crypto for securing gov/mil communications; and the CSA, though wreaking havoc everywhere else, would be locked out of hindering them in it.
---
[1] not "Foreign Signals Agency", since they don't seem to plan on relinquishing their Domestic Signals.
You think adding laws is going to solve the problem?
Not a chance.
Not a chance.
Solve which problem? Adding laws could solve the very small problem of "NSA crypto being trustworthy crypto for use by anyone other than the NSA." Obviously my proposal won't solve any large problems (like making the organization I dubbed the CSA stop... doing the stuff it does; which implicitly further requires that the government stop wanting them to do that stuff.) But specific problems have specific solutions.
> Up until now, it has been NSA pretty much the ones establishing the new security standards, since they have the best minds on it.
They have? I thought they were still regularly fought and ignored by the rest of the crypto community.
They have? I thought they were still regularly fought and ignored by the rest of the crypto community.
I thought of this issue over a year ago. See:
http://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.g...
https://plus.google.com/117091380454742934025/posts/SDcoemc9...
http://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.g...
https://plus.google.com/117091380454742934025/posts/SDcoemc9...
One question based on discussion up thread.
With the current code, if the hardware was truly untrustworthy, it could do a brief analysis of upcoming CPU instructions, and if it sees that it is XORed with something, it could quickly XOR itself with that something in advance so that it can completely control the output of the function.
For sheer paranoia, wouldn't it make sense to mix the hardware entropy into the pool earlier in the function so that it malicious hardware would have to work harder to control the output? It could, of course, still take over. But logic to do so would have to be more intrusive than the XOR hack that I suggested, and so would be more likely to get caught.
With the current code, if the hardware was truly untrustworthy, it could do a brief analysis of upcoming CPU instructions, and if it sees that it is XORed with something, it could quickly XOR itself with that something in advance so that it can completely control the output of the function.
For sheer paranoia, wouldn't it make sense to mix the hardware entropy into the pool earlier in the function so that it malicious hardware would have to work harder to control the output? It could, of course, still take over. But logic to do so would have to be more intrusive than the XOR hack that I suggested, and so would be more likely to get caught.
I'm not convinced the XOR hack could be done in a way such that it wouldn't be noticed by someone inside Intel. But sure, we could do that. It would require calling RDRAND a new more times, but it's relatively cheap.
The concern is not that Intel wouldn't notice it. The concern is that Intel is complicit in the attack.
Where do I start a petition to make people aware of what a complete a-hole Linus Torvalds is? This is clearly identifiable, consistent behavior.
He may be technically correct in his response (or he may not be - I really don't know), but there's certainly nothing wrong with asking questions. Questions shed light. In fact, I now know 0.05% more about the Linux question even by this question, even if it did not have merit in the end.
So to answer Linus' question directly: "Where do I start a petition to raise the IQ and kernel knowledge of people?"
You actually don't need a petition. Just respond. And of course how you respond to other human beings is up to you. Development is complicated. We should all keep learning from one another and encourage communications.
He may be technically correct in his response (or he may not be - I really don't know), but there's certainly nothing wrong with asking questions. Questions shed light. In fact, I now know 0.05% more about the Linux question even by this question, even if it did not have merit in the end.
So to answer Linus' question directly: "Where do I start a petition to raise the IQ and kernel knowledge of people?"
You actually don't need a petition. Just respond. And of course how you respond to other human beings is up to you. Development is complicated. We should all keep learning from one another and encourage communications.
The original petition is an utter waste of time.[0] It provides no insight to the problem, no analysis, no debug, no "if this, then that". It's petitions like this that are "clearly identifiable, consistent behavior" of people who shouldn't be petitioning FREE, OPEN-SOURCE, SOFTWARE. Put an issue in github if this is such a big deal...no one asked this petitioner to use Linux, nor paid for it.
Development is complicated. We should all keep learning from one another and encourage communications
Yes, but calling out the BDFL of one of the most influential pieces of technology is straight up utter poor communication. Linus should have ignored this.
Where do I start a petition to make people aware of what a complete a-hole Linus Torvalds is?
You know what you do with people who are assholes? Ignore them. I find it quite funny that people criticize Linus for his attitude. Personally, I don't condone it and would be my prime reason for not working with him. But you know what? I don't have the capability or know how to contribute to the Linux kernel, so who am I to judge an organization's "style of communication" for providing something that has created massive value to my everyday work?
[0] http://www.change.org/en-GB/petitions/linus-torvalds-remove-...
Development is complicated. We should all keep learning from one another and encourage communications
Yes, but calling out the BDFL of one of the most influential pieces of technology is straight up utter poor communication. Linus should have ignored this.
Where do I start a petition to make people aware of what a complete a-hole Linus Torvalds is?
You know what you do with people who are assholes? Ignore them. I find it quite funny that people criticize Linus for his attitude. Personally, I don't condone it and would be my prime reason for not working with him. But you know what? I don't have the capability or know how to contribute to the Linux kernel, so who am I to judge an organization's "style of communication" for providing something that has created massive value to my everyday work?
[0] http://www.change.org/en-GB/petitions/linus-torvalds-remove-...
In general, I would agree. When he attacks ad-nominem people on the mailing list, I think he's being a douche.
In this instance he's just confronted to a bunch of people signing a petition, most of whom probably don't understand anything about the crypto involved and jump into a bandwagon after all the PRISM controversies. Petitions on change.org are not a good way to dictate the linux kernel roadmap.
That's not democracy, that's demagogy.
In this instance he's just confronted to a bunch of people signing a petition, most of whom probably don't understand anything about the crypto involved and jump into a bandwagon after all the PRISM controversies. Petitions on change.org are not a good way to dictate the linux kernel roadmap.
That's not democracy, that's demagogy.
I guess what Linus is implying is that the petition was added without understanding much about how it works. If you are complaining, make sure you understand the details so that you don't waste anybody's time. There are also other forums to raise this question, instead of a petition.
I want Linus to continue being Linus because it works. There may be other ways to run Linux development, but it is too important a project to leave that to chance.
I want Linus to continue being Linus because it works. There may be other ways to run Linux development, but it is too important a project to leave that to chance.
Why is he being an a-hole? There are times to be civil, and times to be blunt. The original petition disparagingly calls Linux "a NSA approved partner", and boldly claims that removing a feature from the kernel would improve security when it wouldn't. The answer Linus gives is, in this case, quite fitting.
The petition is really very stupid, and anyone with basic knowledge of cryptography will know that. Linus is rightly annoyed, and is fully within his rights to attempt to discourage this stupid behaviour by reacting abrasively.
It's pretty common knowledge that Linus is abrasive and abrupt and frequently rude. It's typically speculated that he does it to manage his workload. This is a case where a response from him shouldn't have been necessary. Just read the code. That's one of the benefits of OSS after all, right?
"Where do I start a petition to make people aware of what a complete a-hole Linus Torvalds is?"
Don't worry about it, he'll solve that problem all by himself.
Don't worry about it, he'll solve that problem all by himself.
Linus deals with a lot of shit in a professional manner. He uses some words that some people don't like. Personally, I find his language enlighteningly clear. If you can ask a sensible question, it will be answered sensibly. If you ask a question having made little effort to find the answer without directly hassling people, you will be answered brusquely.
There's certainly nothing wrong with asking questions in this case - on some older kernel versions, and I believe some current distro kernels, /dev/urandom does return the result of RdRand directly.
Which older versions and which distro's current kernels? This is easily verifiable. Name them, or don't make such claims.
> but there's certainly nothing wrong with asking questions.
Starting a petition is very different from asking a question. The former is much more aggressive than the latter, and so an aggressive answer is understandable.
Starting a petition is very different from asking a question. The former is much more aggressive than the latter, and so an aggressive answer is understandable.
There are those who have technical concerns. But there is no technical solution to a compromised chain of trust - including, "Trust me, I'm Linus and I know what I'm doing."
Ken Thompson described it as "Trusting Trust."
http://cm.bell-labs.com/who/ken/trust.html
Ken Thompson described it as "Trusting Trust."
http://cm.bell-labs.com/who/ken/trust.html
This keeps going around. There's several ways to verify outpuf. For example, GCC has assembler output. You can easily verify assembly and, relatively easily, write an assembler from scratch, so it's actually easy at least verify output without writing a new compiler (or just write a new compiler)
"For example, GCC has assembler output. You can easily verify assembly"
Ah but it is not as easy as you think. Let's put it this way: how did you compile whatever software you are using to verify that assembly dump? Even if you were to examine binary outputs you would need to trust the tools you are using. You also need to trust your kernel, which might just have you open a file that looks innocent while executing a file that is infected.
Ah but it is not as easy as you think. Let's put it this way: how did you compile whatever software you are using to verify that assembly dump? Even if you were to examine binary outputs you would need to trust the tools you are using. You also need to trust your kernel, which might just have you open a file that looks innocent while executing a file that is infected.
Those are techniques for generating a new chain of trust, they don't solve the non-technical problems which arise from a dependence on trust - i.e. if you can't even trust Ken Thompson, who can you trust?
Solipsism is a solution that in the end requires making your own CPU.
Solipsism is a solution that in the end requires making your own CPU.
Previous discussion: https://news.ycombinator.com/item?id=6358550
(Not sure why the link was deleted from HN?)
(Not sure why the link was deleted from HN?)
That deleted one was posted by me. After I posted it I felt guilty about triggering yet another gossipy discussion about Linus, so I deleted it. Not that I was blameless, choosing such a gossipy link to submit.
If you assume the CPU is compromised, then mixing in RdRand among other entropy sources is still not safe. For instance, the RdRand instruction could set a flag that, with some small probability, zeros out anything XORed with it so you occasionally get zeros in the entropy pool. Or some other known-to-the-bad-guys value.
If the CPU is compromised then you've already lost.
If the CPU is compromised then we should try to find out about it.
We might not all be cryptography experts like Linus is implying he is, but he saying there's no way the CPU could be compromised and use the backdoor against Linux? If not, then he should invite more scrutiny, not less.
From what I understand it would be very hard to even know if the CPU is compromised, so why is he so absolutist about it then, if it's impossible for him to prove with absolute 100 percent certainty that it's false?
As the post at the top says: trust no one.
We might not all be cryptography experts like Linus is implying he is, but he saying there's no way the CPU could be compromised and use the backdoor against Linux? If not, then he should invite more scrutiny, not less.
From what I understand it would be very hard to even know if the CPU is compromised, so why is he so absolutist about it then, if it's impossible for him to prove with absolute 100 percent certainty that it's false?
As the post at the top says: trust no one.
> If the CPU is compromised then we should try to find out about it.
This is a copy-paste of my comment from an older thread [0]:
http://www.xakep.ru/post/58104/ (use Google Translate)
TL;DR
The author has found an undeclared software module (backdoor?) working as a hyper-visor in the System Management Block chip on the South Bridge working with Intel CPU with VT virtualization technology.
[0] - https://news.ycombinator.com/item?id=4462782
This is a copy-paste of my comment from an older thread [0]:
http://www.xakep.ru/post/58104/ (use Google Translate)
TL;DR
The author has found an undeclared software module (backdoor?) working as a hyper-visor in the System Management Block chip on the South Bridge working with Intel CPU with VT virtualization technology.
[0] - https://news.ycombinator.com/item?id=4462782
Sure, but the CPU has to perform correctly on general-purpose computations so it's not too likely that, for example, the multiplication instructions occasionally give wrong results. Detecting cryptographic code executing in the CPU and subverting it is hard in general, but quite easy if you have a special instruction used only for the purpose.
There are multiple special-purpose security instructions; AESENC, for instance, or even PCLMULQDQ, which was added to speed up GCM. Which ones should we keep and which ones should we jettison?
Since AESENC and PCLMULQDQ are meant to be deterministic - including their timing - it's rather harder for Intel to subvert them in a way that's not detectable than something like RDRAND.
You've overshot, though. The solution to what you're describing isn't to remove RdRand from the Linux kernel, it's to entirely give up. This is not a defense of the change.org request.
Buy CPUs from two (or n) different vendors and run a user space lockstep execution virtual machine between them. Unless all vendors are compromised in exactly the same way, the output will fail to verify.
Of course, this would prevent you from using RdRand as your VM implementation will only be able to call on deterministic instructions...
Of course, this would prevent you from using RdRand as your VM implementation will only be able to call on deterministic instructions...
[deleted]
"with some small probability, zeros out anything XORed with it"
You really don't know what you're talking about. Really
Write the code for this then, go ahead, and show how it would work (hint: it doesn't)
And as others said, if your CPU is compromised you already lost.
You really don't know what you're talking about. Really
Write the code for this then, go ahead, and show how it would work (hint: it doesn't)
And as others said, if your CPU is compromised you already lost.
Your dismissive tone is rude and uncalled for. There's nothing fundamentally impossible about the method tlb is suggesting. It would actually be quite a clever hack.
It can't be done. Between the RdRand instruction and the next XOR nothing guarantees that:
1 - The task won't be preempted
2 - That XOR will be used for entropy calculation
And even if n. 1 doesn't happen, n. 2 is very hard to guarantee (and easy to avoid)
Of course I'm dismissive because it's obvious to me it can't work like that. But please let's continue discussing impossible theories and barking at wrong trees.
There are easier and more effective attacks than that.
1 - The task won't be preempted
2 - That XOR will be used for entropy calculation
And even if n. 1 doesn't happen, n. 2 is very hard to guarantee (and easy to avoid)
Of course I'm dismissive because it's obvious to me it can't work like that. But please let's continue discussing impossible theories and barking at wrong trees.
There are easier and more effective attacks than that.
More to the point, a change like this is very likely to be _noticed_. Both in terms of the complexity that would be required to make such a change in the microcode, and if the logic screws up and tampers with the wrong XOR, it will cause a bug that people will search for and eventually discover that the CPU was screwing up XOR under some circumstances. Remember the firestorm over the FDIV bug?
It doesn't have to work every time, just occasionally (1 in 1,000,000) is enough to introduce an exploitable weakness. So task preemption isn't a problem.
XOR is used for entropy calculation in the Linux kernel, as Dale Emmons points out in the article.
XOR is used for entropy calculation in the Linux kernel, as Dale Emmons points out in the article.
> So task preemption isn't a problem
Yeah, you're just crashing a different task
> XOR is used for entropy calculation in the Linux kernel
You sound like you don't know C, less alone have any knowledge of assembly language. That phrase is correct but absolutely useless.
Do you know how that code snipped is translated to assembly? On x86? On x64? With optimisations? Without? How different OSs would use RdRand?
Yeah, you're just crashing a different task
> XOR is used for entropy calculation in the Linux kernel
You sound like you don't know C, less alone have any knowledge of assembly language. That phrase is correct but absolutely useless.
Do you know how that code snipped is translated to assembly? On x86? On x64? With optimisations? Without? How different OSs would use RdRand?
That's not something that you can address with software, by definition.
Maybe there are less obvious things they can do (I'm not an expert), but isn't this what testing software like dieharder is designed to detect? I assume people are testing /dev/(u)random often.
I believe you are extrapolating the threat model past anything reasonable.
The original concern around RdRand is that the tiny on-chip random number generator might be compromised.
You are arguing that there might be implementation that uses code analysis to detect data flow from RdRand and mess with it. It sounds very far fetched.
The original concern around RdRand is that the tiny on-chip random number generator might be compromised.
You are arguing that there might be implementation that uses code analysis to detect data flow from RdRand and mess with it. It sounds very far fetched.
The file he mentions:
https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux....
Just so it's easy for everyone to find.
The title is inaccurate. It's not suspected that RdRand is compromised in the kernel, because all it does is query a hardware device for a random number. The controversy is that the devices operate on a standard originally led by someone connected to the NSA, and therefore that hardware may be compromised in some way, but as Linus says here it's not as though that number is returned directly by /dev/random. It's simply used to add further entropy into the actual random number generator.
I think he's right, for whatever that's worth.
I don't disagree with what he says. I am certain that kernel team is knowledgeable and reasonably diligent.
But I am not convinced that the Linux community has the resources and wherewithal to continuously beat state sponsored adversaries when it comes to espionage.
And the real issue is espionage not cryptography. A few billion dollars a year will buy a couple of links in the chain of trust between the kernel team and distributors and end users.
To put it another way, code breaking has been a function of the state for millennia. Computers didn't change the basic premise of doing so by hook or by crook. Algorithms are necessary but not sufficient for secure communications.
But I am not convinced that the Linux community has the resources and wherewithal to continuously beat state sponsored adversaries when it comes to espionage.
And the real issue is espionage not cryptography. A few billion dollars a year will buy a couple of links in the chain of trust between the kernel team and distributors and end users.
To put it another way, code breaking has been a function of the state for millennia. Computers didn't change the basic premise of doing so by hook or by crook. Algorithms are necessary but not sufficient for secure communications.
[deleted]
Not very friendly (well - that's relative), but it's pretty clear and provides a code reference that any developer can understand and check.
It's clear, yes, but it's also a blind assertion: we know what we're doing, you don't. He doesn't explain any of the reasoning, just that RdRand is one of many inputs. The question, and its follow up question, by Dale are reasonable. As the data is XORed after the SHA and fold operations, what's to stop the chip from having a way to predict the output?
http://dilbert.com/strips/comic/2001-10-25/
http://dilbert.com/strips/comic/2001-10-25/
I don't understand what this is supposed to mean. The chip doesn't have to "predict the output". It has the output already.
Yes, I didn't express myself clearly there.
I was thinking of how the chip's output could possibly be used to attempt to predict the output of the PRNG and so be used in something like a side-channel attack. I'm not thinking it's highly likely, but with an organization of mathematicians and code breakers like the NSA has I wondered how much an advantage that would give against random keys, key exchanges, etc.
I was thinking of how the chip's output could possibly be used to attempt to predict the output of the PRNG and so be used in something like a side-channel attack. I'm not thinking it's highly likely, but with an organization of mathematicians and code breakers like the NSA has I wondered how much an advantage that would give against random keys, key exchanges, etc.
A blind assertion? He told you which file to read in the sources. I suppose that if you say that randomization in Linux is broken reading a single .c file should'nt be a problem, and it would give all the evidence you will ever need.
they were expecting a line by line code review from torvalds. what a shame. The code is there, either propose improvement or shut up, is my philosophy.
I don't think he has to explain anything. It's clear that change.org petition was result of circle jerk that caused unnecessary confusion. Everyone is entitled to their opinion, but not everyone is entitled to professional opinion.
When I read about the issue, I was little concerned but did not follow trough. It seems that the whole issue started from people who don't know what they they are talking and who did not check facts. More and more people join and take the SOME approach of enjoying the discussion but not doing the work. This causes FUD and is bad thing. People who do this should be burned just like Linus did.
Btw. Using XOR to mix two random streams is textbook correct way to do it. It's simple and correct .
When I read about the issue, I was little concerned but did not follow trough. It seems that the whole issue started from people who don't know what they they are talking and who did not check facts. More and more people join and take the SOME approach of enjoying the discussion but not doing the work. This causes FUD and is bad thing. People who do this should be burned just like Linus did.
Btw. Using XOR to mix two random streams is textbook correct way to do it. It's simple and correct .
I would prefer a cryptographer, not Linus, to weigh in on how Linux's PRNG works and what impact RdRand would have on it. It's not that I distrust Linus, it's just that it's hard to separate the vitriol from the facts. That, and a second opinion on the matter would settle it. That'd put the FUD to rest.
However, I found this message a good explanation of what RdRand is/does and how they're integrating it with /dev/random. http://www.spinics.net/lists/linux-crypto/msg05883.html
However, I found this message a good explanation of what RdRand is/does and how they're integrating it with /dev/random. http://www.spinics.net/lists/linux-crypto/msg05883.html
If you're willing to believe Linux's PRNG is not biased in any way then you're fine, because anything ^ random -> random. That's the principle behind the one-time pads:
https://en.wikipedia.org/wiki/One-time_pad
Worst case (say, a string of 0s) you don't add any entropy to the pool. But you can't actually remove entropy with a simple xor. Again, that's assuming there are no other weaknesses in the linux PRNG.
https://en.wikipedia.org/wiki/One-time_pad
Worst case (say, a string of 0s) you don't add any entropy to the pool. But you can't actually remove entropy with a simple xor. Again, that's assuming there are no other weaknesses in the linux PRNG.
Linus was responding to totally unsubstantiated request based on wrong information.
The guy behind /dev/random is Ted Ts'o who has worked as Kerberos V5 project leader is part of security area directorate in IETF and chair of IPSec working group.
As far as I see /dev/random uses the best practices and don't innovate unnecessarily. If somebody is willing to spend time actually vetting the implementation, that would be great.
The guy behind /dev/random is Ted Ts'o who has worked as Kerberos V5 project leader is part of security area directorate in IETF and chair of IPSec working group.
As far as I see /dev/random uses the best practices and don't innovate unnecessarily. If somebody is willing to spend time actually vetting the implementation, that would be great.
Whoah whoah whoah let's not go too far here. There are things not to like about Linux devrandom. They have nothing to do with NSA backdoors, though.
By climbing on a podium with a megaphone and waving [0] for banner you effectively forfeit any expectations for being taking seriously. This is not a constructive way to solicit an action. This is your good old attention whoring as they'd say on slashdot. So he's got exactly what he deserved.
[0] http://i.imgur.com/H29TyM1.jpg
[0] http://i.imgur.com/H29TyM1.jpg
Thankfully, there is code that programmers can check on. Not sure what you're on about.
If this guy really wanted RdRand to be taken out of the kernel, he would've posted to LKML explaining his reasoning and requesting feedback. That's instead of demanding action by popular vote.
Sorry, my bad - I got the impression you were talking about Linus.
Does Dale Emmons reply make any sense? I can't imagine how you could "bias" the output of a RNG just by XORing some data in, unless the RNG is already broken. I guess you could argue that the NSA could find vulnerabilities in the stock linux RNG and then use this XOR to hide data in a side channel or something.
Sounds a bit far fetched, although I guess I can't prove him wrong. But if the stock RNG is faulty we're already quite screwed, rdrand or not.
I mean if you're willing to believe this could be compromised, why not imagine that intel inserts backdoors in the silicon of all their chips? Why trust the rest of the logic but not the random number generator specifically?
EDIT: also, the picture illustrating the petition is pretty terrible: https://www.change.org/en-GB/petitions/linus-torvalds-remove...
I can't really blame Linus for responding aggressively on that one...
Sounds a bit far fetched, although I guess I can't prove him wrong. But if the stock RNG is faulty we're already quite screwed, rdrand or not.
I mean if you're willing to believe this could be compromised, why not imagine that intel inserts backdoors in the silicon of all their chips? Why trust the rest of the logic but not the random number generator specifically?
EDIT: also, the picture illustrating the petition is pretty terrible: https://www.change.org/en-GB/petitions/linus-torvalds-remove...
I can't really blame Linus for responding aggressively on that one...
Dale's reply does make sense.
While it is true that:
<random data> ^ <compromised random data> = <random data>
If <compromised random data> has prior knowledge about <random data>, it can emit bits to bias the result.
I.e. if I know I'm going to be XORed with a 1, I can return a 1 to yield a 0.
This is entirely possible in hardware. Especially with instruction decode look-ahead.
While it is true that:
<random data> ^ <compromised random data> = <random data>
If <compromised random data> has prior knowledge about <random data>, it can emit bits to bias the result.
I.e. if I know I'm going to be XORed with a 1, I can return a 1 to yield a 0.
This is entirely possible in hardware. Especially with instruction decode look-ahead.
If the data is being supplied by an attacker that knows what it's being XORed with, which in this case it is, they can completely and undetectably control the output of the RNG that way - they simply have to XOR the output they want with the other data and return that, and then the two XORs will cancel out. (It's undetectable because so long as the output of the hardware RNG looks random, it'll still look just as random after XORing it with anything else.)
Right, but how would they know the output of the other RNG? At this point it's just a tinfoil hat theory, you might as well suspect the drivers of your ethernet card or the people who made the lock on your front door.
They'd know the output of the other RNG because our proposed attacker has the ability to embed malicious hardware and/or microcode in your CPU which can access to the full contents of RAM and all CPU registers. (It's a little harder for them to do so than to just backdoor RdRand, but there doesn't seem much point assuming an attacker can do one but not the other.)
> our proposed attacker has the ability to embed malicious hardware and/or microcode in your CPU which can access to the full contents of RAM and all CPU registers
If the threat model under which rdrand can achieve cancelling XORs is one which requires the threat to have access to RAM and CPU registers, combating it by removing rdrand is like demanding the removal of a front gate that's breakable using teleportation. If the attacker has teleportation, forget the gate, they can teleport straight into your house.
As Ted Ts'o points out elsewhere in thread, "if the microcode can figure out where the entropy pool is and figure out what it's being XOR'ed with and adjust accordingly, you're toast anyway. No matter what you can do, if the adversary has control of the cpu microcode at that level, the adversary can just modify the returned entropy value in memory".
If the threat model under which rdrand can achieve cancelling XORs is one which requires the threat to have access to RAM and CPU registers, combating it by removing rdrand is like demanding the removal of a front gate that's breakable using teleportation. If the attacker has teleportation, forget the gate, they can teleport straight into your house.
As Ted Ts'o points out elsewhere in thread, "if the microcode can figure out where the entropy pool is and figure out what it's being XOR'ed with and adjust accordingly, you're toast anyway. No matter what you can do, if the adversary has control of the cpu microcode at that level, the adversary can just modify the returned entropy value in memory".
I would be amused to know how many of those people screaming outrage at rdrand run proprietary video driver blobs or use other closed source operating systems.
Priorities, people, priorities.
Priorities, people, priorities.
Wow, the comments in this thread sure are disappointing. Oh my, Linus is blunt, who would have thought! I wish people were over that years ago.
Look - in coding, there is code. Linus has his code in the open. This petition should not have been started to begin with, instead, they should have checked the code.
I'm not taking sides here because my C-fu is non-existent, so I don't feel qualified to comment on that part itself. But if you make a petition, you sure as hell make sure that it cannot be easily negated with a RTFC.
He is right to be annoyed by it and more than right to publicly voice that. He is managing one of the (if not THE) largest FOSS project there is. Just imagine how well you would handle if people kept giving you crap like this day in day out. Yeah, you sure would be honeycombs and flowers to everybody. Right.
Look - in coding, there is code. Linus has his code in the open. This petition should not have been started to begin with, instead, they should have checked the code.
I'm not taking sides here because my C-fu is non-existent, so I don't feel qualified to comment on that part itself. But if you make a petition, you sure as hell make sure that it cannot be easily negated with a RTFC.
He is right to be annoyed by it and more than right to publicly voice that. He is managing one of the (if not THE) largest FOSS project there is. Just imagine how well you would handle if people kept giving you crap like this day in day out. Yeah, you sure would be honeycombs and flowers to everybody. Right.
[deleted]
Man... this is the kind of arrogant response that put me off from linux sometimes (and I am writing this from an Ubuntu box). Is there not any other way (less insulting and more pedagogic) to respond that petition?
You don't prove the security of your algorithm by saying trust me. You don't even prove the security of an algorithm by publishing the implementation ("read the code fool!") that's not how security researchers convince their peers or the public. Should Bernstein just publish a cipher or PRNG as C code and just tell people to trust him?
If Linus wanted to convince people, he could point to either a design document that puts forward the reasoning behind the choices made in the implementation, or a security analysis done by researchers on the actual implementation. Linus is not a cryptographer or expert in that field, despite his accolades in others. The history of cryptographic implementations, even by experts in the field who have years of experience in cryptanalysis, is that they make mistakes, both in implementation and design, and the NSA presumably is top-notch at exploiting weaknesses.
I just don't understand why Linus has to act like this. He could choose to either not respond at all (which is probably what he should have done with respect to this petition), or he could have pointed to a previous discussion on the algorithm used, or let one of the other experts who did an analysis comment.
There is nothing to be won by being not only a jerk about it, but making what is perhaps, too strong an assertion about the security of it. Prominent cryptographers in the field have had their algorithms and protocols broken by others, and not even giving any consideration to conditional security seems unwise.
Far from convincing me, Linus's assertions have me wary of possible overconfidence. What would lend confidence for me would be an actual academic paper analyzing it, one that is peer reviewed by others in the field.
If Linus wanted to convince people, he could point to either a design document that puts forward the reasoning behind the choices made in the implementation, or a security analysis done by researchers on the actual implementation. Linus is not a cryptographer or expert in that field, despite his accolades in others. The history of cryptographic implementations, even by experts in the field who have years of experience in cryptanalysis, is that they make mistakes, both in implementation and design, and the NSA presumably is top-notch at exploiting weaknesses.
I just don't understand why Linus has to act like this. He could choose to either not respond at all (which is probably what he should have done with respect to this petition), or he could have pointed to a previous discussion on the algorithm used, or let one of the other experts who did an analysis comment.
There is nothing to be won by being not only a jerk about it, but making what is perhaps, too strong an assertion about the security of it. Prominent cryptographers in the field have had their algorithms and protocols broken by others, and not even giving any consideration to conditional security seems unwise.
Far from convincing me, Linus's assertions have me wary of possible overconfidence. What would lend confidence for me would be an actual academic paper analyzing it, one that is peer reviewed by others in the field.
The third comment (on the article) is interesting. In theory, a 'XOR' among sources of data is 'secure' if any one of them is truly random.
Let's look at this further. Imagine you have a stream of entropy, and then you xor it with a second stream. The first stream is secure (truly random) but the second stream is defective: it's all 1's.
Question: Do you now have a random stream, or is it biased towards 0's or 1's or in any other way?
Answer: If they're independent it's secure. Let's see why. In fact, you can consider the correct (random) stream as being a OTP on the plaintext which is all the rest. In this case the 'rest' is all 1's, but it could be something partially random. So, any random-enough source acts like an OTP on the final output - Except you throw away the key.
Naturally, as OTP's are secure, the resulting 'ciphertext' (looking at it as though it were an OTP operation) does not exhibit any evidence of the 'all 1's plaintext that you "applied" it to. It doesn't matter what order you do the XOR's, or how many are secure (random enough) and how many are insecure.[1] So, if you have 27 sources of entropy you XOR by, then if any one of them are 'random enough' then the output is 'random enough'.
There's just one problem: your output could be LESS random if the 'random enough' "key" could somehow be recovered. For example, if instead of all 1's, for our second stream we XOR'd by a mirror of the first (otherwise secure) stream, then our results will be all 0: a horribly biased RNG.
So, if any of the 27 (or however many) sources 'know' about the most random source, they can 'undo' the entropy that is being added, and add hteir own. so you might be XORing with a copy of the 'random enough' source, netting all 0's, and also xoring by the output of an encrypted output of an iterated counter, encrypted with, e.g. the NSA's private key:
then to anyone that didn't have the NSA's private key it would look like the stream was still random enough. But in fact, the entropy added by one source is removed in another.
The correct way around this is for hte sources to not have enough information about each other to be able to 'leak' keys this way (undo entropy).
So the third comment on the article is very interesting in this light.
[1] XOR is commutative so you can rearrange the expression this way for any number of sources of entropy; it doesn't matter which one is secure: e.g. if D is secure in A XOR B XOR C XOR D XOR E XOR F, the output is still the same as (A XOR B XOR C XOR E XOR F) XOR D (by the commutative property) and therefore secure.
Let's look at this further. Imagine you have a stream of entropy, and then you xor it with a second stream. The first stream is secure (truly random) but the second stream is defective: it's all 1's.
Question: Do you now have a random stream, or is it biased towards 0's or 1's or in any other way?
Answer: If they're independent it's secure. Let's see why. In fact, you can consider the correct (random) stream as being a OTP on the plaintext which is all the rest. In this case the 'rest' is all 1's, but it could be something partially random. So, any random-enough source acts like an OTP on the final output - Except you throw away the key.
Naturally, as OTP's are secure, the resulting 'ciphertext' (looking at it as though it were an OTP operation) does not exhibit any evidence of the 'all 1's plaintext that you "applied" it to. It doesn't matter what order you do the XOR's, or how many are secure (random enough) and how many are insecure.[1] So, if you have 27 sources of entropy you XOR by, then if any one of them are 'random enough' then the output is 'random enough'.
There's just one problem: your output could be LESS random if the 'random enough' "key" could somehow be recovered. For example, if instead of all 1's, for our second stream we XOR'd by a mirror of the first (otherwise secure) stream, then our results will be all 0: a horribly biased RNG.
So, if any of the 27 (or however many) sources 'know' about the most random source, they can 'undo' the entropy that is being added, and add hteir own. so you might be XORing with a copy of the 'random enough' source, netting all 0's, and also xoring by the output of an encrypted output of an iterated counter, encrypted with, e.g. the NSA's private key:
then to anyone that didn't have the NSA's private key it would look like the stream was still random enough. But in fact, the entropy added by one source is removed in another.
The correct way around this is for hte sources to not have enough information about each other to be able to 'leak' keys this way (undo entropy).
So the third comment on the article is very interesting in this light.
[1] XOR is commutative so you can rearrange the expression this way for any number of sources of entropy; it doesn't matter which one is secure: e.g. if D is secure in A XOR B XOR C XOR D XOR E XOR F, the output is still the same as (A XOR B XOR C XOR E XOR F) XOR D (by the commutative property) and therefore secure.
Ever so pleasant, Linus does nothing to explain to luddites why they should use Linux.
People who are concerned about cryptographic security should try learning about cryptographic security, seeing as the current debacle is all about who you should trust to provide cryptographic security solutions.
Why should he? I'm not a massive fan of his outbursts and profanity, but he's head of the kernel, something which 'luddites' don't necessarily need to know about. It's very unlikely they'd be reading these distribution lists (or even know what a distribution list is). The explanation is more the job of the distro maintainers than the kernel maintainers, I would think.
Well, may be the RdRand hardware has microcode reading the memory and inferring the PRNG state. Then what?
Like people has already said, if the silicon is compromised, you are sold.
Like people has already said, if the silicon is compromised, you are sold.
Oh, this is rich.
I bet everything I own, most of these idiots taking Linus to the fire use proprietary software and have mocked RMS for years.
"But you can't trust code because Ken Thompson says so!" Really, dipshit? You don't think every compiler writer and OS developer knows about Thompson's essay by now? Did everyone seriously just discover this ancient essay?
Amazingly, the peanut gallery--on a dime--has gone from trusting proprietary software to scrutinizing open source code.
I bet everything I own, most of these idiots taking Linus to the fire use proprietary software and have mocked RMS for years.
"But you can't trust code because Ken Thompson says so!" Really, dipshit? You don't think every compiler writer and OS developer knows about Thompson's essay by now? Did everyone seriously just discover this ancient essay?
Amazingly, the peanut gallery--on a dime--has gone from trusting proprietary software to scrutinizing open source code.
This just leads to a redirect loop for me, probably because they rely on cookies. Anyone got a plain link to the text?
http://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.g...
i.e. the output is XORed with the bits being returned. (Note that the output of RdRand is not added to the entropy pool itself; it's used to modify the value being returned via an XOR).
This seems reasonable given that the intent is to XOR together two random streams.
And if RdRand is known to NSA then NSA can do the XOR and get back to what would have been returned if RdRand wasn't there. Thus if NSA knows all about RdRand then the effect would be to downgrade the random number generator to the situation before RdRand was used at all. This doesn't seem to provide much vector for an attack on Linux's random number generation, it would just make RdRand useless.
Of course, if RdRand is the only thing you trust...
PS Linus' reply is disappointing, however, because it doesn't explain the situation.