BHUSA15: Understanding and Managing Entropy Usage

Bruce Potter is a director at KEYW Corporation and was previously the Chief Technologist and cofounder of Ponte Technologies. Sasha Wood is a Senior Software Engineer at KEYW Corporation, with ten years' experience in developing and assessing software systems, and researching classical and quantum computational complexity.

Their research was funded by Whitewood Encryption Systems, with help from great interns.

Their goal was to get a better understanding of how entropy is generated and consumed in the enterprise. There were rants from Linus, but nobody seemed to be looking at the actual source code. They wanted to determine rates of Entropy Production on various systems, determine rates of Entropy Consumpitio of common operations and determine correlation etween entropy demand and supply of random data..  The theme: "No one really understands what's happening with entropy and random number generation"

What uses more entropy? Generating an RSA512 bit key or 1024? They both use the same! Surprisingly, running /bin/ls uses more entropy from the kernel than setting up a TLS connection!

How do we distinguish between entropy vs random numbers? It's a bit of a state of mind, there are several ways to think about it.  Entropy is the uncertainty of an outcome. Randomness is about the quality of that uncertainty from a historical perspective.

Full entropy is 100% random. There are tests that measure entropy, but randomness either is or is not. Entropy has a quantity and randomness has a quality. Think about the simple coin flip. A regular person flipping a coin will have random output, but someone like the magicians Penn & Teller - they can control their flip and the outcome is NOT random.

As long as we have great cryptographic primitives, the RNG will be excellent. In theory.

This is actually really hard to judge without analyzing the source code and doing actual testing. Documentation does not match what's actually in the source (common problem). This testing was done on Linux (note: I missed the version number).

On Linux, there are two PRNGs - one that feeds /dev/random and one that feeds /dev/urandom, but both leverage the same entropy source.

Entropy sources: time/date (very low entropy), Disk IO, Interrupts, and other SW things

There are Hradware RNGs - like Ivy Bridge, that uses thermal noise. There's Entropy Key (shot noise, from USB generator). Some places even use Lava Lamps! (seriously)

Linux maintains a entropy pool, data goes in and then fed out to the PRNGs. It has a maximum amount in the pool, but if you don't have HW behind this - it will never fill up.

Linux has a system call that will tell you how much entropy is in the pool.  But, beware - don't check it with a script! you'll invoke ASLR, etc, which will consume entropy from the pool.

The /dev/random and /dev/urandom is generally close to ero. Entropy is fed from the main pool when necessary.

Unloaded VMs are only generating 2 bits of entropy per second. Bare metal is a big faster. The more loaded the machine is - the more entropy you'll get.

For example, if you ping the machine every .001s, it will generate entropy at 13.92bits/s, as compared to 2.4 bits/s on an unloaded system.

RDRAND is normally unavailable in a VM, however, even on bare metal, kernel entropy estimation was not helped by RDRAND. Turns out,due to recent concerns regarding RDRAND, even though RDRAND can be used to reseed the entropy pool, the entropy estimation is NOT increased by the kerenel...on purpose.

VMs do get starved of entropy, but even bare metal systems aren't great.

Android devices did better than Linux boxes observed.

Oddly, the accelerometer on Androids is *not* used to feed the entropy pool, although it would be a good source of entropy.

/dev/random provides output that is roughly 1:1 bits of entropy to bits of random number, access depletes the kernel entroy estimation and with block if the pool is depleted.

/dev/urandom works differently  if you ask for 64 bits, it tries to get 128, and reduce estimation doesn to 128bits. Will not reduce entropy estimation from the pool if the pool is less than 192 bits. Each read produces a hash which is immediately fed back into the pool.

get_random_bytes() just a wrapper to access /dev/urandom.

Here are somethings that are not random: C's "rand" (a linear congruential generator" - if you know two consecutive outputs, you know ALL the outputs.

Python's randompy - implements a Mersenne Twister. Better than rand(), but still not suitable for crypto operations. Need 650 outputs to break the algorithm. So, better, but not great.

When Linux spawns processes, it spawns ASLR, KCMP and other aspeces of fork/copyprocess() , consume up to 256 bits of entropy each time you start a process.

This is not consistent, though, so more research.
 
OpenSSL maintains its OWN PRNG that is seeded by data from he kernel. This PRNG is pulled from for all cryptographic operations including: generating long term keys, generating ephemeral and session keys, and generating nonces. 

OpenSSl only seeds its internal PRNG once per runtime. No problem for things like RSA 1024 it keys. It's a different situation for long running daemons that link to OpenSSL... like webservers.Apache PFS connection requires 300-800 bits of random numbers. If your application does not restrict this, you will be pulling this data from a source that is never reseeded.

OpenSSL pulls seed from /dev/urandom by default (and stirs in other data taht is basically knowable). OpenSSL does NOT check to see the quality of the entropy when it polls /dev/urandom.

mod_SSLs attempt to generate entropy is not very sophisticated. On every request , it stirs in: date/time (4 bytes), PID, and 256 bytes off the stack.  Date/time is low resolution and guessable, ID is a limited search space, and it always looks at the same place on the stack.

mod_SSL is trying really hard, but not really accomplishing much.

How much entropy goes into each random byte?  It depends...

The researches tested various common actions in OpenSSL. Different operations required different amounts of entropy. When creating keys, you need to find big numbers - there's a lot of testing that goes on to find a prime.

Attacks on PRNGs come under three umbrellas: Control/Knowledge of "enough" entropy sources (like RDRAND), knowledge of teh internal state of the PRNG, and analysis of the PRNG traffic.

By default, the Linux kernel pulls from a variety of sources to create entropy pool, so difficult to control them all. Knowledge of the state of the PRNG is very complex, but not impossible to understand.

The caveat is based on PRNGs being seeded correctly - analysis is showing this is not the case.  So, you can follow NIST's guidance on correctness, and still get this wrong.

The researchers created a WES Entropy Client as a solution to the wild west of entropy generation and distribution. Initial release is for OpenSSL.  Client allows users to select sources of entropy, how to use each source, which PRNG to use, etc.

Currently available at http;//whitewoodencryption.com/

Client is under active development, looking for feedback.