Haveged, an entropy source

INTRODUCTION

Complete documentation 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, a minimum supply of random numbers can be maintained by feeding
additional entropy as needed 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 allows validation of the data stream and is a useful
alternative to those situations where use of the random device is inappropriate.

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.

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 intrisics 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. A weak timer sanity check is performed during haveged
setup but this is insufficient to guarantee adequate timer resolution and extended
testing is recommended before putting this configuration into service. 

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-inject (diagnostic)
4.  --enable-nistest (recommended)
5.  --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). If the daemon option is 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 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 package provides two test mechanisms for the haveged random number generator
The tests are performed within the build system by ent/test.sh and nist/test.sh.
By default, only the ent/test.sh is performed. The NIST test suite can be enabled
as a check target with the configure option "-enable-nistest" 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 [KB] - default : 128
   --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

It 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 [] 0=background daemon,!=0 remain attached,
   --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:

version:     1.4               // haveged version                     
arch:        x86               // host build type                     
vendor:      GenuineIntel      // if known                            
cores:       1/1               // threads used/threads enabled         
buffer:      128K              // collection buffer size              
i_cache:     12K (000010)      // instruction cache size (source)     
i_index:     20/40             // instruction blocks used / available 
i_size:      31766/62351       // instruction bytes used / available  
d_cache:     16K (000051)      // data cache size (source)            

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 the usage report to any run
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

The default install puts the executable in /usr/local/sbin and provides a man(8)
page. If the daemon interface is enabled, init.d/Makefile will generate an init
script based upon the target path and a template selected by the @HA_DISTRO@
setting. Two templates are provided: "redhat.in" and "lsb.in". The default,
"redhat.in", is a RedHat style init script. The alternate, "lsb.in", is a
starting point for distributions following the Linux Standard Base conventions.
The init template used is specifed as the HA_DISTRO enviromental variable to
configure:

./configure --enable-nistest HA_DISTRO="lsb.in"

This mechanism can be extended 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.