9 ms·

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

75 points by quchen 13y ago

quchen 13y 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.
- trebor 13y 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/ http://dilbert.com/strips/comic/2001-10-25/
  - hannibal5 13y 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 .
    - trebor 13y ago
      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 http://www.spinics.net/lists/linux-crypto/msg05883.html
      - simias 13y ago
        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 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.
      - hannibal5 13y ago
        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.
        tptacek 13y ago
        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.
  - tptacek 13y 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.
    - trebor 13y ago
      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.
  - riquito 13y 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.
    - meapix 13y ago
      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.
Zikes 13y 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.
raverbashing 13y 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.
- devx 13y 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 13y 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.
  - derefr 13y 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 13y ago
Previous discussion: https://news.ycombinator.com/item?id=6358550 https://news.ycombinator.com/item?id=6358550 (Not sure why the link was deleted from HN?)
- h2s 13y 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.
tlb 13y 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 13y ago
  That's not something that you can address with software, by definition.
- plorkyeran 13y ago
  If the CPU is compromised then you've already lost.
  - deleted 13y ago
    [deleted]
  - tlb 13y 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.
    - jerf 13y ago
      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.
    - tptacek 13y ago
      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?
brudgers 13y 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 http://cm.bell-labs.com/who/ken/trust.html
- batbomb 13y 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 13y 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.
  - brudgers 13y 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 13y 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.
simias 13y 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-rdrand-from-dev-random-4 https://www.change.org/en-GB/petitions/linus-torvalds-remove... I can't really blame Linus for responding aggressively on that one...
- makomk 13y 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 13y ago
    You realize that your attack is predicated on the non-hardware RNG already being broken, right?
    - btilly 13y ago
      Not true. If we're going to put on a tinfoil hat, the hardware RNG only needs to be able to have access to memory to figure out where it is likely to be used.
      - deleted 13y ago
        [deleted]
jgrahamc 13y 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.git/tree/drivers/char/random.c#n948 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 13y 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.
  - tptacek 13y 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.
    - jgrahamc 13y ago
      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; [...] There's one interesting use of this in the Linux kernel: the output is used for randomization of the address space. So, I suppose we could say that if NSA can predict RdRand then they can predict memory layout and which might enable some sorts of interesting attacks.
tptacek 13y ago
I think he's right, for whatever that's worth.
- deleted 13y ago
  [deleted]
- brudgers 13y 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 13y 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.
- simias 13y 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 13y 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.
- makomk 13y 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 13y ago
xutopia 13y ago
Ever so pleasant, Linus does nothing to explain to luddites why they should use Linux.
- lewispollard 13y 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 13y 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 13y 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 13y ago
  Linus never fails to be a complete ass.
- meapix 13y ago
  he doesn't give a shit. You should look at the video where he gave finger to nvidea.
mcosta 13y 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 13y ago
The file he mentions: https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/plain/drivers/char/random.c?id=refs/tags/v3.11 https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.... Just so it's easy for everyone to find.
alextingle 13y ago
This just leads to a redirect loop for me, probably because they rely on cookies. Anyone got a plain link to the text?
huhtenberg 13y 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 http://i.imgur.com/H29TyM1.jpg
- skore 13y ago
  Thankfully, there is code that programmers can check on. Not sure what you're on about.
  - huhtenberg 13y 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.
    - skore 13y ago
      Sorry, my bad - I got the impression you were talking about Linus.
skore 13y 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.
- deleted 13y ago
  [deleted]
tytso 13y ago
I thought of this issue over a year ago. See: http://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/commit/?id=c2557a303ab6712bb6e09447df828c557c710ac9 http://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.g... https://plus.google.com/117091380454742934025/posts/SDcoemc9V3J https://plus.google.com/117091380454742934025/posts/SDcoemc9...
- btilly 13y 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.
  - tytso 13y 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.
    - btilly 13y ago
      The concern is not that Intel wouldn't notice it. The concern is that Intel is complicit in the attack.
cromwellian 13y 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 13y 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.

75 points by quchen 13y 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.

trebor 13y 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/ http://dilbert.com/strips/comic/2001-10-25/
- hannibal5 13y 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 .
  - trebor 13y ago
    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 http://www.spinics.net/lists/linux-crypto/msg05883.html
    - simias 13y ago
      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 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.
    - hannibal5 13y ago
      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.
      - tptacek 13y ago
        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.
- tptacek 13y 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.
  - trebor 13y ago
    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.
- riquito 13y 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.
  - meapix 13y ago
    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.

Zikes 13y 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.

raverbashing 13y 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.

devx 13y 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 13y 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.
- derefr 13y 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 13y ago

Previous discussion: https://news.ycombinator.com/item?id=6358550 https://news.ycombinator.com/item?id=6358550 (Not sure why the link was deleted from HN?)

h2s 13y 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.

tlb 13y 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 13y ago
That's not something that you can address with software, by definition.
plorkyeran 13y ago
If the CPU is compromised then you've already lost.
- deleted 13y ago
  [deleted]
- tlb 13y 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.
  - jerf 13y ago
    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.
  - tptacek 13y ago
    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?

brudgers 13y 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 http://cm.bell-labs.com/who/ken/trust.html

batbomb 13y 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 13y 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.
- brudgers 13y 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 13y 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.

simias 13y 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-rdrand-from-dev-random-4 https://www.change.org/en-GB/petitions/linus-torvalds-remove... I can't really blame Linus for responding aggressively on that one...

makomk 13y 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 13y ago
  You realize that your attack is predicated on the non-hardware RNG already being broken, right?
  - btilly 13y ago
    Not true. If we're going to put on a tinfoil hat, the hardware RNG only needs to be able to have access to memory to figure out where it is likely to be used.
    - deleted 13y ago
      [deleted]

jgrahamc 13y 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.git/tree/drivers/char/random.c#n948 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 13y 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.
- tptacek 13y 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.
  - jgrahamc 13y ago
    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; [...] There's one interesting use of this in the Linux kernel: the output is used for randomization of the address space. So, I suppose we could say that if NSA can predict RdRand then they can predict memory layout and which might enable some sorts of interesting attacks.

tptacek 13y ago

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

deleted 13y ago
[deleted]
brudgers 13y 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 13y 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.

simias 13y 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 13y 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.
makomk 13y 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 13y ago

xutopia 13y ago

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

lewispollard 13y 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 13y 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 13y 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 13y ago
Linus never fails to be a complete ass.
meapix 13y ago
he doesn't give a shit. You should look at the video where he gave finger to nvidea.

mcosta 13y 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 13y ago

The file he mentions: https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/plain/drivers/char/random.c?id=refs/tags/v3.11 https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.... Just so it's easy for everyone to find.

alextingle 13y ago

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

huhtenberg 13y 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 http://i.imgur.com/H29TyM1.jpg

skore 13y ago
Thankfully, there is code that programmers can check on. Not sure what you're on about.
- huhtenberg 13y 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.
  - skore 13y ago
    Sorry, my bad - I got the impression you were talking about Linus.

skore 13y 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.

deleted 13y ago
[deleted]

tytso 13y ago

I thought of this issue over a year ago. See: http://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/commit/?id=c2557a303ab6712bb6e09447df828c557c710ac9 http://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.g... https://plus.google.com/117091380454742934025/posts/SDcoemc9V3J https://plus.google.com/117091380454742934025/posts/SDcoemc9...

btilly 13y 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.
- tytso 13y 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.
  - btilly 13y ago
    The concern is not that Intel wouldn't notice it. The concern is that Intel is complicit in the attack.

cromwellian 13y 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 13y 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.