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

21–30 of 77 posts

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

#21

Post by Perseids »

georgemcbay wrote: post #7
ygra wrote: post #6

Earlier quoted context omitted.

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

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

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

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

#22

Post by CJefferson »

jpalomaki wrote: post #15

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

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

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

#23

Post by makomk »

willvarfar wrote: post #19

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

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.

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

#24

Post by Perseids »

shin_lao wrote: post #14

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

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

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

#25

Post by einhverfr »

simias wrote: post #5

We 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 ou…

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

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

#26

Post by mbq »

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

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

#27

Post by willvarfar »

makomk wrote: post #23
willvarfar wrote: post #19

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

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.

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

#28

Post by zamalek »

tspiteri wrote: post #13

Please do not submit professional troll articles.

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

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

#29

Post by willvarfar »

antocv wrote: post #8
yeukhon wrote: post #2

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

Bruce 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 w…

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

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

#30

Post by simias »

einhverfr wrote: post #25
simias wrote: post #5

We 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 ou…

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

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

Post reply on HN