[Cryptography] TRNG related review: rngd and /dev/random

[Bill Cox]

I've talked a bit about different TRNGs, but there is more to the story.
Once "random" data leaves the TRNG, there needs to be software to make use
of this data securely to generate cryptographic IVs and keys.  I _think_ I
know enough now days about /dev/random and rngd to have a useful opinion,
so here goes...

The problem seems simple.  We want to take all the sources of "entropy" we
have access to and mix them together in a big "entropy pool" which when
completely randomized, can be used in crypto.  However, it must be harder
than it sounds, because we seem to have trouble building opensource entropy
pools that work exactly right, and there is contention about what "exactly
right" would mean in this case.

First, here is my almost certainly inaccurate list of dirt on /dev/random:

- Denial of randomness attacks are as simple as "cat /dev/urandom >
/dev/null"
- If entropy is trickled in, and an attacker who knows the initial state of
the entropy pool (which is a file on disk) and all the public keys of all
pairs generated from /dev/random, she can easily guess all the private keys
- If the hard-coded models in the kernel of entropy in its various sources
(network, hard disk, interrupts) are highly inaccurate (common in VMs for
example), then the entropy in the pool can be highly over-estimated
- Embedded systems such as DD-WRT have had insecure keys due to such issues
(though I think the DD-WRT folks bear much of the blame in this case)

All that said, if you feed and care for this beast properly, you can
generate secure keys from it.  When I generate keys, I check the entropy in
the pool, which you can do with

    $ /proc/sys/kernel/random/entropy_avail

Without a hardware TRNG, the pool on my loptop grows at a very slow rate.
This is likely due to conservative entropy guestimates in the kernel, so I
don't think this is a problem by itself.  If all you want to do is generate
keys with ssh-keygen right away, consider some advice I read here on this
list, and take a photo of your cat (because cats are scientifically proven
to be excellent sources of randomness).  Upload it to your laptop, and
simply do:

    $ sudo cat cat.jpg > /dev/random
    $ shred cat.jpg

If you have an SSD, shred will run, but it wont work...

Assuming you feel good about having randomized /dev/random, just go
generate keys with ssh-keygen, and all should be fine.  However, you may
notice if you are  on an air-gapped machine (which you should be, to
protect the world from all that cat randomness), that it takes a heck of a
long time to generate an RSA-4096 key.  It takes ~30 minutes on my
machine.  This is because the Linux kernel wisely allows you to write
randomness, but it does not assume that your data actually added randomness
to the entropy pool.  Doing that requires using a low-level APIs (ioctrl).

So, if you, like me, got frustrated repeatedly creating keys on air-gapped
Linux machines, the answer may be a hardware TRNG, such as OneRMG
<http://onerng.info/>.  If you do use OneRNG, and follow their directions
(from a few months ago), you'll use rngd to talk to the OneRNG, and rngd
will feed /dev/random.  You will be able to generate cryptographic keys
very fast, because rngd assumes every bit it writes is 100% random.  I hope
that gives everyone a nice warm feeling...

So, here's my almost certainly inaccurate dirt-list on rngd:

- It assumes every bit written is 100% random, and updates the Linux
entropy pool estimate to say so.
- It uses FIPS testing to ensure that the bits are random (there is a
barf-bucket around the corner for you statistical wizards)
- It stops writing to /dev/random after one batch of bits is written (a
nice large batch)
- It will ignore all other entropy sources if hardware TRNGS are enabled
and Intel RDRAND instructions work on your CPU

The _right_ way, IMO, to mix entropy is with a more sophisticated tool that
has a physical model for understanding how each source of entropy works.
That way, we can write a health monitor for each source, and at least
somewhat justify using the claimed entropy rate from these sources.  AFAIK,
rngd has no way for the entropy source to say, "Here's my raw data, I think
it has 0.8 bits of entropy per bit".

The problem is that _every_ entropy source has measurable bias.  There are
no exceptions I am aware of.  To pass the FIPS test required by rngd, every
TRNG manufacturer is therefore forced to pre-whiten the data before rngd
sees it.  This code is usually closed-source, and embedded permanently in
hardware that is difficult to audit.  I suspect most of it is done poorly,
such as feeding an 8-bit hardware ring-oscillator output into a 80-bit LFSR.

The worst problem I found, the one that caused me to stop using rngd, is
that it refused to write data from my OneRNG device to /dev/random.  This
was because in Ubuntu 14.04, with hardware TRNGs enabled in rngd, the
RDRAND instruction _always_ generates all the bits rngd wants before any
other source can generate 1 bit.  The result is that _all_ entropy from
rngd was RDRAND data, and zero was from the OneRNG!

These problems are fixable.  Health monitors with good entropy estimators
should be required for each entropy source.  The rngd-internal pool should
wait until it has enough randomness from N sources before writing any data
to /dev/random,  where N is user-selectable, or even better, allow the user
to specify exactly which sources are required to provide a secure number of
bits (> 200-ish) before the pool is considered secure.  Then, write the
whole thing to /dev/random, and repeat.  Do some decent mixing in rngd
first, with a cryptographic sponge (I use Keccak-1600).

For now, I just use the TRNG I carry in my pocket, an air-gapped machine,
and an my own software for randomizing /dev/random.  Now, I just wish I had
a good reason for all this secrecy :)

Bill
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20160119/e951e6f2/attachment.html>