Best Entropy Generation Software for Linux

Best Entropy Generation Software for Linux

Randomness and entropy – why do computers need it? The key feature of entropy in computer information security is its unpredictability and uncertainty). The important part of keeping information in computers secure is an unpredictable key. The important part is unpredictability, true randomness is not as important.

Like a safe it is important to pick a combination that is unpredictable one that no one can guess. What better way to find a combination that no one will guess than turning to randomness. But if your source of random numbers just happens to give you a series like 222334 you should reject it and try again. It may be random but it does not pass a level of uncertainty or entropy.

Operating systems generate a pool of entropy which is used to generate random numbers. This pool of entropy or randomness is used as a very important part of securing your computer.

With this data secure keys and passwords and session ids to track unique users are generated. One important key to having encrypted data is a piece of data that no one else knows or can guess. A series of binary numbers from the entropy pool is the way computers attempt to find a random, unique value that no other computer would come up with. A little bit of random data is used as a seed to generate lots of random data.

Real Hardware vs. Virtual

If you are running your operating system and software on a physical server maintaining entropy is not really an issue with modern CPU technology. Intel built random number generation into their newer chip sets. Although not everyone trusts it. But for virtual machines (VM) it is more of a problem as the operating system is running on a virtual or simulated machine. Operating systems may collect entropy from things like the movement of the mouse, keystrokes on the keyboard, timing of computing operations or other hardware like video or sound cards. The issue with a VM is that it does not have access to real hardware that behaves in a random fashion, it only has access to virtual hardware er.. software.

Sometimes you may not be able to generate encryption keys or start software like web servers until enough entropy has accumulated. In Linux this pool of randomness is typically in /dev/random/. If your software is using this pool it will wait until there is enough quality randomness the system has collected and computed. But you can always point applications at /dev/urandom which is good enough as long as the server has had time to generate some entropy. /dev/urandom will not block software from working but there is potentially less randomness to any keys generated before entropy has accumulated. In Myths About urandom this is described in great detail.

In my situation, my VM has not generated a sufficient amount of entropy for my taste at the point it boots and begins to start application servers. So, I need to find a way to get some entropy soon after boot up.

Testing for Entropy

For this experiment round I will be testing with VirtualBox running Ubuntu on a Macintosh.

On most Linux operating systems this command will show you the available entropy:

cat /proc/sys/kernel/random/entropy_avail

Note that every time you check the entropy using the command it will deduct some entropy bits from the pool.

To test for randomness I will be taking samples from the /dev/random pool with:

dd if=/dev/random of=random_output.txt count=8192

I may also sample /dev/urandom if the random generation software is slow in building entropy. This will produce a file full of random data.

ENT

The file will be tested using ENT A Pseudorandom Number Sequence Test Program, to gauge the quality of the entropy and measures of randomness. To use it, take the file from the previous dd command and give it to ent as a parameter. Ent will print out metrics ways to judge the randomness and entropy of the data in the file.

Rngtool

I will also use Rngtool to gain metrics on the throughput of the random generation tools.

cat /dev/random | rngtest -c 100

The Best Software

Now, the best software to use in order to keep your pool of entropy full. Well that depends on what operating system you are using and what platform you use to host your virtual machine.

Randomsound

Randomsound works by using the low order bit of the ADC output of your sound card.

I start out with less than 100 bits of entropy but after starting randomsound (sudo randomsound -D) for hours I only have 2652 bits of entropy. It is very slow. I am fairly confident it is not working with the virtual machine in getting to the sound card in the Macintosh. By running entropy_avail after performing typing and mouse movements the entropy did increase to 2830 bits.

So lets stop random sound with: sudo /etc/init.d/randomsound stop and try something else.

timer-entropy

This program is available at http://www.vanheusden.com/te/ where VanHeusden says:

“This program feeds the /dev/random device with entropy-data (random values) read from timers. It does this by measuring how much longer or shorter a sleep takes (this fluctuates a little – microseconds). The time for a sleep jitters due to that the frequency of the clocks of the timers change when they become colder or hotter (and a few other parameters). This program does not require any extra hardware. It produces around 500 bits per second.”
Once started it took about 2 minutes to generate 200 bits of entropy. I let it run to 3968 bits.

I ran dd if=/dev/random of=rand_timer_entropy.txt count=8192 to get a file of random data. Output:

^C0+111 records in
21+0 records out
10752 bytes (11 kB) copied, 255.934 s, 0.0 kB/s

ent rand_timer_entropy.txt reported:

Entropy = 7.979475 bits per byte.
Optimum compression would reduce the size of this 10752 byte file by 0 percent. Chi square distribution for 10752 samples is 306.62, and randomly would exceed this value 2.50 percent of the times. Arithmetic mean value of data bytes is 126.7684 (127.5 = random).
Monte Carlo value for Pi is 3.154017857 (error 0.40 percent).
Serial correlation coefficient is -0.001984 (totally uncorrelated = 0.0).

