Torvalds' response to whether RdRand could be compromised in the Linux kernel
change.org
change.org
/*
* If we have a architectural hardware random number
* generator, mix that in, too.
*/
for (i = 0; i < LONGS(EXTRACT_SIZE); i++) {
unsigned long v;
if (!arch_get_random_long(&v))
break;
hash.l[i] ^= v;
}
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.
/*
* 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;
[...]
But will owning RdRand give you good enough control over ASLR, that's another question.
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.
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.
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.
> (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.
The relevant code is here: http://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.g....
/*
* 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)But it would need to be actively aware of what is where in memory to do this.
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.
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.
That's sort of my point. "Push comes to shove" -> they'll do the easy thing first.
If their goal is to target Linux, and they know what Linux code looks like, why not take it one step farther?
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.
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.
They have? I thought they were still regularly fought and ignored by the rest of the crypto community.
- 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.
Not a chance.
http://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.g...
https://plus.google.com/117091380454742934025/posts/SDcoemc9...
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.
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.
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 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.
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-...
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.
Don't worry about it, he'll solve that problem all by himself.
Ken Thompson described it as "Trusting Trust."
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.
Solipsism is a solution that in the end requires making your own CPU.
(Not sure why the link was deleted from HN?)
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.
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.
Of course, this would prevent you from using RdRand as your VM implementation will only be able to call on deterministic instructions...
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.
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.
XOR is used for entropy calculation in the Linux kernel, as Dale Emmons points out in the article.
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?
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.
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.
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 .
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
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.
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.
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.
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...
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".
Priorities, people, priorities.
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.
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.
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.
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.
Like people has already said, if the silicon is compromised, you are sold.
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.