Hacker News Reader

Comment by gnu8 | Hacker News Reader

If I recall correctly, Linus refused to make this change in Linux, denouncing it as paranoia.

My fear is that the extra complexity adds additional opportunity for a back door to be inserted. However, software can be audited, the hardware cannot be.

View on HN

No, Linus has refused to make a different change in Linux (the complete removal of RDRAND) because linux does not directly use RDRAND output, and it already uses RDRAND as an other source of entropy[-1], which is what FreeBSD is moving towards.

According to Theodore Ts'o, there was pressure from Intel engineers to rely solely on RDRAND but they were rejected[0], it looks like the FreeBSD devs did do it and have /dev/random using RDRAND/Padlock directly[1]

[-1] although — and I don't know why — the linux rng XORs pool output with RDRAND output instead of feeding RDRAND into the entropy pool itself[3]

[0] https://plus.google.com/+TheodoreTso/posts/SDcoemc9V3J#+Theo...

[1] That's the only way I can interpret "for 10, we are going to backtrack and remove RDRAND and Padlock backends and feed them into Yarrow instead of delivering their output directly to /dev/random"[2] anyway

[2] http://www.freebsd.org/news/status/report-2013-09-devsummit....

[3] I'll try to stop now but[4] provides a rationale for it: a history of unnoticed bugs in the random pool making the risk of a trivial xor lower as far as kernel devs are concerned: if you xor a known A and an unknown B, you can't know anything about the output (it won't be any more known than B is), whereas if you know of bugs in the random pool you might be able to take advantage of them and skew the output. Make of that what you will.

[4] http://thread.gmane.org/gmane.linux.kernel/1323386/focus=133...

The last time I've followed, RDRAND was not "just another source" in Linux, as it was xored after another sources were "fully" mixed.

Yes, I had modified my comment to make note of that. Although I tuned the language a bit more (removed the "just" of "just an other source")

Any info on why Intel engineers applied the pressure ?

I've no more information than Ts'o's word, and a commenter or two noting that they remember facing the same pressure (e.g. Jeff Garzik). It is possible and believable that the engineers themselves simply thought "we're providing a perfectly good random data stream, why would you bother doing more work on top of it and increasing the cost of your RNG?", just as it's believable they were in on it.

There are some relevant comments in the latter third of the thread:

> [Ts'o]

> When I asked the engineer who submitted it what his rationale was, he couldn't give me a coherent answer. He tried to handwave something around performance. When I pointed out this was not a problem since we had engineered solutions to support all of the systems that didn't have RDRAND, and invited him to give me one example where we had a performance bottleneck, he never responded.

> [Tony Luck]

> More clarifications - there have been engineers from both Intel and Red Hat referenced in this thread. I believe in the response above Ted is referring to the Red Hat one when he talks about not being given a rationale for a patch being submitted.

> The lead sentence of the post that started this whole thread is rather misleading, and perhaps based on Ted mis-remembering the exact nature of the patch that he applied in July 2012. At no point did any Intel engineer apply "pressure from Intel engineers to let /dev/random rely only on the RDRAND instruction". Peter pointed out above that RDRAND is not suited for this, given the ways that /dev/random and /dev/urandom are used - which is why his patch did not feed RDRAND straight to /dev/

> [Ts'o]

> +Tony Luck That's fair, I should have said /dev/random driver. However, note that get_random_bytes() does get used for key generation inside the kernel, so if RDRAND was comrpomised, we could get screwed that way. The bigger threat though is actually openssl choosing to use RDRAND directly for session keys, without doing something like encrypting the RDRAND output with a secret key. (And BTW, OpenSSL does have a RDRAND engine so that's just a configuration away....)

What Linus correctly points out is that when multiple sources of entropy are combined, no single source can act to diminish the sum total of entropy. Even if rdrand was comprehensively backdoored and entirely predictable by the US government, it's still going to improve the quality of randomness. At worst it's a wash, but it will never reduce it.

Here's the direct link to Linus Torvalds' entertaining observation:

http://www.change.org/en-GB/petitions/linus-torvalds-remove-...

> You recall correctly indeed

No, the situations and concerns are very different.

The situations are indeed different because it's FreeBSD and not Linux. And there's different history behind their /dev/random implementations. But the underling concern is the same: a lack of trust for rdrand -- and the solution should be the same: to only ever use rdrand as an "improver" and never as an actual source of entropy.

The difference is that Linux already didn't trust RdRand, and didn't use RdRand as the sole input to /dev/random.

You're right, the OP's post was badly worded, possibly mistaken, as it implies that the change Linus refused to make was analogous to this change.

It's not true that it will never reduce it. It wouldn't be too hard for a CPU to notice when the result of RDRAND is XORed with something, and do evils to deliberately control the eventual result.

  fake_random = 5
  result = secret ^ real_random
  result = result ^ fake_random

You know the value of fake_random, but the randomness isn't reduced at all (sorry, I can't produce a real mathematical explanation)

  current_random = <something unpredictable>
  fake_random = RDRAND()
  new_random = current_random XOR fake_random

Surprise! new_random is predictable, because the malicious CPU peeked ahead at the XOR operation and adjusted the RDRAND operation accordingly.

Can't you wrap the RDRAND call with some long complicated code , so that tracking what fake_random will be hard to in hardware , thus preventing this attack?

Yes, but then it's an arms race between the hardware manufacturer and the random number software writer.

The fact is that the Linux/BSD random number generators were actually rather good before all this RDRAND stuff.

Try this again, but instead of:

    fake_random = 5

Try:

    fake_random = secret ^ real_random ^ 5

No matter what secret or real_random are, result is now 5. You can't hide secret or real_random from the processor.

In a larger sense, there's no way to stop the processor from simply setting result to whatever it wants before returning it to the place where it's used.

My point is, there's no real way to trust hardware that can't be verified.

Yeah, in fact someone did a neat PoC of this using virtualization software the other day: https://twitter.com/DefuseSec/status/408975222163795969/phot... That's with an unmodified Linux kernel and unmodified instruction set aside from RDRAND. (In practice you'd make the result something less obvious than a constant value, but this presumably makes for a clearer demo.)

Fantastic example of what I was saying. Thanks for that.

Yes, but as stated further up, that CPU could anyway just write arbitrary data to the memory that holds your entropy pool, if you use RDRAND or not.

That's a more fragile attack though, since it requires identifying that memory location.

Really? How?

I think you're mistaken. It looks more like FreeBSD is moving to using these devices the same way Linux already does.

No, as I understand that's a different change. The current state of FreeBSD, if I understand correctly, is that it has the option of returning the hardware-generated random sequence directly. They're changing it so it feeds entropy into the pool. Linux does neither, instead it xors the output of the entropy pool with the output from the hardware random number generator. This is strictly no less secure than the entropy pool on its own.

Note that the implementation of the systems' entropy pools is also quite different -- my understanding is that FreeBSD uses Yarrow, a pRNG, to feed /dev/random, while Linux mixes bits of 'real' random data together, without the extra pRNG stage. Which of these schemes is better is irrelevant to this particular discussion.

No links, I'm afraid, as EE apparently thinks Stack Exchange isn't suitable for under 18s and I can't turn content lock off at the moment.

> This is strictly no less secure than the entropy pool on its own.

I'm not quite certain, it should be possible (though possibly overly complex) to use RDRAND (or calls to the crypto routines) as a trigger for a XOR backdoor working in concert with a RDRAND backdoor, and thus control the final output.

It wouldn't actually be that hard for a CPU to notice which register the result of RDRAND was being XORed with and just set that register to something generated instead. Because, you know, that doesn't actually break any contracts. The effect is still that of XORing with a number we didn't know beforehand.

That assumes we can't read the result of rdrand after the XOR is performed. I don't know the specifics of how the chip RNG is implemented in hardware, but surely its values have to hit some sort of readable memory before the kernel's code performs the XOR?

It doesn't really assume that at all. You can maliciously generate the result of RDRAND according to the instructions that are going to use it - that doesn't prevent that value being used later.

The way a CPU works internally, intermediate results are written to registers, and the registers specified by the machine code are rewritten onto a larger set of real registers. The CPU knows at the instruction decode stage which results are going to be used by which instructions, so that it can schedule them for out of order execution. It also knows when it can throw away the result of a real register because the machine code register it represents has been overwritten with another value. So if the result is used by a second instruction, that doesn't matter

Yes, if you wrote the result of RDRAND to main memory and read it in again, you would destroy that knowledge, but I would bet that the random number generator doesn't do that.

It could certainly be used as an integrity check. If you get different results from the same operations on what should be the same numbers, you know your hardware is maliciously unfit for purpose.

Uh. You're saying you should compare the result of running a random number generator twice and seeing if the two values are the same?

No, you store the register value holding the RDRAND result into memory, then you store the register value holding the number from your other sources of entropy.

Then you read them back from memory and XOR the same numbers again. You compare that result with the XOR from the register values and see if they are the same.

If they are different, the chip is substituting a different XOR result whenever it is capable of determining that one of the operands is the output of an RDRAND instruction.

You might presume that an efficient mixer of multiple entropy sources would just XOR all of its various inputs together, so compromising XOR would be an easy way to discard the entropy of the other inputs in a way that is not easily detected without writing assembly code specifically to check it.

That doesn't protect against the CPU choosing the return value of RDRAND maliciously - just against the XOR operation being duff. To be honest, it's much easier for a CPU to have a malicious RDRAND than compromise XOR. As demonstrated in another post, returning "edx XOR <something predictable>" hoses the Linux RNG.

But a malicious RDRAND is, at worst, useless, contributing zero entropy to a pool of multiple sources. A malicious XOR could reduce the entropy of the pool.

Theoretically, sure.

But practically, that would be (a) easy to catch happening, and (b) require the chip to fingerprint the relevant sections of machine code as implemented in multiple versions of the Linux kernel, and as compiled with innumerable iterations of compiler settings and versions.

I don't want to say improbable, but I find it difficult to imagine otherwise.

Your comment implies that Linus trusts Intel. This is not true, since the change is unnecessary even if they were infiltrated:

"Long answer: we use rdrand as _one_ of many inputs into the random pool, and we use it as a way to _improve_ that random pool. So even if rdrand were to be back-doored by the NSA, our use of rdrand actually improves the quality of the random numbers you get from /dev/random." http://www.change.org/en-GB/petitions/linus-torvalds-remove-...

The conclusion is arguably correct, but the premise not so much. RDRAND isn't used as an input to the random.c pool: http://blog.lvh.io/blog/2013/10/19/thoughts-on-rdrand-in-lin...

> However, software can be audited, the hardware cannot be

Exactly. So work on solid security/privacy principles, rather than take the easy way out and hope for the best.

Reply on news.ycombinator.com