[liberationtech] Random number generation being influenced - rumors

[Andy Isaacson]

On Fri, Sep 06, 2013 at 10:45:46AM -0700, Joe Szilagyi wrote:
> Does anyone put any stock into the rumors floating lately that the
> government may have influenced Intel and/or AMD into altering in
> subtle ways that CPUs handle random number generation? I keep seeing
> this possible FUD floating around in comments here and there on
> other articles.

I agree with some of your premises, but disagree with the conclusion you
seem to be drawing.

Yes, it's just a fear of uncertainty.  We do not have evidence, nor even
a claim based on knowledge, that HWRNG backdooring has occurred.

However, I claim that the fear is well founded and should be taken into
account by all threat models.

HWRNG is a nearly-uniquely difficult security problem to crack.  By
definition it is impossible to prove that a black-box HWRNG is safe.
This is different from the security properties of a blackbox AES or
MODMUL accelerator, which can be demonstrated to conform to a known
specification.  If your AES instructions don't do AES, then testing
against a software implementation will show it!  The AES logic unit
will have a hard time leaking the AES keybits since there's nowhere
nondeterministic to put them.  etc.

By contrast, a properly functioning HWRNG cannot be tested in a way that
distinguishes it from the output of a stream cipher seeded with a
backdoor key.  And there's no way to test the behavior of HWRNG on an
ongoing basis; even if you had a test to run, it might switch to "stream
cipher mode" under the covers.

This is not to say that RdRand is completely unusable.  Putting RdRand
entropy into a software pool implementation like /dev/urandom (or
preferably, a higher-assurance multipool design like Fortuna) is a cheap
way to prevent a putative backdoor from compromising your system state.

Now, there is a way that we can learn that a backdoor was included; if
someone does a tear-down of a HWRNG and finds circuitry that has no
purpose other than being a backdoor, that would be conclusive.  AFAIK
nobody has tried that experiment.

Weighing towards distrusting HWRNG we have the fact that NSA is reported
(yesterday) to have intentionally backdoored Dual_EC_DRBG, and to have
spent significant amounts of money to backdoor chip implementations,
with enough success that they brag about it in administrative summaries.

So, I put a lot of credence in distrusting HWRNG black box
implementations.  But unfortunately we need a lot more reliable entropy.
A fully open source, nothing up my sleeve hardware entropy source would
be a huge improvement.

-andy