[Cryptography] randomness +- entropy

[Theodore Ts'o]

On Fri, Nov 08, 2013 at 02:33:52PM -0800, Ray Dillinger wrote:
> Is there any functionality now in the linux system that provides a
> "pure" PRNG?  ie, if I know or have set the complete state, I can
> then read from it an infinitely-long stream of bits which can be
> repeated by initializing it with the same state (and which will
> repeat after some finite but very long output stream) but which
> is otherwise unpredictable?  Obviously this would be per-process;
> sharing state would allow other processes to draw outputs and
> therefore alter the sequence visible to the current process. This
> used to be random(3). I believe this is still what random(3) does.

Well random(3) is not a cryptographically secure PRNG.  So it's fine
for Monte Carlo algorithms, but not for cryptographic applications.  I
used to think that if all you wanted was a pure CSRNG, you should do
it all in userspace.  But after various implementation disasters where
pools ended up getting shared after fork(2) calls, I've decided I
placed too much confidence in the competence of application-level
programmers, and so I've re-evaluated my position on that front..

> Is there any functionality now in the linux kernel that provides
> a "pure" Random Number Generator?  IE, it would trap, or set an
> 'invalid' flag, or suspend the caller, or something, but won't!
> ever! return a number when there is insufficient entropy to be
> sure that that number is less than completely unpredictable?
> This is what /dev/random was supposed to be, right?

That is still what /dev/random is.  If you don't have enough entopy,
you will block.  The main concern with /dev/random is whether or not
the entropy estimators, which were designed to be conservative, are
really conservative enough.  The work done by Lacharme, Roeck,
Strubel, and Videau in their paper, "The Linux Pseudorandom Number
Generator Revisited"[1] seems to indicate that we are being
sufficiently conservative, but this is always an area were I've been a
little nervous, especially since the work to indicate that there is
hard entropy coming from the chaotic air patterns in HDD's was over
two decades ago.

[1]http://eprint.iacr.org/2012/251.pdf

It's also why I've been a bit resistant towards CPU jitter designs,
which basically use the argument "there sooooo much internal state and
it's soooooo complicated how the L1, L2, TLB cache works, and *I*
can't figure out any kind of correlation, surely it *must* be
entropic".  Of course, the Soviets didn't think the NSA could figure
out the Venona ciphers, either....

> Because, honestly, the 'hybrid' state of both of /dev/random and
> /dev/urandom right now is giving me some concern.  There was a
> time when /dev/random was supposed to deliver NOTHING but hard
> randomness you could absolutely rely on for keying material, and
> /dev/urandom was supposed to be a best-efforts approximation to
> the latter but would rather return a (possibly somewhat)
> predictable result than fail or slow down your process. Knowing
> for sure which was what made designing robust and secure systems
> straightforward, if sometimes hard.

The 'hybrid' nature was always for /dev/urandom (and not /dev/random),
and as I've said, it's going to be evolving towards a CSRNG which gets
periodically reseeded from the entropy pool.

The main reason why most application programs tend not to want to use
/dev/random is precisely because it will block --- but if you want
hard randomness, and the system doesn't have any, what else can you
do?

> The discussion here makes me want to craft something that gives
> two simultaneous results; first, the "random number", and second,
> a "confidence score" that indicates how certain I can be that the
> "random number" is unpredictable.

My suggestion would be to develop some tools that would help us give a
"confidence score" for each entropy source that gets feed into an
random number generator.  This may be a multi-dimensional score,
though, since for some people, it might be enough to assume that the
adversary can't monitor some kind of internal state (i.e., the network
timing on your LAN), but for others, they don't want to make that
assumption (after all, the NSA might have somehow figured out how to
trojan your network switch, for sufficiently large values of tin foil)
and so they want to the confidence score to be tied to physical
quantuum or chaotic effects.  For yet others, they will be willing to
trust that Intel, or some other hardware vendor, is honest in
designing what they claimed, and for others, they aren't so sure.

So the if we can't figure out how to award a "confidence score" to
RDRAND, and some people are using rngd to feed fully credited entropy
into /dev/random, how are you going award a objectively agreed upon
"confidence score" to a system configuration which uses /dev/random
and rngd to feed physical entropy from RDRAND?

If you have more confidence in Intel, and less in the amount of
entropy you can get from measuring HDD or SSD timings, the score might
be very different than if you don't want to include Intel in your TCB.

Regards,

					- Ted

P.S.  The reason why I say the confidence score has to be based on a
specific system configuration is yet another variable might be if you
need to trust that Red Hat or SuSE wasn't approached by the NSA to put
something special in their kernels, versus if you built the kernel
from scratch and someone _you_ trusted to audit all of the
security-relevant code, which would include the /dev/random driver,
the crypto code, critical userspace daemons that listen to the
network, etc.  (And if you do care about such things, that's when you
hire someone like Kees to work on improving the security of ChromeOS.  :-)