Haveged

Haveged, an entropy source

IMPORTANT UPDATE

Starting from Linux kernel v5.4, the HAVEGED inspired algorithm has been included in the Linux kernel (see the LKML article and the Linux Kernel commit). Additionally, since v5.6, as soon as the CRNG (the Linux cryptographic-strength random number generator) gets ready, /dev/random does not block on reads anymore (see this commit).

I'm happy that these changes made it into the mainline kernel. It's pleasing to see that the main idea behind HAVEGED has sustained time test - it was published already in 2003 here. I'm also glad that the HAVEGE algorithm is being further explored and examined - see the CPU Jitter Random Number Generator.

Please note that while the mainline Linux Kernel and HAVEGED are using the same concept to generate the entropy (utilizing the CPU jitter) the implementation is completely different. In this sense, HAVEGED can be viewed as another entropy source.

It means that HAVEGED service is now less relevant. However, it's still useful in the following situations, when you

• need randomness early in the boot process, before the CRNG in the Linux kernel gets fully initialized.
• want to deploy an additional entropy source. HAVEGED now inserts entropy into the kernel every 60 seconds, regardless of the entropy level reported by Linux Kernel. It does not affect the /dev/random read speed but it diversifies the entropy sources, making the Linux Kernel CRNG more robust.
• you are looking for userspace RNG to generate random numbers. See man -S8 haveged for examples or try running haveged -n 0 | pv > /dev/null
• and last but not least, most Linux installations are still running on the older kernel versions.

In any case, I will keep maintaining the HAVEGED project. The userspace application, as well as the haveged library, are not affected in any way by changes in the Linux kernel.

INTRODUCTION

Complete documentation on haveged can be found at http://www.issihosts.com/haveged/

Linux provides device interfaces (/dev/random and /dev/urandom) to a pool of random numbers collected from system interrupt service routines. On some systems, especially on those systems with high needs or limited user interaction, the standard collection mechanism cannot meet demand. In those cases, an adequate supply of random numbers can be maintained by feeding additional entropy into /dev/random pool via a file system interface. The haveged daemon was created to fulfill this function using random data generated by the HAVEGE algorithm.

The HAVEGE algorithm is based upon the indirect effects of unrelated hardware events on the instruction timing of a calculation that is sensitive to processor features such as branch predictors and instruction/data access mechanisms. Samples from a high-resolution timer are input into the algorithm to produce a stream of random data in a collection buffer. The algorithm requires no special privilege other than access to a high resolution timer, as provided by hardware instruction or a system call.

The HAVEGE mechanism is implemented in C using in-line assembly only where direct hardware access is needed. On modern compilers, compiler intrinsics are used to replace much if not all in-line assembly. The haveged implementation of HAVEGE adds two crucial features: automated tuning of the algorithm to an environment and a run time facility to verify the data generated in the collection buffer.

The haveged collection loop is tuned at run-time to match the size of the hosts L1 data and instruction caches. The size determination is made on the basis of the best fit to the following (low to high):

1. as a compiled default
2. as determined by cpuid, if available
3. as determined by the /sys file system, if available
4. as specified by initialization parameters.

Run-time verification of collection buffer contents is based upon the methodology from the proposed AIS-31 standard from BSI, the German Federal Office for Information Security (Bundesamt für Sicherheit in der Informationstechnik). In the suggested configuration, haveged passes most of the requirements for a NTG.1 class device described in version two of the AIS-31 specification.

The haveged implementation also provides an experimental feature to multiplex havege collections over multiple cpu cores. Interprocess coordination in this configuration sacrifices a significant fraction of haveged throughput in exchange for a cpu load spread over a number of processors.

All of the above features are contained within the haveged-devel sub package of haveged. The haveged package can be built with libtool to expose the devel sub package or without libtool if the devel library is not needed. In either case, the executable built contains a file system interface to haveged-devel features and an optional facility to feed havege output into the random device. The build system also provides "check" targets to test the output of the executable's random number generator through the file system interface.

