Trojan hardware RDRAND

[D. J. Bernstein]

http://people.umass.edu/gbecker/BeckerChes13.pdf appeared at CHES 2013
last month. It explains how to build a circuit that looks just like the
Intel RDRAND circuit under a microscope and that passes all the RDRAND
tests, but that also has a back door, making the output predictable to
anyone who knows a secret master key used by the chip builder.

The security consequence is that anyone building keys from RDRAND is
giving Intel, and anyone with sufficient control over Intel, the power
to predict those keys. Even rather extreme reverse engineering would not
detect an exercise of this power. Linus Torvalds was quite wrong in

http://lkml.org/lkml/2011/7/30/116

when he claimed that RDRAND is "public and testable."

Normally /dev/urandom etc. hash multiple entropy sources together, so
there's no harm in adding another source, such as RDRAND. Users who
don't trust the available sources should simply be able to feed some
random keyboard data to /dev/random; then all subsequent /dev/urandom
output will be unpredictable to anyone without a keyboard recording,
no matter how busted the other entropy sources are.

However, for years Intel has been pressuring OS designers to _eliminate_
entropy sources other than RDRAND. The Linus comment above was in the
context of Intel supplying an "RDRAND bypass" patch for Linux. Intel
even claims in

http://www.spinics.net/lists/linux-crypto/msg05883.html

that there's something _wrong_ with feeding RDRAND into /dev/random---
the only "suitable" use of RDRAND is to replace all /dev/urandom output.
Ted Ts'o now says in

https://plus.google.com/117091380454742934025

that he's "so glad" he "resisted pressure from Intel engineers to let
/dev/random rely only on the RDRAND instruction"---but

https://mailman.stanford.edu/pipermail/liberationtech/2013-July/009964.html

seems to indicate that, at least for a while, Linux was in fact allowing
RDRAND to override all other /dev/urandom inputs.

Even worse from a security perspective, Intel is telling _application
developers_ to use RDRAND directly, rather than /dev/urandom. Examples:

http://software.intel.com/en-us/articles/user-manual-for-the-rdrand-library-linux-version/

http://blog.cryptographyengineering.com/2012/02/random-number-generation-illustrated.html
(Intel's David Johnston: "So... eliminate software PRNGs. Just use the
output of the RDRAND instruction wherever you need a random number.")

https://plus.google.com/108313527900507320366/posts/aJvcT7fQSep
(Johnston again: /dev/urandom fails "often" so RDRAND is designed
to "feed entropy directly to the register space of the running
application. ... Standards compliance is an excellent option here.")

The old situation was that many people were incorrectly told that
managing their own entropy pools would improve security, but only a
small fraction went to the effort of actually building their own pools
instead of simply reading /dev/urandom, so we're faced with only a
medium-size crypto-engineering mess to clean up. The new situation is
that no effort is required. RDRAND is going to appear tens of thousands
of times in thousands of applications---and there won't be anything
_visibly_ wrong with the results, so we'll have a tough time explaining
why the application authors should disregard Intel's RDRAND advice.

I chatted with Intel's Jesse Walker about this at CHES. He disclaimed
responsibility for Intel pushing RDRAND into applications; apparently he
was outvoted within Intel.

---Dan

[hein...@gmail.com]

On https://spideroak.com/browse/share/UTwente/RNG/Tests/NIST-STS/ you can find the results of randomness tests of several random generators including RDRAND.

In the document No_of_failures_calculation.txt you can find the used testing method and the test results.

The actual number of failed tests of RDRAND deviates more then 4 sigma from the expected number of failed tests.

The used software can also be downloaded from the same link so these tests can be reproduced.

As you also can see the XOR_SHIFT PRNG and the Picoquant PQRNG150 TRNG pass the tests with a number of failed tets within the 3 sigma deviation so the tests seem to work fine.