Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Linus on /dev/random: "We actually know what we are doing. You don't."

nakedsecurity.sophos.com

Post reply on HN
Print view View original

51–60 of 77 posts

Re: Linus on /dev/random: "We actually know what we are doing. You don't."

#51

Post by jacquesm »

makomk wrote: post #31
jacquesm wrote: post #16

This 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…

Did 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 implementat…

> All it has to do is detect the code sequence in question

Extraordinary claims...

Re: Linus on /dev/random: "We actually know what we are doing. You don't."

#52

Post by willvarfar »

Perseids wrote: post #34
willvarfar wrote: post #27

Earlier quoted context omitted.

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

Why 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 p…

You are completely right.

https://plus.google.com/117091380454742934025/posts/SDcoemc9... and https://lkml.org/lkml/2013/9/6/205 are interesting explanations too.

Re: Linus on /dev/random: "We actually know what we are doing. You don't."

#53

Post by farresito »

icecreampain wrote: post #9

If 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 intere…

He has the same right as you, as me, and as Linus Torvalds to criticize something. There are better programmers than Torvalds out there that are not as successful as he is, and the other way around.

Re: Linus on /dev/random: "We actually know what we are doing. You don't."

#54

Post by betterunix »

willvarfar wrote: post #27
makomk wrote: post #23

Earlier quoted context omitted.

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

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

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

It could potentially use the number of milliseconds since the last hour, or maybe the state of the branch predictor, or any number of other things that have exploitable biases (with NSA resources, 1/1000000000 is pretty good odds).

Re: Linus on /dev/random: "We actually know what we are doing. You don't."

#55

Post by betterunix »

georgemcbay wrote: post #3

I 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 statis…

Ah but that is not quite as easy as you might think. Maybe RDRAND is actually a keyed PRNG, so it is computationally hard to distinguish from "true" randomness. Maybe there are only 1000000000 possible keys, so while you could theoretically detect the back door, it is impractical/unlikely for anyone with less than NSA resources to do so. Conveniently, the NSA has the resources to exploit such a bias.

To further throw you off, it could be the case that the back door is only exploitable after, say, 1kB of output, and it is "truly random" prior to that. That would be plenty useful for the NSA's purposes. It might even be that the back door is only exploitable for some part of the output, maybe the part where you are most likely to find a suitable prime number during some key generation process. Intel periodically releases new products, so the NSA would have plenty of chances to update the backdoor as software changes.

Re: Linus on /dev/random: "We actually know what we are doing. You don't."

#56

Post by chris_wot »

icecreampain wrote: post #9

If 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 intere…

Excellent trolling. Now lets everyone ignore this post.

Re: Linus on /dev/random: "We actually know what we are doing. You don't."

#57

Post by XorNot »

solarexplorer wrote: post #46
zamalek wrote: post #28

Earlier quoted context omitted.

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

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

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

Re: Linus on /dev/random: "We actually know what we are doing. You don't."

#58

Post by alfiejohn_ »

jgrahamc wrote: post #38
makomk wrote: post #31

Earlier quoted context omitted.

Did 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 implementat…

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. How is that going to work? i.e. how is RDRAND going to 'detect the code sequence'?

Aren't the next instructions going to be in the code cache? So "detecting the code sequence" would seem trivial.

Re: Linus on /dev/random: "We actually know what we are doing. You don't."

#60

Post by zamalek »

solarexplorer wrote: post #46
zamalek wrote: post #28

Earlier quoted context omitted.

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

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

Agreed. However any form of "tricking" would be ultimately pointless because a small adjustment could be made to random.c. Existing CPUs can't be "changed" (barring microcode, but avoiding that is simple - don't install new microcode) so they would no longer work against the system.

In addition the amount of transistors required to actively circumvent random.c is prohibitive: CPUs would need to be significantly larger to pull off attacks like this.

Post reply on HN