Haveged, an entropy source

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, 4, 8 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. One retry will be attempted to recover from the the failure of a
single test.

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 resolves 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.

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-capture (diagnostic)
2.  --enable-clock_gettime (not normally needed)
3.  --enable-daemon (default for Linux)
4.  --enable-init (type)
5.  --enable-inject (diagnostic)
6.  --enable-nistest (recommended)
7.  --enable-olt (recommended default)
8.  --enable-threads (experimental)

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-capture or --enable-inject are 'yes', or --enable-daemon is 'yes',
haveged will build without the daemon interfaces (i.e. only file system access
will be available). The install target will install the executable in the user
bin directory and no init method will be configured. If --enable-capture and
--enable-inject are both 'no', --enable-daemon defaults to 'yes' if the host
operating system is Linux and 'no' otherwise.

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_gettime() implementations,
the adequacy of the clock_gettime() resolution cannot be known until run time. 

If --enable-daemon is 'yes', ioctl access required to the random device and
read-write access to the /proc virtual file system is required. The daemon may
be run in the foreground or fork into the background based upon a command line
argument. The daemon interface targets the 2.6 and later kernel and may not work
on 2.4 kernels due to difference in the random interface between those two
kernel versions. The change in the proc file system from pool size expressed in
bytes to pool size expressed in bits has been taken into account, other changes
may be required.

The --enable-init option is active only when --enable-daemon is 'yes'. This
value can specify a template to be used in the installation of an init method
by the build's install target. The default value, 'none', disables the feature.
Other values can be used to install a traditional systemv init script or
systemd unit definition. In the latter case, pkg-config is required by the
install target. See INSTALLATION for details.

The --enable-olt option is provided to suppress the entire online test facility.
This option is provided for systems with a very limited resource budget and the
ability to thoroughly test the RNG output by other means. The online test system
tests the output of the haveged random number generator using AIS-31 test
procedures A and B. Either or both tests may be run as a total failure check (a
"tot" test) at initialization and/or continuously during all subsequent haveged
operation - See the man page and the description at
http://www.issihosts.com/haveged/ais31.html for further information.

The --enable-threads option is an experimental prototype for running multiple
collection threads in a single haveged instance. The goal is to create a
multi-core haveged that would spread collection overhead more evenly over the
available cpu resources.

The --enable-nistest option enables more thorough testing for the check target.
The build system provides to test mechanisms:

1. A "quick" check based upon and adaptation of the public domain ENT program.
   The "entest" program uses the ENT sources to subject a sample to the following:

    a) The Chi-Square result must fall within acceptable bounds (>1% and <99 %)
    b) The entropy/character must exceed a minimum (7.5)
    c) The arithmetic mean must exceed a minimum (127.0)
    d) The monte-carlo approximation of PI must lie within error bounds (.5%)
    e) The Sequential Correlation Coefficient must be below a minimum (.8)

   The program provides a pass-fail indication and an optional display of the
   results to stdout.

2. An adaptation of the NIST Statistical Test Suite as adapted by Oliver
   Rochecouste of irisa.fr as part of the original havege project. More that 400
   tests are performed in a typical run. The program provides as pass-fail
   indication with detailed results reported in the nist.out file in the
   nist directory.  You will need sit down with SP800-*.pdf available from the
   NIST to review the detailed results.
   
The "quick" test is always part of the check target. The NIST suite is run only
when --enable-nistest is 'yes'.

Both scripts function the same way, haveged is run to collect a sample file in
the test directory which is then analyzed by the test program. A pass-fail return
is given in both cases, additional information is written to stdout. The input
samples and the nist.out report are deleted by the clean make target.

The tests can also executed from a shell prompt at any time after "make check" by
executing ent/test.sh or nist/test.sh from the build directory. Command arguments
to the script are passed on to the haveged invocation, this allows the sample
size to be adjusted via "-r" or cache sizes to be specified via "-d" and "-i".

Both test mechanisms are statistical and even a fully functional random number
generator will experience occasional failures. It is not uncommon to see one or
two failures in the NIST suite and the entest will occasionally fail with a small
sample size (usually the Chi-Square test barks). Early haveged releases used a
entest sample size of 1MB, this has been increased to 16MB because failures with
that sample size were all too common. A 16MB sample will also deplete and refill
the haveged collection area to exercise all buffer logic.


RUNNING haveged

The following invocation arguments are always available:

   --buffer     , -b [] Buffer size [KW] - default : 128 (512KB)
   --data       , -d [] Data cache size [KB]
   --inst       , -i [] Instruction cache size [KB]
   --file       , -f [] Sample output file - default: 'sample', use '-' for stdout
   --number     , -n [] Write to file, units can be k, m, g, t. Use 0 for unlimited
   --verbose    , -v [] Output level 0=minimal,1=info,<diagnostics>
   --help       , -h    This help

If haveged is built with online testing enabled, the following is present

   --onlinetest , -o [] [t<x>][c<x>] x=[a[n][w]][b[w]] 't'ot, 'c'ontinuous, default: ta8b"

