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

[John-Mark Gurney]

Bill Cox wrote this message on Tue, Jan 19, 2016 at 17:37 -0800:
> 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)

This depends upon the assumption that either the attacker has root, or
that the system designer is incompetent (which happens too often)...
Anyone who deploys systems needs to understand the deploying/cloning
systems w/o replacing the entropy pool (or having a hardware TRNG)
means an insecure system..  So, you have to start w/ an assumption that
the pool has >=256 bits of entropy...

> 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.

The assumption that once you have a secure pool, that you can deplete
it's entropy is complete BS and it's sad that Linux continues to suffer
from this misconception...  There are a number of places that talk about
this, one being:
http://blog.cr.yp.to/20140205-entropy.html

> 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...

As stated above, this is just simply making sure your system starts w/
a good source of entropy...

> 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).

This is entirely a problem w/ Linux...

There are well known and published entropy pool algorithms, like Fortuna
that are much better in this way...

[Fortuna] https://en.wikipedia.org/wiki/Fortuna_(PRNG)

[lots of Linux issues deleted]

> 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!

Wow, that's pretty bad that it doesn't even round robin...

If you have a system w/ a user on console, then it's very easy to generate
randomness...  Just have the user mash the keyboard for 80+ characters,
timing each keypress, and you'll have enough entropy...  The real issue is
off-line and embedded systems that don't have it...

> 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 :)

The real solution is for Linux to not be broken...  You just can't simply
deplete a large entropy pool ever!  If someone ever figures out how to
take 2^64 bytes of some CSPRNG (say AES in counter mode, or hash) and
extract the key, then the underlying cryptographic primitive will be
considered broken, and it'll be replaced.

-- 
  John-Mark Gurney				Voice: +1 415 225 5579

     "All that I will do, has been done, All that I have, has not."