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 contents of this
buffer can be fed into the random device or accessed directly through the file
system. File system access is a useful alternative to those situations where
use of the random device is either inappropriate or not available.

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. In any case, the compiler has a
large role determining how HAVEGE operates in practice and any port of haveged
to a new environment should be fully tested before being put into production.
The build system provides "check" targets to test the output of the haveged
random number generator through the file system interface.

Online test options based upon the methodology from the proposed AIS-31 standard
from the German Federal Office for Information Security (Bundesamt für Sicherheit
in der  Informationstechnik) are provided in haveged as a final check of the output
of the random number generator. In its default configuration, haveged passes most
of the requirements for a NTG.1 class device described in version two of the
AIS-31 specification.

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.

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

The default host type is provided for those systems without user level access to
a high-resolution system timer. In this case, clock_gettime(CLOCK_MONOTONIC)
is used as the timer source. In this case, extended testing is recommended before
putting this configuration into service using the build check targets and/or
use of the online test facilities to verify correct operation.

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 on the command line.

Under most circumstances, the default tuning will suffice and manual overrides are
unnecessary.

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

1.  --enable-capture (diagnostic)
2.  --enable-daemon (default for Linux)
3.  --enable-init (type)
4.  --enable-inject (diagnostic)
5.  --enable-olt (recommended default)
6.  --enable-nistest (recommended)
7.  --enable-threads (experimental)

If options capture or inject are enabled, or the daemon option is disabled,
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 the daemon option defaults
to "enabled" if the host operating system for the build is Linux and disabled
otherwise.

The daemon interface requires access to the random device and the /proc virtual
file system as well as the ability to fork into the background. The daemon
interface targets the 2.6 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 daemon interface includes an init method to start the daemon at system boot.
The sysV mechanism is used by default. The enable-init method specifies a template
to be used for the init script. A simple naming convention indicates if the
template will be used to install a traditional systemv init script ("haveged")
or a systemd unit definition ("haveged.service"). In the latter case, pkg-config
is required by the install target. See INSTALLATION for details.

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.

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 online test facility does require additional resources and for systems with
a limited resource budget, the enable-olt build switch can be used to suppress
the entire online test facility.

The build system provides two additional test mechanisms for the haveged random
number generator within the build system. The tests are implemented by by
ent/test.sh and nist/test.sh. By default, only the ent/test.sh test is performed.
The other test must be enabled with the configure option "-enable-nistest"
to ensure so that both tests are executed by the check target:

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.


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 case, 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 mechanism 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.

The threads option is a 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.


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: tb"

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 displays build and tuning information:

haveged: version: 1.5; arch: x86; vendor: GenuineIntel; cores: 1/1, buffer: 128
haveged: d_cache: 32K (000020), i_cache: 32K (000020), i_index: 20/40, i_size: 31756/62345
haveged: tot tests: B, continuous tests:

Sources displayed in parenthesis are bit values indicating where the tuning
information was found:

0x00001          Default value
0x00002          Invocation parameter
0x00004-0x00020  Cpuid functions available
0x00040          Virtual file system available
0x00100-0x02000  Cpuid detail
0x04000-         Virtual file system detail

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

0x01             Adds build/tuning display and testing summary to any run
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.




INSTALLATION

If the daemon interface is not enabled, the install places the executable in
the bin directory and provides a man(8) page. It the daemon interface is enabled,
the executable is installed in the sbin directory and the daemon startup is
enabeled at system boot.

A simple template system is used to setup the init method. The template must
reside in the init.d build directory and is selected by the --enable-init build
option. Template names "service.*" indicate that a systemd style init, while
templates with other style names ("sysv.*" recommended) are used for sysv
style init scripts.

Examples:

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

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


EXTRAS

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


