Re: Lightweight support for instruction RNGs

On Mon, 21 Dec 2015, Alistair Crooks wrote:
> What I'm trying to get at is that some people seem to think "more
entropy is good", and I don't believe it's as simple as that.

  The only attack I know of where adding additional entropy can be harmful
is DJB's attack (http://blog.cr.yp.to/20140205-entropy.html) where
malicious CPU firmware could snoop on the other values used and brute
force a few bits of the output.  This shouldn't normally help
signficantly, but some extremely fragile algorithms exist (e.g. DSA with
random nonces) that can be completely broken by a consistent few bits of
"randomness" never being random.  Additionally, this could be an
exfiltration route for otherwise secret data.  The testing you suggested
might determine if this attack was being carried out, although the
malicious firmware could almost certainly tell when such tests are run
and not affect the output then (or just time limit how often the attack
is performed to not affect testing).  The malicious code may also not be
the normal code and might not be present on the test machine even if it
exists somewhere.  Thor's code seems vulnerable to this attack.  OTOH,
it isn't clear to me that a CPU that could do this couldn't also detect
the particular algorithms using the random data and just modify the data
in memory then (even if you don't use CPU random data, and then it
wouldn't need to brute force anything and there would be no way to avoid
it).  Maybe that would be harder but maybe not; the attack is already
not generic in that each OS entropy pool works differently.  So I think
DJB's attack should be considered (I think the argument is that other
possible attacks would be more likely to be detected), but avoiding it
isn't necessarily the best choice depending on the tradeoffs and overall
strategy (in particular, to what extent NetBSD is aiming to recover from
state compromise; if that isn't a goal (and it doesn't seem like a goal
looking at the code) then initializing the pool with CPU random data
rather than adding it later would prevent this attack without any
downside).

  Besides that attack, the main issue I see with Thor's code is that
RDSEED is vulnerable to unprivileged exhaustion, so I would suggest
falling back on RDRAND if RDSEED fails (I don't think RDSEED will ever
be present without RDRAND, so one extra test and fallthrough would do
that, plus verify both are present in init just to be sure).  RDRAND
could potentially fail temporarily in some future CPU (Intel only
guarantees it won't temporarily fail if you call it ten times in a row)
but it might not make sense to deal with that in this context since it
should be called often enough to make it highly likely that it should
provide data sufficiently often even with an exhaustion attack (at least
if there is a decent probability of first call success with such
attacks; I don't know if there could possibly be exhaustion attacks that
are reliable if RDRAND is only called once).  OTOH, calling it ten times
would allow printing a message if it fails ten times and the user would
almost certainly like to know if their CPU RNG is broken, although I'm
not sure how likely it is that the RNG breaks while the rest of the CPU
continues to work (or how long it would take the user to see a line in
dmesg if that does happen).

> As an aside, I think that we all need to remember, on some platforms,
our entropy pool is not as full as we'd like it to be.

  An excellent reason to use CPU randomness when available.  This seems
much more likely to cause problems than malicious CPU firmware.

-M