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

by quchen • 13 years ago

75 106 13 years ago

quchen• 13 years ago

Not very friendly (well - that's relative), but it's pretty clear and provides a code reference that any developer can understand and check.

trebor3• 13 years ago

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/

hannibal53• 13 years ago

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 .

tptacek6• 13 years ago

I don't understand what this is supposed to mean. The chip doesn't have to "predict the output". It has the output already.

riquito• 13 years ago

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.

Zikes• 13 years ago

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.

raverbashing4• 13 years ago

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.

devx2• 13 years ago

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.

quaunaut• 13 years ago

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.

derefr2• 13 years ago

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.

scrrr• 13 years ago

Previous discussion: https://news.ycombinator.com/item?id=6358550

(Not sure why the link was deleted from HN?)

h2s• 13 years ago

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.

tlb3• 13 years ago

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.

cliveowen• 13 years ago

That's not something that you can address with software, by definition.

plorkyeran• 13 years ago

If the CPU is compromised then you've already lost.

tlb3• 13 years ago

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.

devx2• 13 years ago

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.

bcoates• 13 years ago

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...

raverbashing4• 13 years ago

"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.

reitzensteinm• 13 years ago

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.

m_ram• 13 years ago

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.

hannibal53• 13 years ago

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.

brudgers3• 13 years ago

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

batbomb• 13 years ago

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)

betterunix• 13 years ago

"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.

brudgers3• 13 years ago

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.

logicallee• 13 years ago

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.

simias6• 13 years ago

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...

makomk4• 13 years ago

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.)

defen• 13 years ago

You realize that your attack is predicated on the non-hardware RNG already being broken, right?

simias6• 13 years ago

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.

optimiz32• 13 years ago

Dale's reply does make sense.

While it is true that:

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.

jgrahamc4• 13 years ago

Suppose for the moment that the output of RdRand is known at all times to the NSA. In the relevant Linux code it is mixed in as follows:

     /*
      * 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;
     }

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.

marvin• 13 years ago

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.

tptacek6• 13 years ago

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.

unwind• 13 years ago

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....

btilly6• 13 years ago

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.

jgrahamc4• 13 years ago

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.

optimiz32• 13 years ago

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.

tedunangst• 13 years ago

Backdooring the XOR instruction would be far more useful.

tptacek6• 13 years ago

I think he's right, for whatever that's worth.

brudgers3• 13 years ago

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.

mrcwinn• 13 years ago

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.

simias6• 13 years ago

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.

jeswin• 13 years ago

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.

makomk4• 13 years ago

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.

harshreality• 13 years ago

Which older versions and which distro's current kernels? This is easily verifiable. Name them, or don't make such claims.

tspiteri• 13 years ago

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.

gpvos• 13 years ago

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.

kevinmchugh• 13 years ago

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?

mbesto• 13 years ago

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-...

Dewie• 13 years ago

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.

lotsofcows• 13 years ago

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.

sanskritabelt• 13 years ago

"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.

xutopia• 13 years ago

Ever so pleasant, Linus does nothing to explain to luddites why they should use Linux.

lewispollard• 13 years ago

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.

XorNot• 13 years ago

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.

pmelendez• 13 years ago

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?

KeyBoardG• 13 years ago

Linus never fails to be a complete ass.

meapix2• 13 years ago

he doesn't give a shit. You should look at the video where he gave finger to nvidea.

mcosta• 13 years ago

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.

testrecord• 13 years ago

The file he mentions: https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.... Just so it's easy for everyone to find.

alextingle• 13 years ago

This just leads to a redirect loop for me, probably because they rely on cookies. Anyone got a plain link to the text?

huhtenberg2• 13 years ago

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

skore3• 13 years ago

Thankfully, there is code that programmers can check on. Not sure what you're on about.

huhtenberg2• 13 years ago

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.

skore3• 13 years ago

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.

tytso3• 13 years ago

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...

btilly6• 13 years ago

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.

tytso3• 13 years ago

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.

cromwellian• 13 years ago

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.

aryastark• 13 years ago

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.

Torvalds' response to whether RdRand could be compromised in the Linux kernel

Related Stories