Sooner or later you begin creating or using random data, for a multitude of reasons:
- create ssh and PGP keys
- create certificates
- do financial simulations
- feed your tests with loads of data
- brute-force-attacks during penetration testing and ethical hacking
- inside a game engine to add variations
and many, many more. The opposite of randomness is certainty which leads to a philosophical question: isn't it interesting that much of our success depends on randomness while we are constantly striving for certainty?
I think while we talk about randomness and random data, we do need limited randomness: inside specific boundaries and with certain qualities.
For example, if you want to simulate to roll a dice, you clearly need a random data source which emits two distinct values. What you also want is randomness regarding the distribution of these values over all trials. That means you don't want to be able to identify patterns (at best, random data is undisguisable from noise, as encrypted data should be).
And in testing, you need lots of data!
So you have basically two options:
- cryptographically secure random number generation
- cryptographically insecure random number generation
Most of the time you might want to test general purpose functionality with no requirements for cryptographically secure random data. If you need to create a few thousand data sets simulating user's personal data it does not matter that much, if names or characters in streets repeat. And testing crypto-software is something which should only be done by experts in this fields (as you should never implement cryptography on your own not beeing an expert).
Most programming languages offer you appropriate functions and methods for both types of random numbers.
So, why bother?
The problem lies in the performance or the number of random numbers which can be generated per time unit. And to be precise: in the performance of the cryptographically secure random number generation. Its performance relies on the so-called entropy pool, where all available random event sources provide additional data to generate data in that entropy pool. New numbers are only generated when the pool is large enough. The Linux kernel has normally three sources for new random data: the input layer, interrupt data and disks. You might think that a decent Linux server should have plenty of events from these sources, but it does only add very specific data to the pool.
Quote (1) from random.c:
* add_disk_randomness() uses what amounts to the seek time of block * layer request events, on a per-disk_devt basis, as input to the * entropy pool. Note that high-speed solid-state drives with very low * seek times do not make for good sources of entropy, as their seek * times are usually fairly consistent.
And high-speed SSDs are not that uncommon nowadays. So high IO is no guarantee for fast random.
Quote (2) from random.c:
* add_interrupt_randomness() uses the interrupt timing as random * inputs to the entropy pool. Using the cycle counters and the irq source * as inputs, it feeds the randomness roughly once a second.
Once (!) a second, that is not very fast.
Quote (3) from random.c:
* add_input_randomness() uses the input layer interrupt timing, as well as * the event type information from the hardware.
Yes: type faster, dude! We need more entropy!
You could ask: aren't there more event sources? Sure, but the question is always the same: is it really a source of high quality randomness?
So a few days ago I came across exactly that situation:
a Java-based test ran fast for the first run, each consecutive run was delayed for 2-3 minutes. It was a mid-sized server with a large number of CPUs and only SSDs and no one typing on the console (a typical headless one), the Jenkins server.
The test data was generated using Java's default random class, which turned out to use data from /dev/random by default, which is feed by the Linux kernels entropy pool. After the first test, the pool went empty and the next ones delayed by several minutes. This was repeatable: trigger Jenkins build job and watch tests getting stuck after the first one.
The differences in performance of /dev/random vs. /dev/urandom:
# urandom dd if=/dev/urandom of=/dev/null bs=1 count=10M 10485760+0 records in 10485760+0 records out 10485760 bytes (10 MB, 10 MiB) copied, 10.6776 s, 982 kB/s # random dd if=/dev/random of=/dev/null bs=1 count=10M 10485760+0 records in 10485760+0 records out 10485760 bytes (10 MB, 10 MiB) copied, 852.927 s, 12.3 kB/s
12.3 kB/s - that hurts ... but it can be explained (see above).
So there were basically two options:
- force Java to use a pseudo number generator which does not rely on /dev/random
- make pseudo number generation faster
To make Java use something else than/dev/random is easy: you need to adjust the file jre/lib/security/java.security and set securerandom.source. By default it is set to securerandom.source=file:/dev/random, which is the feed by the entropy pool and possibly blocking when no more random values are available. To use the non-blocking random source set it to securerandom.source=file:/dev/urandom.
The Linux manpage for random states:
The /dev/random interface is considered a legacy interface, and /dev/urandom is preferred and sufficient in all use cases, with the exception of applications which require randomness during early boot time; for these applications, getrandom(2) must be used instead, because it will block until the entropy pool is initialized.
In our case, the consumers are Java processes that are started by Jenkins, so there is no requirement for the randomness during early boot time.
If you are curious and want to know how much random data is currently available in the entropy pool just issue this command:
Every number lower than 1.000 can be considered too low for normal operation; if you request more data than available the requesting process will block.
To speed up the generation of random data means to add a performant event source for the entropy pool. Such a source needs to generate data with a certain quality and independent from things like user input or disk movements: it must be reliably available even under cloud conditions, e.g. headless operations which are some of a norm today.
One way to do that is to use more data which is rather random and available in higher amounts: statistics of CPU instruction execution. There is an algorithm which was designed to leverage from this, HArdware Volatile Entropy Gathering and Expansion (HAVEGE, details are here). As the execution time for instructions are not predictable due to a large number of optimizations and environment conditions (process switching, cache hits and misses, memory access etc.), this source is able to generate high-quality random data at high rates. The original paper talks about several hundred megabits per second.
Luckily there is an Open Source implementation available haveged.
Your package system should be able to provide a version if:
apt install haveged
should do the work on Debian or Ubuntu systems.
As soon as it is running you should be able to see an increase in the performance of random number generation as here:
dd if=/dev/random of=/dev/null bs=1 count=10M 10485760+0 records in 10485760+0 records out 10485760 bytes (10 MB, 10 MiB) copied, 32.7755 s, 320 kB/s
Here we can see the performance jump roughly by a factor of 25.
I was curious about the usage of entropy in the system and just issued this to watch:
while true ; do echo $(date) : $(cat /proc/sys/kernel/random/entropy_avail) ; sleep 1 ; done Tue Mar 12 13:44:20 CET 2019 : 2900 Tue Mar 12 13:44:21 CET 2019 : 2907 Tue Mar 12 13:44:22 CET 2019 : 2915 Tue Mar 12 13:44:23 CET 2019 : 2920 Tue Mar 12 13:44:24 CET 2019 : 2927 Tue Mar 12 13:44:25 CET 2019 : 2932 Tue Mar 12 13:44:26 CET 2019 : 2939 Tue Mar 12 13:44:27 CET 2019 : 2951 Tue Mar 12 13:44:28 CET 2019 : 2952 Tue Mar 12 13:44:29 CET 2019 : 2956 Tue Mar 12 13:44:30 CET 2019 : 2958 Tue Mar 12 13:44:31 CET 2019 : 2963 Tue Mar 12 13:44:32 CET 2019 : 2967 Tue Mar 12 13:44:33 CET 2019 : 2974 Tue Mar 12 13:44:34 CET 2019 : 2981 Tue Mar 12 13:44:35 CET 2019 : 2991 Tue Mar 12 13:44:36 CET 2019 : 2994 Tue Mar 12 13:44:37 CET 2019 : 3003 Tue Mar 12 13:44:38 CET 2019 : 3005 Tue Mar 12 13:44:39 CET 2019 : 3012 Tue Mar 12 13:44:40 CET 2019 : 3014 Tue Mar 12 13:44:41 CET 2019 : 3019 Tue Mar 12 13:44:42 CET 2019 : 3023 Tue Mar 12 13:44:43 CET 2019 : 3026 Tue Mar 12 13:44:44 CET 2019 : 3027 Tue Mar 12 13:44:45 CET 2019 : 3035 Tue Mar 12 13:44:46 CET 2019 : 3036 Tue Mar 12 13:44:47 CET 2019 : 3045 Tue Mar 12 13:44:48 CET 2019 : 3050 Tue Mar 12 13:44:49 CET 2019 : 3052 Tue Mar 12 13:44:50 CET 2019 : 3055 Tue Mar 12 13:44:51 CET 2019 : 3058 Tue Mar 12 13:44:52 CET 2019 : 3061 Tue Mar 12 13:44:53 CET 2019 : 3064 Tue Mar 12 13:44:54 CET 2019 : 3066 Tue Mar 12 13:44:55 CET 2019 : 3074 Tue Mar 12 13:44:56 CET 2019 : 3078 Tue Mar 12 13:44:57 CET 2019 : 3084 Tue Mar 12 13:44:58 CET 2019 : 3087 Tue Mar 12 13:44:59 CET 2019 : 3090 Tue Mar 12 13:45:00 CET 2019 : 3095 Tue Mar 12 13:45:01 CET 2019 : 3102 Tue Mar 12 13:45:02 CET 2019 : 3108 Tue Mar 12 13:45:03 CET 2019 : 3112 Tue Mar 12 13:45:04 CET 2019 : 3114 Tue Mar 12 13:45:05 CET 2019 : 3119 Tue Mar 12 13:45:06 CET 2019 : 3122 Tue Mar 12 13:45:07 CET 2019 : 3129 Tue Mar 12 13:45:08 CET 2019 : 3130 Tue Mar 12 13:45:09 CET 2019 : 3135 Tue Mar 12 13:45:10 CET 2019 : 3136 Tue Mar 12 13:45:11 CET 2019 : 3139 Tue Mar 12 13:45:12 CET 2019 : 3142 Tue Mar 12 13:45:13 CET 2019 : 3144
You can see here a constant need for random data in the system.
If you need more random data you probably need dedicated hardware.
Happy hacking :-)