TESTING haveged

Testing via build check targets has been part of the haveged distribution since the project moved to automake. Original tests were limited to a quick evaluation implemented as an adaptation of the open source ent tool from Fourmilab and a more thorough evaluation based upon the NIST SP800 test suite. Run time testing was added to haveged version 1.5 as part of an effort to loosely follow the RNG testing AIS-31 framework of the German Common Criteria organization, BSI.

The significant features of the AIS-31 framework are:

Run-time tests are broken into 2 groups, Procedure A containing 5 tests, and Procedure B containing 3 tests. Procedure A consists of performing a 48-bit disjointedness test on 64K sequences, followed by 257 repetitions of the four FIPS-140-1 tests and an auto-correlation test on successive 2000 bit sequences. Procedure B performs distribution tests for 10,000 occurrences of 1, 2, 3, 4 bit runs in successive samples, followed by a entropy estimate based upon on another 256000+2560 bit sample. A sample must pass all individual tests to pass the procedure. An ideal RNG is expected to pass Procedure A with a probability of 0.9987 and pass Procedure B with with a probability of 0.9998. One retry will be attempted to recover from the the failure of a single test in either procedure. The probability an ideal generator would fail the retry is nill.

Special features of the haveged implementation:

1. A failure of either procedure is a fatal error. In the case of haveged, the instance will terminate.
2. The tests operate directly on the collection buffer after a fill. Performance costs are acceptable except for the auto-correlation test, test5. An option to skip test5 on some repetitions mitigates this problem.
3. Tests can take place at start up (a "tot" test) or continuously as specified by a haveged parameter. In the continuous case, there is no implied alignment between the collection buffer and the testing context. Collection buffer contents will be released for consumption provided the buffer does not contain a failed individual test.
4. The size of the input required to complete procedure B depends on the content. This means there is no fixed alignment of the test input in the collection buffer.
5. Procedure retries are logged. Extended information is available with -v3. Retries are expected (see failure rates above) but normally only seen with output ranges north of a few GB.

More detailed information on the adaptation of the BIS framework can be found at http://www.issihosts.com/haveged/ais31.html

BUILDING haveged

This package originated on "Enterprise Linux 5" systems (RHEL 5 / CentOS 5 / SL 5), but every effort has been made to retain and broaden the hardware support of the original HAVEGE implementation. The package uses the automake build system. By default, the build uses a libtool build to expose haveged-devel. The contrib/build directory contains a build.sh script to toggle the libtool requirement and recover from some autotools failures. Change directory to the build directory and type ./build.sh for options.

The configure process uses hardware detection via config.sub or the configure "-host" command line argument. The configure "host" variable is used to select in-line assembly or compiler intrinsics appropriate to the build target.

Currently supported hosts are:

1. x86
2. ia64
3. powerpc
4. s390
5. sparc
6. sparclite
7. generic

The generic host type is provided for those systems without user level access to a high-resolution system timer. In this case, the --enable-clock_gettime option is set to 'yes'.

The following build options are available to "./configure":

1. --enable-clock_gettime (default 'no' for recognized hosts)
2. --enable-daemon (default 'yes' if Linux)
3. --enable-diagnostic (default 'no')
4. --enable-nistest (default 'no' but recommended)
5. --enable-olt (default 'yes')
6. --enable-threads (experimental)
7. --enable-tune (default 'yes')

Detailed option information is available by typing "./configure --help". For options xxx that take "yes/no" arguments, --disable-xxx may be used as the inverse of --enable-xxx.

If --enable-clock_gettime() is 'yes', the clock_gettime(CLOCK_MONOTONIC) system call will be used as a timer source. This option defaults to 'yes' for generic host builds and 'no' otherwise. This option may proved useful if access to time hardware is privileged. Due to variability of clock_get