6 ms·
Linus on /dev/random: "We actually know what we are doing. You don't."
- yeukhon 13y agoI'd want to hear Linus responding to both the OP and Taylor. But quick thought: do people like Bruce Schneier ever read this file? I think in the next year or two we will see a huge number of research going into finding "backdoor", suggesting implementation weaknesses. I am not going to speculate too much about who is NSA mole or why certain code got into the codebase. I'm more interested in researchers to find more weaknesses, like how Barton Miller did by fuzzing unix programs back in the 90s! I wish I had enough knowledge to help out.
- antocv 13y agoBruce Schneier I have all the respect for the guy, really, but then I read his guardian article "how to keep your data safe and secure" and mentions keeping "air gap" between computers with sensitive data but then he himself admits after all his methods and safeguards for the leaks he is working with, he uses Windows and usb-sticks to transfer (encrypted) files between them. He uses Windows. He uses Windows. And he was claiming in the article that free and open source are better for security. Oh really, so your encrypted files on your usb-sticks for sure cant spread malware through your airgap through a file-system exploit? For sure it has never been done before that a file system could be used to take over an OSs internals, oh never.
- icecreampain 13y agoUsing [only] Windows should automatically disqualify one from giving and security related advice. At least Linux and BSD source is viewable by people. Lots of people.
- anon1385 13y agoThe same lots of people that immediately noticed when Debian shipped a broken openssl? Or the ones that didn't notice at all for years until somebody noticed identical certs showing up in the wild? https://en.wikipedia.org/wiki/Random_number_generator_attack#Debian_OpenSSL https://en.wikipedia.org/wiki/Random_number_generator_attack...
- jamesrom 13y agoIt's still good advice. In fact, unless you audit the source of your OS, it's compiler, hardware and any software you need to use you can't really make any guarantees either.
- antocv 13y agoI can make you the guarantee that Microsoft is actively cooperating with the NSA and has backdoors in Windows. I can guarantee you that few people have access to the Windows source to check it. I can also guarantee you that many more people have access and have audited the source code of a GNU/Linux system. I cant guarantee you that GNU/Linux doesnt have backdoors. But for all intents and purposes it is just plain Wrong to use windows for any security related activities. Would you be more comfortable leaking documents using a GNU/Linux livecd or Windows?
- yeukhon 13y agoSorry. I think you are too paranoid. You are. Close source can have backdoor and open source can have backdoor too. I like to use Linux and my Mac to do programming work, but it doesn't mean I don't care about Windows. If you think Linux has less chance getting backdoor, well, look at all the speculation we got these days. If NSIT cryptographic standard has reduced security as many people believe, then your communicate is dead. If you believe that all ISP are cooperating with the US government here in the US, why the hell are you still using the Internet as we know it? You are guaranteeing that only an open source system will not have a backdoor while a closed source must have. Microsoft has collaboration with NSA in one way or another. Is that a secret? Most of their "collaboration" probably come from business things like military-kind projects. They might have backdoor. But guarantee is a big assumption. If you don't have solid proof then you are making false accusation. It's like saying because your friend shakes hands and hang out with a cold-blood murder he must be a cold-blooded person too. Plain wrong, ignorant and simply stupid. Security has a trust involved. If you don't trust your USB, your own product, then you will not get any security. There is nothing wrong with transferring things between usb and windows computer. It's fine. You can still run SCP, SSH over your Windows socket. Is that now weaker because damn MS is working with NSA as you say? Someone give this man a cookie because we are obviously living in an fantasy. If you think your ipod, your laptop don't have backdoor according to how MS and Intel are working with NSA, you are contradicting. Stop using the Internet and stop using anything. Then you are safe.
- willvarfar 13y agoI think you are throwing the baby out with the bath water here. Bruce Schneier can be presumed to have evaluated his risks; he's a very well known author on exactly that.
- georgemcbay 13y agoI never followed this at all prior to reading this article so forgive me if this was covered outside the scope of this write-up, but... If the CPU did give you a RDRAND value that was pre-baked to weaken the number it thinks you're going to XOR it against it, it would be easy to detect this by feeding RDRAND the same input state repeatedly and seeing if there is a pattern to what is spit out or if it is indeed statistically random... So why hasn't someone (who thinks RDRAND is a trap) done that instead of just claiming it could maybe be doing something fishy?
- ygra 13y agoHow would you distinguish actual randomness from the output of a CSPRNG with a known or weak seed? Patterns won't be apparent in either output.
- georgemcbay 13y agoThe gist of the argument as I understand it is that some people think Intel's chip (at the chip level) is taking a look at data that the RDRAND result will be used as an XOR against and using that to mess with the result RDRAND returns in some way to weaken the overall random number. If this were true and you set up a repeatable test situation in which you force the other parts of the RNG to generate the same numbers prior to RDRAND and then did the RDRAND and captured the results then I don't see how one could argue RDRAND is compromised in this way if the results coming out of it over time even appear to be statistically random. ...unless people think the chip is also detecting situations where you are actively trying to fool it by setting up repeated simulations of the same initial value to be XORed, which strains credibility way beyond what I'm willing to believe.
- Perseids 13y agoActually that is quite simple. For simplicity let us assume RDRAND will only attack the Linux RNG. Now RDRAND first generates its own weak random stream w_k. When it predicts that Linux will generate l_k it outputs l_k xor w_k thus the final output of the Linux RNG will be w_k. As w_k looks random for everyone who does not have the private key you cannot check that there is anything wrong with w_k or w_k xor l_k.
- deleted 13y ago[deleted]
- simias 13y agoWe allow the wild web to have access to our closed source GPU driver blobs but we elaborate tinfoil hat theories about rdrand. This is insane. Regarding "(I'm not sure I agree with Linus that mixing in a known-tainted RDRAND stream would nevertheless invariably improve randomness, but on the surface, it shouldn't reduce it.)": I think it's fair to say it would, in practice. Even if the NSA knows how to predict the output of rdrand (because it's really some stream cipher with a known key or something), most people don't. Therefore, it wouldn't improve the randomness of the final stream from the NSA point of view, but it would from the point of view of any other attacker not in the secret. So I think it's fair to say it can't do harm and it can actually do some good. See also the previous discussion: https://news.ycombinator.com/item?id=6359892 https://news.ycombinator.com/item?id=6359892 The consensus seems to be that if the NSA can backdoor rdrand so deeply that it can keep track of the CPU state and the contents of the RAM then you might as well throw away the whole CPU, why would you choose to trust all instructions but rdrand? They could have compromised the interrupt vector, the syscall vector or anything else. This feels like "rumor based cryptography" or more precisely "FUD based cryptography". We're just running in circles.
- einhverfr 13y agoThis is true. I think it is unlikely that rdrand is this deeply backdoored. However, I do think for something this critical the comments should match the code better and working on fixing the problems identified in the article is probably prudent. It is worth noting that police used to be able to exploit firewire DMA to bypass disk encryption and copy encryption keys out of memory from any system with a firewire port. This has been fixed and a CPU-level exploit for crypto seems unlikely to me because making something that not only worked consistently but didn't slow down general purpose programming when it worked, would be an engineering marvel. This being said, having clear, unimpeachable code in these areas is a good start because it helps ensure that other problems are not lurking under the surface.
- simias 13y agoI agree that the comment of get_random_bytes should be fixed, it's misleading. However I don't think modifying code that has no known bug or weakness because of a rumor and some handwaving is good policy. It's more likely than not to introduce a regression and create real trouble. If it's ain't broke... Or in this case: If you can't prove it's broke... EDIT: I would also remind everybody that if they really don't trust rdrand for any reason they can just add the "nordrand" boot kernel param and disable this code. It's a non-issue.
- icecreampain 13y agoIf you consider the title of the article, "Rudest man in Linuxdom", you understand very quickly that the article author is imposing their own moral on Linus, but that's OK because the author is a proven programming genius of greater skill than the person who invented Linux, git, etc. ... Oh wait, he isn't. The author of the article is just another "tech blogger" that is interested in page views. So what's more interesting an article to write: one about RDRAND, or one about how mean, naughty and rude that ignorant "Linus Torvalds" person is? The second option will generate more page views so the choice is obvious. Since the author of the article is quick to criticize Linus and his way of expressing himself, even going so far as to, in a bullet list, sentence Linus to community service for the crime of not being as kind, understanding and tolerant a person as the author, I'm going to do the same. Hey, article author! If I were king, here's what I would want you to do: * Write an operating system that is used by millions of people and powers a large part of the Internet (together with BSD and friends). * Write a distributed CVS that is also used by millions of people. * Stop writing bullet lists about people. * Stop trying to attract hits to your tech blog and create something of use to the human species. How about rewriting the graphics support in the kernel or something? * Criticize what people say, not how they say it. I'm tempted to go on, but I know that the author has no interest in neither learning nor creating anything, only criticizing other people, so anything I write is for the enjoyment of HN (in addition to mine).
- hrjet 13y agoRegardless of how the author has presented his arguments, why don't _we_ focus on the actual arguments? This is getting rather too meta. Also, what's the use of an open-source OS that is used by millions if it is shrouded in esoteric arguments? I would certainly like Linux developers to better express themselves even if _I_ can't build such a system myself.
- iSnow 13y ago>The author of the article is just another "tech blogger" So ridiculing him instead attacking his arguments is A-OK but he has to keep silent because Thorwalds is a great coder?
- zamalek 13y ago
- tspiteri 13y agoPlease do not submit professional troll articles.
- zamalek 13y agoAgreed. This article is very one-sided, and after posting a calmly worded comment regarding Linus's standpoint[1] on his attitude, it was deleted. The article is simply link bait and is not professional journalism. That being said, I have more confidence in Linus's knowledge regarding /dev/random. Mostly because XOR in this context is secure: 1. XOR is an incredibly powerful encryption algorithm (not primitive); one of the best we have. The problem with XOR is that you MUST use a UNIQUE one time pad (that is the length of the data) for every message AND you need to be able to securely transmit that one time pad. AES CTR is effectively using AES to create a one time pad for XOR encryption, as an example. 2. The prior steps are effectively creating a irrecoverable OTP meaning that any malicious intent in RRAND is effectively encrypted away. [1]: http://marc.info/?l=linux-kernel&m=137391223711946&w=2 http://marc.info/?l=linux-kernel&m=137391223711946&w=2
- solarexplorer 13y agoThe argument is that RDRAND may have access to the previously generated OTP. If that is true, a malicious RDRAND can cancel out any randomness from that OTP. In that case the "incredibly powerful encryption algorithm" XOR can be tricked to generate a stream of zeros, shakespeares complete works, or whatever you like.
- XorNot 13y agoWho the christ is feeding the output of /dev/random for its use as a cryptographic function without checking that what they read is in fact NOT just a stream of zeroes? Because that's an outcome which can happen from any truly random number generator just by chance - its unlikely, but not unreasonable. Hence debiasing and the like.
- Peaker 13y ago
- shin_lao 13y agoIt could be summed up as is: either you have a test that shows that rdrand has got problematic behavior or you shut up. Backdooring rdrand is of little to no interest given how PRNGs are built.
- Perseids 13y agoI would agree with you if the Linux RNG was build according to common cryptographic wisdom. But as far as I can tell by reading the article the random sources are compressed in a common randomness pool using CRC. If RDRAND was added to this pool it might reduce the randomness of this pool. If these sources were added by a cryptographically secure mixing primitive this would not be possible. A faster alternative would be to maintain one pool for every randomness source that is added to via CRC and then only mix all pools together with a cryptographically secure primitive when randomness is requested.
- jpalomaki 13y agoIf I remember right, the original reasoning why this could be a problem was something along the lines: You are using sources s1, s2, s3. Then final result is combination c(s1,s2,s3). Now somebody screws up something and the sources s1 and s2 start returning just constant values. If you were just using s1 and s2 you would immediately notice this. However since you are combining all three, you are getting something that looks good but what might not be really secure if the source s3 is compromised. (I think this came up in some HN discussion some weeks ago) I'm not familiar with the Linux implementation so I don't know if this has any meaning there.
- CJefferson 13y agoThe problem with this argument is that it would also apply to any low quality random source, and linux (and other OSes) all use sources of dubious quality. The reason to use them is that when we mix, they only improve matters.
- jacquesm 13y agoThis whole discussion about rdrand reminds me of people arguing about what strength the secondary lock on their upstairs back window should be when the downstairs floor has single pane glass windows all around. Even if rdrand is backdoored it would have to be a significant supplier of entropy in the resulting random number for this to be a meaningful attack vector, as soon as you mix it with other (good enough, large enough) sources of entropy you get a situation where some other attack is more likely to be far more feasible than to use the knowledge about some of the bits that rdrand contributes to the entropy pool. Such as: - good old b&e and placing a keylogger or hardware bug (very easy to hide in a keyboard) - a compromised bit of the OS - compromising the application that you use to encrypt your messages or finding a significant weakness in the application. - doing any of the above with the recipient
- makomk 13y agoDid you actually look at how the Linux kernel is mixing RDRAND output with other randomness, or read the comments by the author of the original change.org petition? Because of the way Linux mixes RDRAND output with other entropy using XOR, a malicious RDRAND implementation can easily make the output of /dev/random totally determinisitc whilst being completely indistinguishable from a correctly-functioning implementation except to the attacker. All it has to do is detect the code sequence in question and XOR the output of RDRAND with the randomness from the other entropy sources before returning it. The two XORs cancel out, and this is completely undetectable because there's no way to distinguish between a true random bitstream, a good PRNG, and a good PRNG XORed with data you provided based on the bits themselves.
- jeswin 13y agoInstead of discussing on LKML or other forums, he decides to create a petition on change.org. Got what it deserved. Somebody should be apologizing here, and it isn't Linus.
- willvarfar 13y agoIf you think RDRAND is examining the L1 and registers in order to derandomise it, why wouldn't the evil chip just skip bothering with RDRAND and instead just attack that random buffer it knows how to find...?
- makomk 13y agoMucking with RDRAND can easily be done in such a way that it's provably impossible to detect any differences in behaviour. It's much harder to guarantee that if you start mucking with buffers in memory, since there are so many clever ways a developer could check their work and catch you out.
- willvarfar 13y agoHow's the provably impossible to detect bit work again? Surely it'd fail a Chi Square test on reruns with the same input? The attack can't use external input e.g. clock because the NSA can't correlate generating the random number with seeing it in flight.
- Perseids 13y agoWhy should the CPU not have an internal counter that is backed up in flash memory between reboots? 128bit would be enough, with the highest bits set to the processor serial number. Using this counter in AES-CTR mode – i.e. encrypt the counter with the secret key to generate the pseudo random data – the NSA could reconstruct the internal CPU state from a single block (16 bytes) of random data. As many random data is published verbatim, for example as nonces, getting such a block should not be a problem.
- makomk 13y agoYeah, or if the onboard flash memory is too difficult to implement, they could even just initialise the lower bits of the counter from the real hardware RNG every boot. Either of these options would be statistically indistinguishable from true randomness unless you knew the key.
- mbq 13y agoWhen I first learned about RDRAND I was thrilled because I naively assumed this would be just a hardware RNG with direct link to the CPU register vector capable of delivering randomness with a speed of cache hits or better. This would be an end to all struggles with non-crypto PRNGs (which have zyllions of uses in science, mostly in Monte Carlo methods and machine learning, but also some in "consumer computing" like raytracing). But no, Intel made a sluggish hardware PRNG that occasionally eats some thermal bits just to make crypto guys happy -- and bang, now everybody thinks it is an NSA backdoor.
- Perseids 13y agoYou think 500MB/s [1] is slow? Or are you concerned with the latency of each call? Also I don't understand why you rant against PRNGs. Do you know that this stretching of actual random data makes RDRAND considerable faster than using actual randomness? [1]Source: http://stackoverflow.com/questions/10484164/what-is-the-latency-and-throughput-of-the-rdrand-instruction-on-ivy-bridge http://stackoverflow.com/questions/10484164/what-is-the-late...
- mbq 13y agoThis 500MB/s a merged stream when using all cores, I got like 140MB/s on one (from my answer in the SO thread you linked). And I'm not ranting, I'm just crying over a lost opportunity. Nowadays you must spend time to think which PRNG to use and how to implement it to satisfy some quality/speed trade-off; an RNG (infinite cycle by design) directly connected to CPU (no transfer bottlenecks) that passes Die Hard (read random enough for science) would be a golden bullet. Yes, PRNG makes RDRAND faster than its entropy source in its current design; but it is not hitting any wall. Intel engineers could made it way faster if they had focused on maximal throughput possible not just big enough for crypto.
- Perseids 13y ago> And I'm not ranting Sorry if I offended you. I'm still surprised that poses a challenge for your applications. I thought fast non-cryptographic RNGs were a solved problem. How much random data do you generate? If you use a significant amount of CPU just for that I doubt it would be feasible for Intel to build a cryptographically secure RNG with the same throughput without significant extra costs (think one extra core). (I'm no expert on that subject though.)
- mcherm 13y agoWhere do I go to elect this guy "King"? All of his suggestions were reasonable and measured.
- topynate 13y agoIs rdrand really the very last stage? As in the output is "stream XOR rdrand"? If that is really the case it puts full, 100% trust in Intel not to insert a backdoor. It wouldn't even be hard. All the CPU need do is check for the xor operation used with rdrand as an operand, and instead of performing the xor, substitute the backdoored pseudo-random stream instead. No runtime monitoring of internal state would be necessary, the whole thing could be done at the assembly to microcode translation layer.
- lukio 13y agoWhy is this _AGAIN_ here? This has been posted like 50 times already during a couple of days. And what Linus says isn't actually even anything bad that should create this kind of stupid fuzz.
- PMan74 13y agoGood article if only for "bucket of digital slurry."
- deadslow 13y agoThe way things are, people are going to post on HN if Linus farts and others would upvote.