Encryption Entropy
Nate Drake guides you through the chaotic topic of increasing randomness to secure your system. Don’t forget to plug in your lava lamp while you’re at it.
Nate Drake guides you through the chaotic topic of increasing randomness to secure your system. Don’t forget your lava lamp!
What do a lava lamp, waste paper basket and a smoke detector have in common? Aside from being readily available from your nearest bachelor pad, they’ve all played a role in increasing entropy, or randomness by any other name. Generating truly unpredictable bits of data lies at the heart of key operations such as reliably encrypting web traffic. In this guide, we’ll explore how Linux manages entropy to produce good-quality random data, as well as ways for you to increase and test the available entropy on your system.
The war on entropy
Currently, there’s no method to prove definitively that a certain data stream is entirely random. However, you can prove data to be non-random under certain circumstances. By way of example, while writing this article the author rolled two unbiased six-sided dice to give the results 2-5 (total seven). Superficially, the sum of these numbers can appear random because there was no way to predict each die roll in advance. However, they can’t be said to be truly unpredictable as the sum of two dice is more likely to be seven (17 per cent) than any other value.
For this reason in 1890, the Victorian statistician Francis Galton was able to create a system to generate random numbers by drawing three custom six-sided dice from a wastepaper basket without looking. (See http://galton.org/ essays/1890-1899/galton-1890-dice.pdf for a full rundown of his methods).
In the 21st century, DNS company CloudFlare certainly deserves recognition for the creative ways it attempts to feed random number generators in its systems, one of which includes using cameras to track the moving blobs of wax inside the lava lamps. While the heat currents that move the lava aren’t completely unpredictable, the camera recording the lamps also registers ambient noise and light, helping to encrypt keys for around 10 per cent of the traffic that’s used in Cloudflare’s network.
If a random number generator doesn’t function properly however, the consequences can be disastrous. In August 2017, programmers Dan Shumow and Niels Ferguson outlined their findings that the Dual EC PRNG developed by the NSA in the early 2000s and approved by NIST generated random numbers in a potentially insecure way.
Human error also plays its role in weakening randomness. In 2008 the Debian project announced that a well-meaning developer had removed two lines of code from the OpenSSL package it was distributing. This had the side-effect of crippling the PRNG (pseudo random number generator) used by OpenSSL, which reduced the potentially limitless number of SSL/SSH keys that it can generate to just 32,767.
Anatomy of a RNG
Cryptographic keys are created using a CSPRNG (Cryptographically secure pseudo-random number generator) seeded with a good supply of random data are extremely hard to brute force. Linux maintains an entropy ‘pool’ that’s collected from a number of sources ( seebelow). The data goes through a process of de-biasing to remove predictable bits, then is fed to a CSPRNG. The CSPRNG in turn seeds an entropy pool that can be utilised via the device file /dev/random. For instance, to generate a 1MB file containing random data exclusively drawn from the entropy pool, open Terminal and run the following: dd if=/dev/random of=test bs=1M count=1 iflag-fullblock
If the pool doesn’t contain enough random bits to create your chosen file it will ‘block’ until more entropy becomes available. You may have encountered this before when generating a GPG/SSH key on your machine. Usually, the utility in question encourages you to keep on using your computer to enable it to collect randomness from running processes, key presses and so on.
While this is fine for desktop machines, if you’re running a server then ‘blocking’ can cause issues because they’re usually run headlessly.
To circumvent this issue, applications can instead draw upon /dev/urandom, which provides a non-blocking source of pseudo-randomness. While previously t maintained a separate entropy pool, as of Linux 4.8 it now draws random values directly from the CSPRNG, which currently uses a
variant of the ChaCha20 stream cipher to continually generate pseudo-random bits based on an initial random seed.
The Holy Seed
The online debate about the relative merits of /dev/random vs /dev/urandom is as frenzied as it is entertaining. The general consensus is that /dev/urandom is probably secure for most cryptographic purposes – provided that the initial bits used to seed it are sufficiently random.
In the case of /dev/urandom each ChaCha20 instance is reseeded every five minutes, although the randomness of data obtained from this will be different on a system that’s virtualised and/or headless. Randomness is often collected via prompts from hardware devices such as a hard disk sending requests to the OS (known as interrupts), although with the advent of SSDs these are also fewer and further between.
One possible workaround for this is to install Haveged, which is available in both the Debian and Ubuntu reposotories. Haveged is specifically designed for low-entropy situations like those outlined above. The haveged implementation seeds /dev/random using differences in your processor’s time stamp counter (TSC) after executing a loop repeatedly. Because instructions take different times to run and are executed at different times, this can generate a fair amount of entropy.
To get started simply install it by opening Terminal and running sudo apt-get install haveged . Make sure to add Haveged to your system startup processes by running update-rc.d haveged defaults too.
If your PC is relatively recent, Haveged may be surplus to requirements as all Intel Ivy Bridge and AMD64 CPUs since 2015 have an on-chip hardware random number generator. In September 2013, Theodore Ts’o, the creator of /dev/random, noted that relying solely on CPUs like these to generate entropy leaves systems open to government-mandated backdoors. As of Linux kernel 3.16 however, the system mixes entropy gained from hardware devices into /dev/random, so randomness doesn’t come exclusively from one source.
Super paranoid readers can also find instructions online to build your own hardware RNG, which measures quantum events such as from Geiger counters or smoke detectors.
Testing randomness
As you’ve previously learned, it’s impossible to prove any sequence of data bits are truly random. There are, however, some utilities which may indicate data isn’t truly random. The easiest one to interpret is rngtest that’s part of the rng-tools package (see box, above, to install this). Once installed open Terminal and run cat /dev/random | rngtest -c 1000 using FIPS (Federal Information Processing Standard) 140-2 tests. If the number of failures relative to successes is greater than one per cent then the data is probably not random. Consider installing ent, which can run further tests on your data, such as the chi-squared distribution and the Monte Carlo value for Pi. Above all, remember that the best-quality randomness comes from a variety of sources.