From Calomel.org I learned that the closer entropy is to 8 bits per byte is better. 7.979475 seems good. Optimum compression is good because the file will not compress which means there is no repeated data. The chi square distribution should be greater than 10% and lower than 90% according to Calomel.org. The timer_entropy failed here with a value of 2.5%. Also the arithmetic mean value is off by one this points to the file being not quite random. The best data will also have a Monte Carlo value of Pi almost equal to Pi. we are off by .4%. Serial correlation should be as close to zero as possible.

HAVEGEd

haveged is based on HAVAGE. HAVAGE stands for HArdware Volatile Entropy Gathering and Expansion. In summary, it works by timing the ticks of a processor between certain operations they call flutter. That is a gross oversimplification but there are four pages of explanation on the haveged website.

Entropy available is at 100 bits now.

sudo /etc/init.d/haveged start

Random Data

Within 10 seconds I have 3848 bits of entropy. So I collect my file of random data which runs in seconds. haveged is very fast at generating entropy. By the outputs below it looks to be around 3.8 MB/s

_dd if=/dev/random of=havegedentropy.txt count=8192
0+8192 records in
2047+1 records out
1048478 bytes (1.0 MB) copied, 0.274385 s, 3.8 MB/s
_$ cat /proc/sys/kernel/random/entropyavail
3968

And at the end the entropy pool is up to 3968 bits.

Ent reports the following:

_ent havegedentropy.txt
Entropy = 7.999847 bits per byte.
Optimum compression would reduce the size of this 1048478 byte file by 0 percent.
Chi square distribution for 1048478 samples is 223.14, and randomly would exceed this value 90.00 percent of the times.
Arithmetic mean value of data bytes is 127.4428 (127.5 = random).
Monte Carlo value for Pi is 3.138109027 (error 0.11 percent). Serial correlation coefficient is 0.000016 (totally uncorrelated = 0.0).

Second run:

Entropy = 7.999848 bits per byte. Optimum compression would reduce the size of this 1048434 byte file by 0 percent.

Chi square distribution for 1048434 samples is 220.87, and randomly would exceed this value 90.00 percent of the times. Arithmetic mean value of data bytes is 127.4005 (127.5 = random).
Monte Carlo value for Pi is 3.140752780 (error 0.03 percent).
Serial correlation coefficient is 0.000161 (totally uncorrelated = 0.0).

Third run:

_ent havegedentropy3.txt Entropy = 7.999779 bits per byte.
Optimum compression would reduce the size of this 1048505 byte file by 0 percent.
Chi square distribution for 1048505 samples is 321.04, and randomly would exceed this value 0.50 percent of the times.
Arithmetic mean value of data bytes is 127.6146 (127.5 = random).
Monte Carlo value for Pi is 3.137052933 (error 0.14 percent).
Serial correlation coefficient is -0.000989 (totally uncorrelated = 0.0).

Now these are better numbers. Entropy is higher and the rest of the values are closer to the goal. The chi square distribution is almost too high now. It is at 90% the first two runs but then drops to .5% on the final run.

The good thing about haveged is that it generates data very quickly and works on VirtualBox. According to Tom Leek on Security Stackexchange haveged needs access to the rdtsc instruction to get to the processors clock with sub-nanosecond precision. On VirtualBox this instruction is not virtualized. On VMware it is, so for haveged to work you need to configure VMware with:
monitor_control.disable_tsc_offsetting=TRUE

Rngtest

Using rngtest to verify the quality of haveaged yields the following results:

cat /dev/random | rngtest -c 10000
rngtest 5
Copyright (c) 2004 by Henrique de Moraes Holschuh This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. rngtest: starting FIPS tests…
rngtest: bits received from input: 200000032
rngtest: FIPS 140-2 successes: 9995
rngtest: FIPS 140-2 failures: 5
rngtest: FIPS 140-2(2001-10-10) Monobit: 1
rngtest: FIPS 140-2(2001-10-10) Poker: 0
rngtest: FIPS 140-2(2001-10-10) Runs: 3
rngtest: FIPS 140-2(2001-10-10) Long run: 1
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
rngtest: input channel speed: (min=1.322; avg=29.429; max=75.092)Mibits/s
rngtest: FIPS tests speed: (min=1.789; avg=133.068; max=171.833)Mibits/s
rngtest: Program run time: 7925437 microseconds

Second run

cat /dev/random | rngtest -c 10000
rngtest 5
Copyright (c) 2004 by Henrique de Moraes Holschuh This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

rngtest: starting FIPS tests…
rngtest: bits received from input: 200000032
rngtest: FIPS 140-2 successes: 9987
rngtest: FIPS 140-2 failures: 13
rngtest: FIPS 140-2(2001-10-10) Monobit: 2
rngtest: FIPS 140-2(2001-10-10) Poker: 2
rngtest: FIPS 140-2(2001-10-10) Runs: 3
rngtest: FIPS 140-2(2001-10-10) Long run: 6
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
rngtest: input channel speed: (min=1.537; avg=28.381; max=19073.486)Mibits/s
rngtest: FIPS tests speed: (min=1.803; avg=137.853; max=171.833)Mibits/s
rngtest: Program run time: 8116055 microseconds