The default configuration executes the "tot" test using AIS procedure B. At the completion
of the tot test, the buffer is reloaded and any continuous tests will be run before
data becomes available.

If haveged is built with threads support, the following is present

   --threads    , -t [] Number of threads

If daemon interface is enabled the following options are available:

   --Foreground , -F    Run daemon in foreground, do not fork and detach,
   --pid        , -p [] The location of the daemon pid file, default: /var/run/haveged.pid
   --run        , -r [] 0=daemon,1=config info,>1=Write <r>KB sample file
   --write      , -w [] Set write_wakeup_threshold [bits]

The "-b", "-d", "-i" options are needed only in special cases. Generator output
should be validated after changes to these values.

Non-zero "-r" options are used to test the haveged random number generator; The
random number generator will be configured, the initial data collection pass
will be executed, configuration details will be written to stdout, and a "-r"
KB sample of output will be written to the sample output file for all "-r" > 1.
The "-n" option provides a more friendly version of r > 1. If the daemon interface
is not enabled, the run value option is not available and defaults to 1.

Output for r=1, v=1 displays build, tuning, and execution information:

haveged: ver: 1.7; arch: x86; vend: GenuineIntel, opts: (<opts>); collect: 128K
haveged: cpu: (<tune>);data: 32K (<tune>); inst: 32K (<tune>); idx: 19/40; sz: 32685/61064
haveged: tot tests: <spec>; continuous tests: <spec>
haveged: fills: 0, generated: 0

where
    ver:     build: package version
    arch:    build: architecture: ia64, generic, ppc, s390, sparc, sparclite, x86
    vend:    exec:  vendor string of host from cpuid if available
    opts:    build: option list: C=clock_gettime, M=multi-core, T=online tests
    collect: exec:  collection buffer size
    cpu:     tuning: (sources list for cpu info)
    data:    tuning: size, (sources list for L1 data cache)
    inst:    tuning: size, (sources list for L1 instruction cache)
    idx:     tuning: collector loops used/collector loops available
    sz:      tuning: collector size used/collector size available.
    <spec>   exec: tests executed

tuning sources are:
    D=default value, P=instance parameter, C=cpuid present,
    H=hyperthreading, A=AMD cpuid, A5=AMD fn5, A6=AMD fn6, A8=AMD fn8
    L2=Intel has leaf2, L4=Intel has leaf4, B=Intel leaf b,
    4=intel leaf4, V=virtual file system available
    VS=/sys/devices/system/cpu/cpu%d/cache/index<n>/level,
    VO=/sys/devices/system/cpu/online, VI=/proc/cpuinfo
    VC=/sys/devices/system/cpu

Sources displayed in parenthesis are white separated lists of the above tokens. The
"collector * used/collector *available" values indicate the fit of the haveged
collection loop to the L1 instruction cache.

The <spec> fields list the online test specification string followed by <pass>/<fail>
counts for the A and B test procedures. If the B procedure has been run the summary
will show the last entropy estimate (Coron's test). See TESTING section above for
more information.

The "-v" option also uses a bit mask to obtain additional diagnostic information

0x01             Adds build/tuning display
0x02             Show test details
0x04             Show timing for collections
0x08             Show collection loop characteristics
0x10             Show code offsets.

The "-w" option will set proc/sys/kernel/random/write_wakeup_threshold to the
given value. This is useful because this threshold is very small on some systems.
A minimum of 1024 is recommended.

The file system interface supports file creation of up data setups up to 16tb or
can be part of a piped command set. See the man file for examples.

INSTALLATION

If the daemon interface is not enabled, the install places the executable in
automake's bin_PROGRAMS directory and provides a man(8) page. A man(3) page
is provided for the libtool build It the daemon interface is enabled, the
executable is installed in automake's sbin_PROGRAMS directory.

If the daemon interface is enabled, the enable-init setting provides a simple
template system is to setup the init method. If enable--init is set to none
no action is taken. Otherwise, the template must reside in the init.d build
directory and is selected by the setting. Template names "service.*" indicate
that a systemd style init, while template names "sysv.*" are used for sysv
style init scripts.

Examples:

./configure --enable-init=service.redhat
./configure --enable-init=sysv.lsb

The default setting is "none". Custom init scripts can be added as necessary
by adding templates to init.d.

A sample file, haveged.spec, is provided in the build root as a guide for
those who want to build a rpm. As with init scripts, the sample may need
customization before use. A more complete SPEC file example, fedora.spec,
can be found in the contrib directory.


EXTRAS

The contrib directory contains bits and pieces that are not integrated into the
distribution. Currently this directory contains build related uitilies in
the build directory and an unorganized collection of some of the tools used
to analyze haveged in the diags directory.

The script contrib/build/build.sh organizes the build utilities. The script
provides methods to toggle the use of libtool in the build in particularly
problematic environments, a bootstrap to recover from automake error states
and the option to build and run a devel sample program after the devel
sub package has been built.