In an effort to provide a flexible implementation for a random number
generator that also delivers entropy during early boot time, allows
replacement of the deterministic random number generation mechanism,
implement the various components in separate code for easier
maintenance, and provide compliance to SP800-90[A|B|C], introduce
the Linux Random Number Generator (LRNG) framework.
The general design is as follows. Additional implementation details
are given in [1]. The LRNG consists of the following components:
1. The LRNG implements a DRNG. The DRNG always generates the
requested amount of output. When using the SP800-90A terminology
it operates without prediction resistance. The secondary DRNG
maintains a counter of how many bytes were generated since last
re-seed and a timer of the elapsed time since last re-seed. If either
the counter or the timer reaches a threshold, the secondary DRNG is
seeded from the entropy pool.
In case the Linux kernel detects a NUMA system, one secondary DRNG
instance per NUMA node is maintained.
2. The DRNG is seeded by concatenating the data from the
following sources:
(a) the output of the entropy pool,
(b) the Jitter RNG if available and enabled, and
(c) the CPU-based noise source such as Intel RDRAND if available and
enabled.
The entropy estimate of the data of all noise sources are added to
form the entropy estimate of the data used to seed the DRNG with.
The LRNG ensures, however, that the DRNG after seeding is at
maximum the security strength of the DRNG.
The LRNG is designed such that none of these noise sources can dominate
the other noise sources to provide seed data to the DRNG during due to
the following:
(a) During boot time, the amount of received interrupts are the trigger
points to (re)seed the DRNG.
(b) At runtime, the available entropy from the slow noise source is
concatenated with a pre-defined amount of data from the fast noise
sources. In addition, each DRNG reseed operation triggers external
noise source providers to deliver one block of data.
3. The entropy pool accumulates entropy obtained from certain events,
which will henceforth be collectively called "slow noise sources".
The entropy pool collects noise data from slow noise sources. Any data
received by the LRNG from the slow noise sources is inserted into a
per-CPU entropy pool using a hash operation that can be changed during
runtime. Per default, SHA-256 is used.
(a) When an interrupt occurs, the high-resolution time stamp is mixed
into the per-CPU entropy pool. This time stamp is credited with
heuristically implied entropy.
(b) HID event data like the key stroke or the mouse coordinates are
mixed into the per-CPU entropy pool. This data is not credited with
entropy by the LRNG.
(c) Device drivers may provide data that is mixed into an auxiliary
pool using the same hash that is used to process the per-CPU entropy
pool. This data is not credited with entropy by the LRNG.
Any data provided from user space by either writing to /dev/random,
/dev/urandom or the IOCTL of RNDADDENTROPY on both device files
are always injected into the auxiliary pool.
In addition, when a hardware random number generator covered by the
Linux kernel HW generator framework wants to deliver random numbers,
it is injected into the auxiliary pool as well. HW generator noise source
is handled separately from the other noise source due to the fact that
the HW generator framework may decide by itself when to deliver data
whereas the other noise sources always requested for data driven by the
LRNG operation. Similarly any user space provided data is inserted into
the entropy pool.
When seed data for the DRNG is to be generated, all per-CPU
entropy pools and the auxiliary pool are hashed. The message digest
forms the new auxiliary pool state. At the same time, this data
is used for seeding the DRNG.
To speed up the interrupt handling code of the LRNG, the time stamp
collected for an interrupt event is truncated to the 8 least
significant bits. 64 truncated time stamps are concatenated and then
jointly inserted into the per-CPU entropy pool. During boot time,
until the fully seeded stage is reached, each time stamp with its
32 least significant bits is are concatenated. When 16 such events
are received, they are injected into the per-CPU entropy pool.
The LRNG allows the DRNG mechanism to be changed at runtime. Per default,
a ChaCha20-based DRNG is used. The ChaCha20-DRNG implemented for the
LRNG is also provided as a stand-alone user space deterministic random
number generator. The LRNG also offers an SP800-90A DRBG based on the
Linux kernel crypto API DRBG implementation.
The processing of entropic data from the noise source before injecting
them into the DRNG is performed with the following mathematical
operations:
1. Truncation: The received time stamps are truncated to 8 least
significant bits (or 32 least significant bits during boot time)
2. Concatenation: The received and truncated time stamps