Out of 20,000 tests I had only 18 failures.

rngd

Rngd-tools and the rngd command is not a tool to generate entropy. It is a program that takes randomness from a true random hardware device and puts it into /dev/random. These devices include OneRNG and trueRNG

oneRNG A True Random Generation Hardware Device

But we can use rngd to insert our own data file or data stream into /dev/random with this command:

sudo rngd -f -r [random data file]

Confirmed Random File

To see if we can get better randomness I will try to load data from RNG Research into our entropy pool. The data is generated from an outside source that is not a computer. They have tested the data with a tool called diehard and documented the entropy and randomness of the files. I am downloading block0.rng. Do not do this if you really want to use /dev/random to generate keys. This data is no longer unpredictable since it is public on the internet.

_$ cat /proc/sys/kernel/random/entropyavail
67
$ sudo rngd -r Downloads/block0.rng
_$ cat /proc/sys/kernel/random/entropyavail
3164
_$ dd if=/dev/random of=randfile.txt count=8192
0+8192 records in
1943+1 records out
_995134 bytes (995 kB) copied, 0.305225 s, 3.3 MB/s $ ent randfile.txt
Entropy = 7.999799 bits per byte.

Optimum compression would reduce the size of this 995134 byte file by 0 percent.

Chi square distribution for 995134 samples is 276.44, and randomly would exceed this value 25.00 percent of the times.

Arithmetic mean value of data bytes is 127.5281 (127.5 = random).
Monte Carlo value for Pi is 3.146266317 (error 0.15 percent).
Serial correlation coefficient is 0.000545 (totally uncorrelated = 0.0).

If this data is compared to the results from the other tools all of the tests above indicate that it is more random. Using a device outside of the computer to generate random entropy may be be best solution.

timer-entropy and haveged together

Now what happens if I combine methods. By mistake I left multiple methods running and noticed better results. With timer-entropy and haveged the results are:

Entropy = 7.999807 bits per byte.

Optimum compression would reduce the size of this 1048339 byte file by 0 percent.

Chi square distribution for 1048339 samples is 280.77, and randomly would exceed this value 25.00 percent of the times.

Arithmetic mean value of data bytes is 127.3958 (127.5 = random).

Monte Carlo value for Pi is 3.144199676 (error 0.08 percent).

Serial correlation coefficient is -0.000197 (totally uncorrelated = 0.0).

Results

Test randomsound timer-entropy haveged known random data timer-entropy & haveged
entropy = 8 N/A 7.979475 7.999847 7.999799 7.999807
chi square = 10%-90% N/A 2.50% 90% 25% 25%
Arithmetic mean = 127.5 N/A 126.7684 127.4428 127.5281 127.3958
Monte Carlo value for Pi N/A error 0.40% error 0.11% error 0.15% error .08%
Serial correlation = 0 N/A -0.001984 0.000016 0.000545 -0.000197
rngtest N/A N/A .09% failure .01% failure 0.05%
speed did not finish 23k/sec 3.8 MB/sec N/A 3.8 MB/sec

Conclusion

Getting random data is important to keeping secrets. At one time I thought this problem was solved but then virtualization became the best way to deploy new servers. When software ran on real hardware it was much easier to get sources to build entropy. Now virtual machine platforms are blocking access to the real world where randomness can be harvested.

It seems that the best way to get entropy may be connecting an external device dedicated to generating it for all the virtual machines being hosted. But from these experiments it could be that use of haveged and at least one other software method for gathering entropy might be the best option.

So in conclusion, I do not yet know the best software to generate random data and entropy. But hopefully this will point you in a beneficial direction.

Other Sources of Randomness

RDRAND

Computers with Intel CPU’s have a built in random data generator hardware on the Ivy Bridge Xeon processor. It is called with the RDRAND instruction set. There is a way to have rngd use it for populating the entropy pool /dev/random as documented in this case study. I am running on a MacBook which does not have the Xeon so it will not work.

Random.org

Random.org is a service on the internet where one can get random data. Random.org uses multiple sources of noise from the static from radios to feed into algorithms that produce random files for free.

Entropy in the News

Forbes Cloud Computing Security Technology

BBC – Web’s random numbers are too weak, researchers warn

Resources used

White Noise Boutique – (Art) a place to purchase random white noise.

https://en.wikipedia.org/wiki/Entropy_(computing))

http://spectrum.ieee.org/computing/hardware/behind-intels-new-randomnumber-generator

http://bredsaal.dk/improving-randomness-and-entropy-in-ubuntu-9-10

http://openfortress.org/cryptodoc/random/

http://www.randomnumbers.info/content/Generating.htm

https://blog.cloudflare.com/why-randomness-matters/

https://blog.mozilla.org/warner/2014/03/04/remote-entropy/

http://bredsaal.dk/improving-randomness-and-entropy-in-ubuntu-9-10

haveged as a source of entropy

Not-So-Random Numbers in Virtualized Linux and the Whirlwind RNG

0 replies

Leave a Reply

Want to join the discussion?
Feel free to contribute!

Leave a Reply

Your email address will not be published. Required fields are marked *