Linux Random Number Generator – A New Approach

Stephan Müller <smueller@chronox.de>

1 Introduction

1.1 Linux /dev/random Status Quo

• the block device identifier which is static for the lifetime of the system and thus provides little [B]  [B] If two or more disks are present in the system that are deemed to provide entropy, the order of event arrivals for the different disks may provide some small entropy. or no entropy,
• the event time of a block device I/O operation in Jiffies which is a coarse timer and provides very limited amount of entropy, and
• the event time of a block device I/O operation using a high-resolution timer which provides almost all measured entropy for this noise source [C]  [C] Such entropy naturally relies on the assumption that the time variances of events are hard to predict with sufficient precision relative to the resolution of the timer. In addition, any attacker is assumed to not have access to the kernel memory holding the entropy as otherwise it is eliminated..

• the HID identifier such as a key or the movement directions of a mouse which provide a hard to quantify amount of entropy,
• the event time of an HID operation in Jiffies which again provides a very limited amount of entropy, and
• the event time of an HID operation using a high-resolution timer that again provides almost all measured entropy for this noise source.

• mixing the high-resolution time stamp, the Jiffies time stamp, the value of the instruction pointer and the register content into a per-CPU fast_pool where the high-resolution time stamp again provides the majority of entropy – due to a high correlation between the interrupt occurrence and the HID / block device noise sources the time stamp for those events are considered to have relatively little entropy which implies that the content of the fast_pool at the time of injection into the input_pool is heuristically assumed to have one bit of entropy, and
• injecting the content of the fast_pool into the input_pool entropy pool once a second or after 64 interrupts have been processed by that per-CPU fast_pool – whatever comes later.

1.2 A New Approach

• The Linux /dev/random implementation in drivers/char/random.c is called legacy /dev/random↓ henceforth. Although the naming refers only to the interface, the entirety of the legacy random number generation in the Linux kernel available through different interfaces like /dev/random, /dev/urandom, getrandom(2) or the in-kernel function of get_random_bytes is covered by the name.
• The newly proposed approach for entropy collection is called Linux Random Number Generator↓ (LRNG) throughout this document. It provides an API and ABI compatible replacement implementation of the legacy /dev/random implementation providing the same interfaces and identical user-visible behavior but with a completely different collection and management of entropy as well as generation of random numbers.

1. The LRNG considers the timing of interrupts as the source of entropy. Therefore, the entropy heuristic applied by the LRNG only rests on the timing of interrupts. Other event information like the HID event data (e.g. which key stroke was received, which mouse coordinate was recorded) or block device numbers are picked up and stirred into the entropy pool but without awarding them any heuristic entropy. Thus, the LRNG is not affected by the aforementioned correlation issue.The LRNG introduces the concept of slow and fast noise sources. Fast noise sources provide entropy at the time of request. A slow noise source collects data over time into an entropy pool – the interrupt events are considered such a slow noise source. The LRNG combines both types of noise sources that when the entropy pool is queried for entropy, all fast noise sources are also queried for additional entropy and the concatenated data is handled by the post-processing to generate random numbers. With this, the LRNG can use both types of noise sources without allowing one noise source to dominate another.
2. The seeding mechanism of the LRNG during boot ensures that entropy data is forwarded to the deterministic random number generators in well-defined chunks of 32 bits, 128 bits and 256 bits where these chunks denominate the of initial, minimal and full seed levels of the LRNG. Thus, the LRNG cannot be tricked into repeatedly releasing small entropy levels to the deterministic random number generators and thus to callers. Such attack approach would diminish the collected entropy significantly. Commonly, the minimal entropy threshold of 128 bits of the LRNG is reached before or at the time user space boots. The full seed level of 256 bits is reached at the time the initramfs is executed but before the root partition is mounted on standard Linux distributions.
3. The LRNG supports a runtime-switchable deterministic random number generator that generates data for a calling user that can be enabled during compile time. With a well defined API developers can implement their own deterministic random number generator if the provided ones are not considered appropriate. Per default, a ChaCha20-based deterministic random number generator is used. In addition, an SP800-90A [4] DRBG offering all three DRBG types is provided as well. The SP800-90A DRBG and its cryptographic primitives are taken from the kernel crypto API which implies that these implementations are covered by the power-on health tests offered by the kernel crypto API.
4. The LRNG provides a health test interface that monitor the received entropy for the slow noise source can can be enabled during compile time. Using this test interface, SP800-90B [5] compliant health tests are implemented. With these health tests and additional logic, the LRNG is considered SP800-90B, as well as SP800-90C compliant. When using an SP800-90A DRBG at the same time the LRNG operates compliant to SP800-90B, the output of an LRNG can be used directly for purposes requiring data from a FIPS 140-2 approved noise source and random number generator.
5. To analyze the slow noise source, the LRNG provides a development interface allowing to extract the raw unconditioned noise data [G]  [G] This interface is solely intended for development. It is intended to be disabled at compile time for production systems..
6. Tests are developed for various aspects of the LRNG allowing a user-space simulation of those LRNG functions. Such simulations allow developers to further analyze and assess the implementation and the resulting behavior of the LRNG. In addition, tests for all types of entropy assessments required by SP800-90B are provided. Finally, this document provides a full SP800-90B entropy analysis.

1. During boot time, the LRNG is designed to already provide random numbers with sufficiently high entropy. It is common that long-running daemons with cryptographic support seed their deterministic random number generators (DRNG) when they start during boot time. The re-seeding of those DRNGs may be conducted very much later, if at all which implies that until such re-seeding happens, the DRNG may provide weak random numbers. The LRNG is intended to ensure that for such use cases, sufficient entropy is available during early user space boot. Daemons that link with OpenSSL, for example, use a DRNG that is not automatically re-seeded by OpenSSL. If the author of such daemons is not careful, the OpenSSL DRNG is seeded once during boot time of the system and never thereafter. Hence seeding such DRNGs with random numbers having high entropy is very important.\begin_inset Separator latexpar\end_inset
   As documented in chapter 5↓ the DRNG is seeded with full security strength of 256 bits during the first steps of the initramfs time after about 1.3 seconds after boot. That measurement was taken within a virtual machine with very few devices attached where the legacy /dev/random implementation initializes the nonblocking_pool or the ChaCha20 DRNG after 30 seconds or more after boot with 128 bits of entropy. In addition, the LRNG maintains the information by when the DRNG is ‘‘minimally’’ seeded with 128 bits of entropy to trigger in-kernel callers requesting random numbers with sufficient quality. This is commonly achieved even before user space is initiated.
2. The LRNG must be a drop-in replacement for the legacy /dev/random in respect to the ABI and API of its external interfaces. This allows keeping any frictions during replacement to a minimum. The interfaces to be kept ABI and API compatible cover all in-kernel interfaces as well as the user space interfaces. No user space or kernel space user of the LRNG is required to be changed at all.
3. All user-visible behavior implemented by the legacy /dev/random – such as the per-NUMA-node DRNG instances are provided by the LRNG as well.
4. The LRNG must be very lightweight in hot code paths. As described in the design in chapter 2↓, the LRNG is hooked into the interrupt handler and therefore should finish the code path in interrupt context very fast.
5. The LRNG must not use locking in hot code paths to limit the impact on massively parallel systems.
6. The LRNG must handle modern computing environments without a degradation of entropy. The LRNG therefore must work in virtualized environments, with SSDs, on systems without HIDs or block devices and so forth.
7. The LRNG must provide a design that allows quantitative testing of the entropy behavior.
8. The LRNG must use testable and widely accepted cryptography for conditioning.
9. The LRNG must allow the use of cipher implementations backed by architecture specific optimized assembler code or even hardware accelerators. This provides the potential for lowering the CPU costs when generating random numbers – less power is required for the operation and battery time is conserved.
10. The LRNG must separate the cryptographic processing from the noiseentropy source maintenance to allow a replacement of these components.

1.3 Advantages Introduced by LRNG

• Sole use of crypto for data processing:
  • Exclusive use of a hash operation for conditioning entropy data with a clear mathematical description as given section 2.2↓ – non-cryptographic operations like LFSR are not used.
  • The LRNG uses only properly defined and implemented cryptographic algorithms unlike the use of the SHA-1 transformation in the legacy /dev/random implementation that is not compliant with SHA-1 as defined in FIPS 180-4.
  • Hash operations use NUMA-node-local hash instances to benefit large parallel systems.
  • LRNG uses limited number of data post-processing steps as documented in section 2.2↓ compared to the large variation of different post-processing steps in the legacy /dev/random implementation that have no apparent mathematical description (see section 5.5↓).
• Performance
  • Faster by up to 130% in the critical code path of the interrupt handler depending on data collection size configurable at kernel compile time as outlined in section 5.2↓ - the default selects the collection size providing the fastest performance.
  • Block device data path is not instrumented by LRNG which implies that the LRNG does not add any delays compared to the legacy /dev/random.
  • Configurable data collection sizes to accommodate small environments and big environments via CONFIG_LRNG_COLLECTION_SIZE.
  • Entropy collection using an almost never contended lock to benefit large parallel systems – worst case rate of contention is the number of DRNG reseeds, usually the number of potential contentions per 10 minutes is equal to number of NUMA nodes.
  • ChaCha20 DRNG is significantly faster as implemented in the legacy /dev/random as demonstrated with table 2↓.
  • Faster entropy collection during boot time to reach fully seeded level, including on virtual systems or systems with SSDs as outlined in section 5.1↓.
• Testing
  • Availablility of run-time health tests of the raw unconditioned noise sourceentropy source data of the interrupt entropy source to identify degradation of the available entropy as documented in section 2.5.2↓. Such health tests are important today due to virtual machine monitors reducing the resolution of or disabling the high-resolution timer.
  • Heuristic entropy estimation for the interrupt entropy source is based on quantitative measurements and analysis following SP800-90B and not on coincidental underestimation of entropy applied by the legacy /dev/random as outlined in [9] section 4.4.
  • Power-on self tests for critical deterministic components (ChaCha20 DRNG, software hash implementation, and entropy collection logic) not already covered by power-up tests of the kernel crypto API as documented in section 2.14↓.
  • Availability of test interfaces for all operational stages of the LRNG including boot-time raw entropy event data sampling as outlined in section 2.15↓.
  • Fully testable ChaCha20 DRNG via a userspace ChaCha20 DRNG implementation.
  • In case of using the SP800-90A DRBG, it is fully testable and tested via the NIST ACVP test framework, for example certificates A628, and A737.
  • In case of using the kernel crypto API SHASH hash implementation, it is fully testable and tested via the NIST ACVP test framework, for example certificates A734, A737, and A738.
  • The LRNG offers a test interface to validate the used software hash implementation and in particular that the LRNG invokes the hash correctly, allowing a NIST ACVP-compliant test cycle – see section 2.15↓.
  • Availability of stress testing covering the different code paths for data and mechanism (de)allocations and code paths covered with locks.
  • Availability of fully automated regression testing covering different LRNG functions in different configurations allow an unattended functional verification testing.
• Entropy collection of the internal interrupt entropy source
  • The LRNG is fully compliant to SP800-90B requirements and is shipped with a full SP800-90B assessment and all required test tools. The legacy /dev/random implementation on the other hand has architectural limitations which does not easily allow to bring the implementation in compliance with SP800-90B as outlined in section 5.5↓.
  • Full entropy assessment and description is provided with chapter 3↓, specifically section 3.3.6↓.
  • Guarantee that entropy events are not credited with entropy twice (the legacy /dev/random implementation credits HID/disk and interrupt events with entropy which are a derivative of each other) and guarantee that entropy data is not reused for two different use cases (as done in the legacy /dev/random implementation when injecting a part of fast_pool into the net_rand_state).
  • The LRNG provides a configuration to be compliant to SP800-90C following RBG2(NP) as well as RBG2(P) construction methods.
• Configurable
  • LRNG kernel configuration allows configuration that is functionally equivalent to the legacy /dev/random. Non-compiled additional code is folded into no-ops.
  • The following additional functions are compile-time selectable independent of each other:
    • Enabling of switchable cryptographic implementation support. This allows enabling SP800-90A DRBG.
    • Enabling of using Jitter RNG noise sourceentropy source.
    • Enabling of interrupt entropynoise source health tests including SP800-90B health tests.
    • Enabling of test interface allowing to enable each test interface individually.
    • Enabling of the power-up self test.
    • Selectively enabling of each entropy source and configuring their entropy rate.
    • The entropy rate used to credit the internal interrupt entropy source, the external CPU-based entropy source and Jitter RNG entropy source can be configured including setting an entropy rate of zero or full entropy – see sections 2.9.1↓ and 2.8.1↓. A rate of zero implies that the entropy source still provides data which is credited with zero bits of entropy.
  • At boot-time, the SP800-90B health tests for the internal interrupt entropy source can be enabled as outlined in section 2.5.2↓.
  • At boot-timecompile time, the entropy rate used to credit the internal interrupt entropy source, the external CPU-based noise source and Jitter RNG noise source can be configured including setting an entropy rate of zero or full entropy – see sections 2.5.1↓, 2.9.1↓ and 2.8.1↓.
  • Configurable seeding strategies are provided following different concepts.
• Run-time pluggable cryptographic implementations used for all data processing steps specified in section 2.2↓
  • The DRNG can be replaced with a different implementation allowing any type of DRNG to provide data via the output interfaces. The LRNG provides the following types of DRNG implementations:
    • ChaCha20-based software implementation that is used per default.
    • SP800-90A DRBG using accelerated cryptographic implementations that may sleep.
    • Any DRNG that is accessible via the kernel crypto API RNG subsystem.
  • The hash component can be replaced with any other hash implementation provided the implementation does not sleep. The LRNG provides the following types of hash implementations:
    • SHA-256 software implementation that is used per default. Due to kernel build system inconsistencies, the software SHA-1 implementation is used if the kernel crypto API is not compiled.
    • SHA-512 hash using the fastest hash implementation available via the kernel crypto API SHASH subsystem.
• Code structure
  • The LRNG source code is available for current upstream Linux kernel separate to the legacy /dev/random which means that users who are conservative can use the unchanged legacy /dev/random implementation.
  • Back-port patches are available to apply the LRNG to LTS Linux kernel versions of 5.10, 5.8, 5.4, 4.19, 4.14, 4.12, 4.10, and 4.4. In addition, backport patches for kernel version 5.8, 4.12 and 4.10 are provided. Patches for other kernel versions are easily derived from the existing ones.

1.4 Document Structure

• The design of the LRNG is documented in chapter 2↓. The design discussion references to the actual implementation whose source code is publicly available.
• The statistical testing including the SP800-90B compliance assessment is provided in chapter 3↓.
• The comparison of the LRNG with the legacy /dev/random is covered in chapter 5↓.
• The various appendices cover miscellaneous topics supporting the general description.

2 LRNG Design

Figure 1 LRNG Big Picture

• Orange marked parts consisting of the IRQ noise sourceentropy source that feeds into the per-CPU entropy pool from which the hash of pools is derived.

• The auxiliary pool collects data from external entropy sources which deliver data at times not controllable by the LRNG.
• The CPU entropy source obtains data from a potentially existing source in the CPU like RDSEED on Intel CPUs.
• The Jitter RNG entropy source is another external entropy source.

2.1 LRNG 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 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 DRNG is seeded from the entropy pool and additional ‘‘fast’’ noise sourcesentropy sources with the available entropy.
   In case the Linux kernel detects a NUMA system, one DRNG instance per NUMA node is maintained.
   Depending on the used interface to request data from the DRNG, the caller may be put to sleep until the LRNG is fully seeded:
   1. /dev/urandom and the getrandom system call with the GRND_INSECURE flag always generates data including when the LRNG is not properly seeded.
   2. /dev/random and the getrandom system call with the GRND_RANDOM or with a flag of zero generates data only when the LRNG is fully seeded.
2. The DRNG is seeded by concatenating the data from the following sources:
   1. the output of the auxiliary pool,
   2. the output of the per-CPU entropy pools,
   3. the Jitter RNG if available, and
   4. the CPU-based noiseentropy source such as Intel RDSEED if available.
   The entropy estimate of the data of all noiseentropy 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 used DRNG implementation of 256 bits.
   The LRNG is designed such that none of these noiseentropy sources can dominate the other noiseentropy sources to provide seed data to the DRNG due to the following:
   1. During boot time, the amount of received interruptsavailable entropy isare the trigger points to (re)seed the DRNG following the explanation in the next section.
   2. 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 datathe DRNG reseed is triggered by either the DRNG due to hitting the aforementioned thresholds or by a user space caller. The reseed is never triggered by the entropy sources.
3. The contentmessage digest of the auxiliary pool is used directly for seeding the DRNG. If the auxiliary pool is intended to provide full entropy, external entropy provider must always ensure that at least 256 bits of entropy are injected into the LRNG when the LRNG requests that data. The following sources of entropy are used for the auxiliary pool:
   1. Data written to /dev/random or /dev/urandom is added to the pool without crediting it with entropy.
   2. Data provided with the IOCTL RNDADDENTROPY is inserted into the pool with the entropy rate defined by the IOCTL caller.
   3. Data provided with the in-kernel API call of add_hwgenerator_randomness is inserted into the pool with the entropy rate defined by the API caller.
   4. Device drivers may provide data that is mixed into the auxiliary pool. This data is not credited with entropy by the LRNG and it is unrelated to the data credited with entropy, i.e. the time stamp. Thus it is treated as additional data to stir the entropy pool.
   When the DRNG requires fresh seed data from the auxiliary entropy pool, a message digest of the pool is calculated. The data returned as seed data is truncated to the amount of bits requested by the caller (commonly 256 bits which is equal to the security strength of the DRNG). Note, the output is not truncated to the available entropy to ensure that data that is not credited with entropy is used to at least stir the DRNG. It is possible that only data is inserted into the auxiliary pool that is not credited with entropy. In this case, this data shall still find its way into the DRNG.
4. The per-CPU entropy pools collects noise data from the interrupt slow noiseentropy sources. Any data received by the LRNG from the slowinterrupt noiseentropy sources is inserted into the per-CPU entropy pool using an a hash. After boot, the used hash is SHA-256, but the used hash algorithm can be changed at runtime. The following sources of entropy are used:
   1. When an interrupt occurs, the high-resolution time stamp is concatenated with previous time stamps. Once a given number of time stamps are received, they are hashed together with the per-CPU entropy pool to form a new state of that entropy pool. This time stamp is credited with heuristically implied entropy. To speed up the interrupt handling code of the LRNG, the time stamp collected for an interrupt event is first divided by its greatest common divisor (GCD) truncated to the 8 least significant bits. 1,024 truncated time stamps are concatenated and then processed by the mentioned hash operation. During boot time, until the GCD value is calculated, each time stamp truncated to the 32 least significant bits instead. These 32 bits are concatenated like the 8 bit values and processed by the hash operation. More details are given in section 2.5.1↓.
   2. HID event data like the key stroke or the mouse coordinates are concatenated with the time stamps and processed as outlined for the time stamps. This data is not credited with entropy by the LRNG and this data has no correlation with the data credited with entropy, i.e. the time stamp. Thus it is treated as additional data to stir the entropy pool.
   3. Device drivers may provide data that is mixed into the auxiliary pool using the hash operation. This data is not credited with entropy by the LRNG and it is unrelated to the data credited with entropy, i.e. the time stamp. Thus it is treated as additional data to stir the entropy pool.
   When the DRNG requires fresh seed data from the entropy pools, a hashmessage digest of all per-CPU entropy pools is created. The data returned as seed data is truncated to the amount of bits requested by the caller (commonly 256 bits which is equal to the security strength of the DRNG) or truncated to the available entropy, whatever is smaller. The result of this operation is that the generated data used to seed the DRNG have full entropy. The truncation operation maintains entropy as it is defined by [5] section 5.1.3.1.1 table 1 which defines that each approved hash has full security strength even though the hash operation performs a truncation (e.g. for SHA-384 or SHA-512/256).
5. Any data provided from user space either provided via /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.
   The reason for having the auxiliary pool is to allow injection of entropy data compliant to [5] section 3.1.6. As the LRNG may maintain multiple DRNGs, it would not be clear into which DRNG to inject it at the time of receipt of data from these auxiliary noise sources.
   When the entropy pool is processed with the hash function to obtain random numbers, the auxiliary pool is ‘‘read’’ at the same time. Thus, the hash operation generates random numbers using both pools at the same time.
6. To support backward secrecy, the following steps are applied:
   1. The temporary seed buffer holding the concatenation of data from all entropy sources to seed the DRNG is also injected into the auxiliary pool like other data by hashing it together with the existing auxiliary pool data to form the new auxiliary pool content. The injection of the temporary seed buffer will not alter the entropy estimation of the auxiliary pool.
   2. The message digest created for each per-CPU entropy pool is inserted into the corresponding per-CPU entropy pool.

2.2 LRNG Data Processing

1. Truncation: The received time stamps are truncated to 8 least significant bits (or 32 least significant bits during boot time) – note the GCD is a value calculated during initialization and is fixed thereafter which implies that the time stamp divided by the GCD is the raw entropy value: t₈ (or t₃₂)
2. Concatenation: The received and truncated time stamps as well as auxiliary 32 bit words a₃₂ are concatenated to fill the per-CPU collection pool that is capable of holding 1,024 8-bit words [I]  [I] The LRNG collection size is compile-time configurable where 1,024 is a default value. When configuring a different value, the number of the concatenated data must be adjusted as needed. However, this modification has no impact to the illustration of the data processing. - the order of the data a₃₂ or t₈ present in the concatenation depends on the occurrence of events - the following formula depicts one possible order for illustration - the implementation is provided with functions _lrng_pcpu_array_add_u32 and lrng_pcpu_array_add_slot:
   (1) CP = t_{8n − 1019}||a_32n||t_{8n − 1018}|| ... ||t_8n
   Note: In case the continuous compression operation is disabled, the auxiliary 32 bit words a₃₂ are discarded and are not injected into the collection pool. This approach is taken to prevent non-entropy data to potentially overwrite entropy data in the collection pool when the array wraps.
3. Hashing: All concatenated time stamp data received from the interrupts since the last output generation of the per-CPU entropy pool EP_{CPUn − 1} are hashed together with that last output EP_{CPUn − 1} to generate new per-CPU entropy pool output of EP_CPUn. The following steps are performed:
   1. One filled per-CPU collection pool CP_m is inserted into the per-CPU entropy pool using a hash update operation.
   2. To generate data from the entropy pool EP_CPUn as used by function 4↓, a hash final operation is performed.
   3. Once a hash final operation is performed it is followed by an immediate re-initialization of the hash state with a hash init operation and adding the just calculated message digest with the first hash update.
   The implementation is provided with function lrng_pcpu_array_compress together with the function lrng_pcpu_pool_hash_one generating data from the per-CPU entropy pool:

   (2) EP_CPUn = SHA(CP_m||CP_m − 1||...||CP_{m − n − 1}||EP_{CPUn − 1})
   Note: The hash updateing operation is performed at the following occasions:
   1. Continuous compression enabled: The hash updateing is performed every time the collection pool is full. This operation therefore is performed in interrupt context. In addition, the operation is performed at the time operation of equation 4↓ is invoked which is in process context.
   2. Continuous compression enabled and disabled: The hash updateing is performed at the time the operation of equation 4↓ is invoked, i.e. at the time the DRNG is reseeded. This operation therefore is performed in process context. This guarantees that all unprocessed entropy data in the collection pool is added to the entropy pool at the time the entropy pool is requested for random data.
   This implies that in case of disabled continuous compression, the oldest entries in the collection pool are overwritten with newer entropy event data when more entropy events are collected than can be held in the collection pool between DRNG reseeds.
4. Hashing: When new data D_m is added to the auxiliary pool AP, the data is concatenated with all previously added data and hashed together with theinserted into the auxiliary pool with a hash update operationto form a new auxiliary pool state - the implementation is provided with function lrng_pool_insert_aux. The hashmessage digest generation operation is performed at the time entropy from the auxiliary pool is requested. To ensure backward secrecy, the temporary seed buffer T_n − 1 that holds among others the auxiliary pool digest from the previous generation round as depicted with equation 9↓ is concatenated with the received data:
   (3) AP_n = SHA(T_n − 1||D_m||D_m − 1||...||D_{m − n − 1})
5. Hashing: A message digest of all per-CPU entropy pools is calculated. This message digest is used to fill the interrupt slowentropy noise source output buffer S discussed in the following - the implementation is provided with function lrng_pcpu_pool_hash:
   (4) EP_alln = SHA(EP_CPU0n||EP_CPU1n|| ... ||EP_CPUXn)
6. Hashing: If the CPU entropy source provides less than full entropy, a message digest of the amount of data to be requested from it is calculated:
   (5) C_cond = SHA(C₁|| ... ||C_m)
7. Truncation: The most-significant bits (MSB) defined by the requested number of bits (commonly equal to the security strength of the DRBG) or the entropy available transported with the buffer (which is the minimum of the message digest size and the available entropy in all entropy pools and the auxiliary pool), whatever is smaller, are obtained from the slowinterrupt entropy noise source output buffer S - the implementation is provided with function lrng_pcpu_pool_hash:
   (6) S_n = MSB_{min(entropy, security strength)}(EP_alln)
8. Truncation: The MSB of the auxiliary pool of the size of the DRNG security strength are used for the seed buffer:
   (7) A_n = MSB_{min(digest size, security strength)}(AP_n)
9. Truncation: If the CPU entropy source provides less than full entropy, the MSB defined by the requested number of bits (commonly equal to the security strength of the DRBG) or the applied message digest size, what ever is smaller, are obtained - the implementation is provided with function lrng_get_arch_data_compress – otherwise C_n is the data obtained directly from the CPU entropy source:
   (8) C_n = MSB_{min(digest size, security strength)}(C_cond)
10. Concatenation: The temporary seed buffer T used to seed the DRNG is a concatenation of the auxiliary pool entropy source A, the slowinterrupt entropy noise source buffer S, the Jitter RNG output J, the CPU noise sourceentropy source output C, and the current time t - the implementation is provided with function lrng_fill_seed_buffer:
    (9) T_n = A_n||S_n||J_n||C_n||t

2.3 LRNG Architecture

1. The DRNG is reseeded from the entropy pool and potentially the fast noiseentropy sources if all entropy sourcesthe entropy pool collectivelyhas collected have at least 32 bits of entropy available from the interrupt noise source. The goal of this step is to ensure that the DRNG receive some initial entropy as early as possible. In addition it receives the entropy available from the fast noise sources.
2. The DRNG is reseeded from the auxiliary pool, the entropy pools and potentially the fast noise sources if all noise sources collectively can provide at least 128 bits of entropyThe DRNG is reseeded from the entropy sources if all entropy sources collectively have at least 128 bits of entropy available.
3. The DRNG is reseeded from the auxiliary pool, the entropy pools and potentially the fast noise sources if all noise sources collectively can provide at least 256 bits of entropy.The DRNG is reseeded from the entropy sources if all entropy sources collectively have at least 256 bits of entropy available.

• The maximum number of random bytes that can be generated with one DRNG generate operation is limited to 4096 bytes. When longer random numbers are requested, multiple DRNG generate operations are performed. The ChaCha20 DRNG as well as the SP800-90A DRBGs implement an update of their state after completing a generate request for backward secrecy.
• The DRNG is reseeded with whatever entropy is available, but at least 128 bits – in the worst case where no additional entropy can be provided by the noise sourceentropy sources, the DRNG is not re-seeded and continues its operation to try to reseed again after again the expiry of one of these thresholds:\begin_inset Separator latexpar\end_inset
  • If the last reseeding of the DRNG is more than 600 seconds ago [J]  [J] Note, this value will not empty the entropy pool even on a completely quiet system. Testing of the LRNG was performed on a KVM without fast noise sourceentropy sources and with a minimal user space, where only the SSH daemon was running, During the testing, no operation was performed by a user. Yet, the system collected more than 256 bits of entropy from the interrupt noise sourceentropy source within that time frame, satisfying the DRNG reseed requirement., or
  • 2²⁰ DRNG generate operations are performed, whatever comes first, or
  • the DRNG is forced to reseed before the next generation of random numbers if data has been injected into the LRNG by writing data into /dev/random or /dev/urandom.
  The chosen values prevent high-volume requests from user space to cause frequent reseeding operations which drag down the performance of the DRNG [K]  [K] Considering that the maximum request size is 4096 bytes defined by LRNG_DRNG_MAX_REQSIZE (i.e. each request is segmented into 4096 byte chunks) and at most 2²⁰ requests defined by LRNG_DRNG_RESEED_THRESH can be made before a forced reseed takes place, at most 4096⋅2²⁰ = 4, 294, 967, 296 bytes can be obtained from the DRNG without a reseed operation. [L]  [L] After boot, the ChaCha20 DRNG state is also used for the atomic DRNG state. Although both DRNGs are controlled by separate and isolated objects, the DRNG state is identical. As the LRNG_DRNG_RESEED_THRESH is enforced local to each DRNG object, the theoretical maximum number of random bytes the ChaCha20 DRNG state could generate before a forced reseed is twice the amount listed before – once for the DRNG object and once for the atomic DRNG object..
• If the DRNG was not reseeded for the last 2³⁰ DRNG generate operations – i.e. the reseeding requests discussed in the previous bullets were unsuccessful – the DRNG reverts back to an unseeded state. This applies that the DRNG will not produce random numbers when accessed via the blocking interfaces. In this case, the DRNG behaves like during boot time.

2.3.1 Minimally Versus Fully Seeded Level

• Upon reaching the minimally seeded level, the kernel-space callers waiting for a seeded DRNG via the API calls of either wait_for_random_bytes is woken up.
• When reaching the fully seeded level, the user-space callers waiting for a fully seeded DRNG via the getrandom system call or /dev/random are woken up. Also in-kernel callers waiting with add_random_ready_callback are woken up. Finally, in-kernel callers can poll rng_is_initialized which returns true if the LRNG is fully seeded and initialized.

2.3.2 Seeding Examples

2.3.3 NUMA Systems

Figure 2 DRNG Instances on NUMA systems with seeding strategy

2.3.4 Flexible Design

2.3.5 Covered Design Concerns of Legacy /dev/random

2.4 LRNG Data Structures

• The data from the interrupt noise sourceentropy source is processed with a per-CPU entropy pool. In addition, a per-CPU collection pool that can hold the concatenated time stamps is maintained. Both are accessed lockless since the currently executing CPU’s entropy pool and collection pool is used. During access to the entropy pool, the LRNG though takes a lock since the entropy pool is also read when the hash is calculated for filling the seed buffer. As the filling of the seed buffer is very infrequently (see above for the reseed periods of the DRNG), the lock is hardly contented which allows the conclusion that the entropy collection operates quasi-lockless.
• The deterministic random number generator data structure for the DRNG holds the reference to the DRNG instance and the hash instance and associated meta data needed for its operation. The DRNG is managed with a separate data structure. When using the DRNG, a full read/write lock is used to guard (a) against replacement of the DRNG reference while operating on the DRNG state, and (b) to read/write the DRNG state. Contrarily when using the hash, only a read-lock is used to guard against the replacement of the hash reference. This implies that the hash state is kept on the stack of the calling application.

2.5 Interrupt Processing - LRNG-internal Entropy Source

Figure 3 Interrupt Processing

1. A high-resolution time stamp is obtained using the service random_get_entropy kernel function. This integer value is divided by a GCD to eliminate bits that do not change. Although that function returns a 64-bit integer, only the bottom 8 bits, i.e. the fast moving bits, are used for further processing. To ensure fast processing, these 8 bits are concatenated and stored in the operating CPU’s data collection pool. After the receipt of 1,024 time stamps, the data collection pool with all concatenated time stamps is inserted into the currently executing CPU’s entropy pool. During boot time until the LRNG completed the calculation of the GCD, the 32 least significant bits of the data are directly inserted into the CPU’s entropy pool. Entropy is contained in the variations of the time of events and its time delta variations. Figure 1↑ depicts the time stamp array holding the 8-bit time stamp values.
2. The health tests discussed in section 2.5.2↓ are performed on each received time stamp where the truncated time stamp value is forwarded to the health test. Unless 1,024 time stamps have been received, the processing of an interrupt stops now.
3. The per-CPU collection pool is added to the same CPU’s entropy pool by performing a hash update operation. This approach works as the per-CPU entropy pool is managed as the message digest state. When data of the per-CPU entropy is to be extracted, a hash final operation is performed followed by an immediate re-initialization of the state buffer using the message digest of the previous extraction. This operation is depicted in figure 4↓ for the entropy pool maintained by CPU 0. The other CPUs perform the same processing with their independent copy of the collection pool and the entropy pool. In case the continuous compression support is disabled, the hash operation is not performed. Instead, the oldest entropy values in the collection pool are overwritten with the latest entropy value. In case the continuous compression operation is disabled, the hash update operation is conducted in process context at the time of obtaining random numbers from the entropy pool requested to seed the DRNG documented in section 2.10↓.
   

   Figure 4 Collection Pool Processing
4. The LRNG increases the per-CPU counter of the received interrupt events by the number of healthy interrupts stored in the per-CPU collection pool. This counter is translated into an entropy statement when the LRNG wants to know how much entropy is present in the entropy pool. This counter is also adjusted when reading data from the entropy.
5. If equal or more than /proc/sys/kernel/random/read_wakeup_threshold healthy bits are received by all per-CPU entropy pools, the wait queue where readers wait for entropy is woken up. Note, to limit the amount of wakeup calls if the entropy pool is full, a wakeup call is only performed after receiving 32 interrupt events. The reason is that the smallest amount of random numbers generated from the entropy pool 32 bits anyway, i.e. the initially seeded level.
6. If all DRNG instances are fully seeded, the processing stops. This implies that only during boot time the next step is triggered. At runtime, the interrupt noise sourceentropy sources will not trigger a reseeding of the DRNG.
7. If less than LRNG_IRQ_ENTROPY_BITS healthy bits are received, the processing of the LRNG interrupt callback terminates. This value denominates the number of healthy bits that must be collected to assume this bit string has 256 bits of entropy. That value is set to a default value of 256 (interrupts). Section 2.5.1↓ explains this default value. Note, during boot time, this value is set to 128 bits of entropy.
8. Otherwise, the LRNG triggers a kernel work queue to perform a seeding operation discussed in section 2.10↓.

• IRQ number,
• High 32 bits of the instruction pointer,
• Low 32 bits of the instruction pointer,
• A 32 bit value obtained from a register value – the LRNG iterates through all registers present on the system.

2.5.1 Entropy Amount of Interrupts

2.5.2 Health Tests

• Stuck Test
• Repetition Count Test (RCT)
• Adaptive Proportion Test (APT)

• Sources feeding the auxiliary entropy pool: The interface functions to provide entropy data (add_hwgenerator_randomness or the IOCTL RNDADDENTROPY have to be invoked with the value 0 for the entropy rate.
• CPU-based noise sourceentropy source: CONFIG_LRNG_CPU_ENTROPY_RATE=0
• Jitter RNG: CONFIG_LRNG_JENT_ENTROPY_RATE=0

1. The entropy of the entire entropy pool is invalidated.
2. All DRNGs are reset which imply that they are treated as being not seeded and require a reseed during next invocation.
3. The SP800-90B startup health test are initiated with all implications discussed in section 5↓. That implies that from that point on, new events must be observed and its entropy must be inserted into the entropy pool before random numbers are calculated from the entropy pool.

• SP800-90B compliant output interfaces
  • /dev/random
  • getrandom(2) system call when called with a flag that does not include GRND_INSECURE
  • get_random_bytes kernel-internal interface when being triggered by the callback registered with add_random_ready_callback
• SP800-90B non-compliant output interfaces
  • /dev/urandom
  • getrandom(2) system call when called with GRND_INSECURE
  • get_random_bytes kernel-internal interface called directly
  • randomize_page kernel-internal interface
  • get_random_u32 and get_random_u64 kernel-internal interfaces
  • get_random_u32_wait, get_random_u64_wait, get_random_int_wait, and get_random_long_wait kernel-internal interfaces

2.6 HID Event Processing

1. The LRNG checks if the received event value is identical to the previous one. If so, the event is discarded to prevent auto-repeats and the like to be processed.
2. The event values are concatenated to the per-CPU collection pool for interrupts as well. This is depicted in figure 3↑ where the HID data is processed as the “other event data”.

2.7 LRNG-external NoiseAuxiliary Entropy Pool - LRNG-external Entropy Sources

2.7.1 Kernel Hardware Random Number Generator Drivers

2.7.2 Injecting Data From User Space

• When writing data into /dev/random or /dev/urandom, the data is added to the auxiliary pool and triggers a reseed of the DRNGs at the time the next random number is about to be generated. The LRNG assumes it has zero bits of entropy.
• When using the privileged IOCTL of RNDADDENTROPY with /dev/random, the caller can inject entropic data into the auxiliary pool and define the amount of entropy associated with that data.

2.7.3 Auxiliary Pool

1. Data is inserted the same way as data is added into the per-CPU entropy pools. The auxiliary pool technically is the message digest state where new data is inserted into the pool by performing a hash update operation.
2. When entropy is to be extracted from the auxiliary pool, a hash final operation is performed which is immediately followed by a hash init operation to initialize the hash context for new data.
3. The generated message digest is truncated to the extractedamount of data requested by the DRNG (e.g. either 256 or 384 bits) entropy and returned to the caller. Note, the auxiliary pool output is not truncated to the amount of entropy the data contains because the entropy provider may add data to the auxiliary pool without entropy, e.g. by simply writing to /dev/random. Thus, it may be possible that the auxiliary pool contains zero bits of entropy but yet contains data that should be used to ‘‘stir’’ the DRNG state.

Figure 5 Auxiliary Pool Processing

2.8 Jitter RNG - LRNG-external Entropy Source

2.8.1 Entropy of CPU Jitter RNG Noise SourceEntropy Source

2.9 CPU-base Entropy Source - LRNG-external Entropy Source

• CPU entropy source provides full entropy: The CPU entropy source is queried for the amount of data which is stored in the temporary seed buffer.
• CPU entropy source provides less than full entropy: For this entropy source, the LRNG contains the information about how much data must be fetched from the CPU entropy source to get full entropy. The required amount of data is pulled from the CPU entropy source and conditioned with the hash currently in use by the LRNG. The calculated message digest is truncated to the requested amount of data which is stored in the temporary seed buffer.

2.9.1 Entropy of CPU NoiseEntropy Source

2.10 DRNG Seeding Operation

1. The first block is filled with data copied the message digest from the auxiliary pool.
2. The second block contains the hash outputmessage digest calculated from all per-CPU entropy pools as depicted in figure 3↑ That buffer receives as much data from the hash operation as entropy can be pulled from the entropy pools. In the worst case when no new interrupts are received a zero buffer will be injected into the DRNG. This is performed by iterating over all per-CPU entropy pools and:
   1. Perform a hash update operation to inject the current content of the per-CPU collection pool into the per-CPU entropy pool.
   2. Perform a hash final operation on the per-CPU entropy pool to obtain the message digest.
   3. That message digest is used to re-initialize the per-CPU entropy pool with a hash init and hash update operation to ensure backward secrecy.
   4. Also, the message digest is fed into the hash operation to collect the output from all entropy pools.
   Once the message digest from all is obtained, it is truncated to the amount of entropy present in all entropy pools.
3. The third and fourth 256-bit blocks are dedicated the fast noiseentropy sources and is filled with data from those noise sourceentropy sources – i.e. RDSEED on Intel x86 CPUs or equivalent sources on other CPUs and the Jitter RNG. If the fast noise sources is deactivated, its 256 bit block is zero and zero bits of entropy is assumed for this block. The fast noise source is only pulled if either entropy was obtained from the slow noise sources or the data is intended for the DRNG. The reason is that the fast noise sources can dominate the slow noise sources when much entropic data is required.

2.10.1 DRNG May Become Not Fully Seeded

2.11 Cryptographic Primitives Used By LRNG

2.11.1 DRBG

2.11.2 ChaCha20 DRNG

Figure 6 ChaCha20 DRNG Operation

1. generating one output block of ChaCha20,
2. partition the generated ChaCha20 block into two key-sized chunks,
3. and XOR both chunks with the key part of the ChaCha20 state.

1. The key-size seed chunk is XORed into the ChaCha20 key location of the state.
2. This operation is followed by invoking the state update function.
3. Repeat the previous steps for all unprocessed key-sized seed chunks.

2.11.3 PRNG Registered with Linux Kernel Crypto API

2.12 get_random_bytes in Atomic Contexts

2.13 LRNG External Interfaces

• Specifically, the get_random_int() family do not attempt to do ‘‘anti-backtracking’’. If you capture the state of the kernel (e.g. * by snapshotting the VM), you can figure out previous get_random_int() return values. But if the value is stored in the kernel anyway, this is not a problem.
  It is safe to expose get_random_int() output to attackers (e.g. as * network cookies); given outputs 1..n, it’s not feasible to predict outputs 0 or n+1. The only concern is an attacker who breaks into the kernel later; the get_random_int() engine is not reseeded as often as the get_random_bytes() one.
  For network ports/cookies, stack canaries, PRNG seeds, address space layout randomization, session authentication keys, or other applications where the sensitive data is stored in the kernel in plaintext for as long as it’s sensitive, the get_random_int() family is just fine.
  Consider ASLR. We want to keep the address space secret from an outside attacker while the process is running, but once the address space is torn down, it’s of no use to an attacker any more. And it’s stored in kernel data structures as long as it’s alive, so worrying about an attacker’s ability to extrapolate it from the get_random_int() DRNG is silly.
  Even some cryptographic keys are safe to generate with get_random_int(). In particular, keys for SipHash are generally fine. Here, knowledge of the key authorizes you to do something to a kernel object (inject packets to a network connection, or flood a hash table), and the key is stored with the object being protected. Once it goes away, we no longer care if anyone knows the key.

2.14 LRNG Self-Tests

• The hash function used to obtain data from the entropy pool is tested. The power-on self test vector is taken from crypto/testmgr.h for the hash known answer test using the string ‘‘abc’’ as input.
• The ChaCha20 DRNG is tested by seeding its state, generating random numbers, and comparing them with expected data. The standalone user space ChaCha20 DRNG not only allows studying of the LRNG ChaCha20 DRNG in user space, but is also used to generate the known answers.
• The operation to store time stamps in the collection pool is tested by injecting integers in that array using the management functions and comparing the array content with expected values. The expected values for the array operation are generated during compile time in the function lrng_data_process_selftest.

• The SP800-90A DRBG is self-tested by the Linux kernel crypto API test manager during instantiation.
• When using a PRNG the LRNG kernel module lrng_kcapi.ko, its self-test is driven by the Linux kernel crypto API test manager.
• The raw noise source of the interrupt timings isare tested at runtime with at least the stuck test. In addition the SP800-90B start-up and runtime tests discussed in section 2.5.2↑ are performed if they are enabled.

2.15 LRNG Test Interfaces

• The interface /sys/kernel/debug/lrng_testing/lrng_raw_hires allows reading of the raw unconditioned noise data collected while the read operation is in progress by providing the time stamps of the events collected by the LRNG that otherwise are injected into the entropy pool. When booting the kernel with the kernel command line option lrng_testing.boot_raw_hires_test=1, the time stamps of the first 1,024 events recorded by the LRNG are stored. The first read of the lrng_raw_hires file after boot provides this data in this case.
• The interface /sys/kernel/debug/lrng_testing/lrng_raw_jiffies allows reading of the raw unconditioned Jiffies collected while the read operation is in progress by providing the Jiffies values collected by the LRNG that otherwise are injected into the entropy pool (if no high-resolution time stamp is detected). When booting the kernel with the kernel command line option lrng_testing.boot_raw_jiffies_test=1, the time stamps of the first 1,024 events recorded by the LRNG are stored. The first read of the lrng_raw_jiffies file after boot provides this data in this case.
• The interface /sys/kernel/debug/lrng_testing/lrng_raw_irq allows reading of the raw unconditioned interrupt numbers collected while the read operation is in progress by providing the interrupt number values collected by the LRNG that otherwise are injected into the entropy pool (if no high-resolution time stamp is detected) or into the random32 PRNG external to the LRNG. When booting the kernel with the kernel command line option lrng_testing.boot_raw_irq_test=1, the time stamps of the first 1,024 events recorded by the LRNG are stored. The first read of the lrng_raw_irq file after boot provides this data in this case.
• The interface /sys/kernel/debug/lrng_testing/lrng_raw_irqflags allows reading of the raw unconditioned interrupt flags collected while the read operation is in progress by providing the interrupt flag values collected by the LRNG that otherwise are injected into the entropy pool (if no high-resolution time stamp is detected) or into the random32 PRNG external to the LRNG. When booting the kernel with the kernel command line option lrng_testing.boot_raw_irqflag_test=1, the time stamps of the first 1,024 events recorded by the LRNG are stored. The first read of the lrng_raw_irqflags file after boot provides this data in this case.
• The interface /sys/kernel/debug/lrng_testing/lrng_raw_retip allows reading of the raw unconditioned return instruction pointer collected while the read operation is in progress by providing the instruction pointer 32 LSB values collected by the LRNG that otherwise are injected into the entropy pool (if no high-resolution time stamp is detected) or into the random32 PRNG external to the LRNG. When booting the kernel with the kernel command line option lrng_testing.boot_raw_retip_test=1, the time stamps of the first 1,024 events recorded by the LRNG are stored. The first read of the lrng_raw_retip file after boot provides this data in this case.
• The interface /sys/kernel/debug/lrng_testing/lrng_raw_regs allows reading of the raw unconditioned interrupt register state collected while the read operation is in progress by providing the selected register 32 LSB values collected by the LRNG that otherwise are injected into the entropy pool (if no high-resolution time stamp is detected). When booting the kernel with the kernel command line option lrng_testing.boot_raw_regs_test=1, the time stamps of the first 1,024 events recorded by the LRNG are stored. The first read of the lrng_raw_regs file after boot provides this data in this case.
• The interface /sys/kernel/debug/lrng_testing/lrng_raw_array allows reading of the raw noise data that has been stored in the per-CPU collection pool collected while the read operation is in progress. When booting the kernel with the kernel command line option lrng_testing.boot_raw_array=1, the array content of the first 1,024 events recorded by the LRNG are stored. The first read of the lrng_raw_array file after boot provides this data in this case.
• The interface /sys/kernel/debug/lrng_testing/lrng_irq_perf allows reading of the number of cycles used to process one interrupt event. This allows measuring the performance impact of the LRNG on the interrupt handler. When booting the kernel with the kernel command line option lrng_testing.boot_irq_perf=1, the performance data of the first 1,024 events recorded by the LRNG are stored. The first read of the lrng_irq_perf file after boot provides this data in this case.
• The interface /sys/kernel/debug/lrng_testing/lrng_acvt_hash allows sending data to the used hash operation to calculate a message digest that is returned to user space. With this interface ACVP testing can be implemented showing compliance of the hash implementation with a NIST reference implementation.

3 Interrupt Entropy Source Assessment

3.1 Noise Source Behavior

• When an interrupt occurs, the LRNG obtains a high-resolution time stamp. Technically it may be a cycle counter offered by the CPU that produces the time stamp which is unrelated to time, but provides a fast-moving counter.
• The time stamp is divided by the greatest common divisor (GCD) that is calculated during boot time by using the first 100 time stamps.
• After the division with the GCD, the 8 least-significant bits of the time stamp are used. The higher-order bits are discarded. These 8 bits are now subject to post-processing via the collection pool, the entropy pool and the DRNG.

3.1.1 Distribution of Raw Data

Figure 7 RISC-V Raw Noise Source Data Distribution

• A histogram of the number of time stamps received for each of the 256 possible time stamp values is depicted.
• The 25% and 75% quartiles of the distribution are marked with the two green lines. They are at the time stamp value of 63 and 192, respectively
• The mean of the distribution is marked with the red line which is 127.45.
• The median of the distribution is marked with the blue line at 128.
• The black line marks the distribution of the time stamps.
• The standard derivation is not depicted, but it is at 73.89.
• The variation coefficient is not shown in the figure, but it is 0.579801.

• Asymptotic significance P: 0.2343
• Degrees of freedom: 255

Figure 8 USB Armory Mark II: Raw Noise Source Data

Figure 9 Periodic timer interrupt: Specific ARMv7 System Raw Noise Source Data

Figure 10 IBM System Z Raw Noise Source Data

3.1.2 Greatest Common Divisor Assessment

Figure 11 Without GCD - Raw Noise Source Data Distribution

• A histogram of the number of time stamps received for each of the 256 possible time stamp values is depicted.
• The 25% and 75% quartiles of the distribution are marked with the two green lines. They are at the time stamp value of 63 and 188, respectively
• The mean of the distribution is marked with the red line which is 125.99.
• The median of the distribution is marked with the blue line at 128.
• The standard derivation is not depicted, but it is at 73.84.
• The variation coefficient is not shown in the figure, but it is 0.586089.
• 𝜒² P value for equi-distribution Goodness-of-Fit test: 0.4263
• 𝜒² degrees of freedom for equi-distribution Goodness-of-Fit test: 63

Figure 12 With GCD - Raw Noise Source Data Distribution

• A histogram of the number of time stamps received for each of the 256 possible time stamp values is depicted.
• The 25% and 75% quartiles of the distribution are marked with the two green lines. They are at the time stamp value of 64 and 192, respectively
• The mean of the distribution is marked with the red line which is 127.58.
• The median of the distribution is marked with the blue line at 124.
• The standard derivation is not depicted, but it is at 73.93.
• The variation coefficient is not shown in the figure, but it is 0.579468.
• 𝜒² P value for equi-distribution Goodness-of-Fit test: 0.3181
• 𝜒² degrees of freedom for equi-distribution Goodness-of-Fit test: 255

3.1.3 Worst and Regular Case Distribution

• Worst case
  • 25% quartile: 64
  • Median: 128
  • Mean: 127.6
  • 75% quartile: 192
  • Standard derivation: 73.91
  • Variation coefficient: 0.579221
  • 𝜒² P value for equi-distribution Goodness-of-Fit test: 0.9445
  • 𝜒² degrees of freedom for equi-distribution Goodness-of-Fit test: 255
• Regular case
  • 25% quartile: 63
  • Median: 128
  • Mean: 127.52
  • 75% quartile: 192
  • Standard derivation: 74
  • Variation coefficient: 0.580276
  • 𝜒² P value for equi-distribution Goodness-of-Fit test: 0.4693
  • 𝜒² degrees of freedom for equi-distribution Goodness-of-Fit test: 255

3.2 FIPS 140-2 Compliance

3.2.1 FIPS 140-2 IG 7.18 Requirement For Statistical Testing

• Raw Entropy Tests: The tests obtain the raw unconditioned and unprocessed noise information and records it for analysis with the SP800-90B non-IID statistical test tool. The test tool includes the gathering of raw entropy for one execution run as well as for the restart tests required in SP800-90B section 3.1.4. The tool adjusts the data to be processed by the SP800-90B statistical test tool. The test tool provides the SP800-90B minimum entropy values.

3.2.2 FIPS 140-2 IG 7.18 Heuristic Analysis

3.2.3 FIPS 140-2 IG 7.18 Additional Comment 1

3.2.4 FIPS 140-2 IG 7.18 Additional Comment 2

3.2.5 FIPS 140-2 IG 7.18 Additional Comment 3

• For collecting of entropy data from the noise sourceentropy sources, an approved message digest operation is used.
• For reading the entropy pool and compressing the entropy data, the hash operation is used. The security strength of the LRNG is the minimum of the DRBG security strength and the security strength of the hash following [5] section 3.1.5.1.1 table 1. All ciphers can be tested via ACVT, including the LRNG-builtin SHA-1 or SHA-256 hash implementation.

3.2.6 FIPS 140-2 IG 7.18 Additional Comment 4

3.2.7 FIPS 140-2 IG 7.18 Additional Comment 6

3.2.8 FIPS 140-2 IG 7.18 Additional Comment 9

3.3 SP800-90B Compliance

3.3.1 SP800-90B Section 3.1.1

3.3.2 SP800-90B Section 3.1.2

3.3.3 SP800-90B Section 3.1.3

1. Gathering of the raw entropy data of the time stamps.
2. Obtaining the four least significant bits of each time stamp and concatenate them to form a bit stream.
3. The bit stream is processed with the SP800-90B entropy testing tool to gather the minimum entropy.

3.3.4 SP800-90B Section 3.1.4

1. Gathering of the raw restart entropy data of the time stamps.
2. Obtaining the four least significant bits of each time stamp either row-wise or column-wise and concatenate them to form a bit stream. There are 1,000 bit streams row-wise, and 1,000 bit streams column-wise boundary generated.
3. The bit streams are processed with the SP800-90B entropy testing tool to gather the minimum entropy.

• Using the 8 least significant bits of the time stamps in column-wise assessment – lowest entropy value of all 1,000 column entries: 3.455504
• Using the 8 least significant bits of the time stamps in row-wise assessment – lowest entropy value of all 1,000 column entries: 3.393808
• Sanity check of the 1,000 x 1,000 matrix passes with value of one

3.3.5 SP800-90B Section 3.1.5

• ChaCha20: SHA-256 in normal case, SHA-1 if kernel is not compiled with CONFIG_CRYPTO
• SP800-90A Hash DRBG: SHA-512
• SP800-90A HMAC DRBG: SHA-512
• SP800-90A CTR DRBG: SHA-512

• Compression of entropy delivered from the interrupt noise sourceentropy source when adding the entropy into the per-CPU entropy pools.
• Compression of entropy delivered from one or more LRNG-external entropy sources when adding the entropy into the auxiliary pool.
• Compression of entropy delivered by the different per-CPU entropy pools when ‘‘reading’’ the entropy pools.

• Function 2↑:
  • n_{inper − CPU pool} equals to 8,192 bits as the per-CPU entropy pool obtains its input data from the collection pool that has a size of 8,192 bits (1,024 * 8 bits) [W]  [W] Section 5.2↓ outlines that the LRNG collection size can be modified at compile time where the default is 1,024. When a different collection size is chosen, the value needs to be adjusted accordingly. Yet, such modified value has no impact to the entropy analysis. .
  • n_{outper − CPU pool} is the message digest size in bits.
  • nw_{per − CPU pool} is the message digest size in bits.
• Function 3↑:
  • n_inaux pool equals to 512 bits as the auxiliary pool pool size is 512 bits in size plus the provided input data.
  • n_outaux pool is the message digest size in bits.
  • nw_aux pool is the message digest size in bits.
• Function 4↑:
  • n_{inhash pools} equals to \mathop∑^max CPU_a = 0n_{outper − CPU poola} + n_outhash aux
  • n_{outhash pools} is the message digest size in bits.
  • nw_hash pools is the message digest size in bits.

3.3.6 SP800-90B Section 3.1.5.1

• The entropy content of the input h_{inper − CPU pool}: The input entropy of the hash used to process the per-CPU entropy pool is equal to the entropy provided by the per-CPU collection pool and the entropy already present in the per-CPU entropy pool considering that both data components are hashed at the same time to form a new per-CPU entropy pool state. Of course, the entropy held in the per-CPU entropy pool will never be larger than the digest size of the used hash which is compliant to [5] section 3.1.5.1.1 table 1.
• The entropy content of the input h_inaux pool: The input entropy of the hash used to process the auxiliary pool is equal to the entropy provided by the noise source and the already collected entropy in the auxiliary pool considering that both data components are hashed at the same time to form a new auxiliary pool state. Of course, the entropy held in the auxiliary pool will never be larger than the digest size of the used hash which is compliant to [5] section 3.1.5.1.1 table 1.
• The entropy content of the input h_{inhash pools}: The input entropy of the hash used to process the entire entropy pool is equal to the entropy found in all per-CPU entropy pools managed by the hash operation and the auxiliary pool. Again, the entropy generated by the hash will never be larger than the digest size of the used hash which is compliant to [5] section 3.1.5.1.1 table 1.

• h_{outSHA − 512} = min(h_in, n_{outSHA − 512}), 
• h_{outSHA − 256} = min(h_in, n_{outSHA − 256}), or
• h_{outSHA − 1} = min(h_in, n_{outSHA − 160}).

1. h_aux pool = 105 − 105 = 0 leaving h_{snot debited} = 256 − 105 = 151
2. h_{per − CPU poolCPU0} = 185 − 185 = 0 leaving h_{snot debited} = 256 − 185 = 71
3. h_{per − CPU poolCPU1} = 123 − 71 = 52

1. h_aux pool = 155 − 155 = 0 leaving h_{snot debited} = 256 − 155 = 101 and leaving h_{per − CPU poolnot debited} = 128
2. h_{per − CPU poolCPU0} = 80 − 80 = 0 leaving h_{snot debited} = 256 − 155 − 80 = 21 and leaving h_{per − CPU poolnot debited} = 128 − 80 = 48
3. h_{per − CPU poolCPU1} = 123 − max(48, 21) = 75

3.3.7 SP800-90B Section 3.1.6

• The noise source of the timing of the occurrence of interrupts. The entire SP800-90B analysis covers this one noise source. Thus, the requirements in this section for the interrupt noise source are trivially met.
• Auxiliary data delivered as part of interrupts: HID event data. This data is concatenated with the interrupt time stamps into the collection pool. Yet it is always credited with zero bits of entropy.
• The Jitter RNG: This noise source is a complete stand-alone noise source whose compliance to SP800-90B is vetted independently. If the user considers this noise source to be not SP800-90B compliant, it may credit it with zero bits of entropy as outlined in section 2.5.2↑.
• The CPU-based noise source like Intel RDRAND: Like the Jitter RNG, this noise source is a complete stand-alone noise source whose SP800-90B compliance is vetted independently. If the user considers this noise source to be not SP800-90B compliant, it may credit it with zero bits of entropy as outlined in section 2.5.2↑.
• A user-space RNGD is allowed to feed entropy into the LRNG via the RNDADDENTROPY IOCTL. This data is received and processed by the LRNG with an approved hash. The data is stored in the auxiliary pool. Similarly all other user space data is fed into the auxiliary pool.
• A kernel space hardware noise source is allowed to feed entropy into the LRNG via the add_hwgenerator_randomness function. The data is processed identically to user space entropy data by applying an approved hash and storing it in the auxiliary pool.

3.3.8 SP800-90B Section 3.2.1 Requirement 1

3.3.9 SP800-90B Section 3.2.1 Requirement 2

3.3.10 SP800-90B Section 3.2.1 Requirement 3

3.3.11 SP800-90B Section 3.2.1 Requirement 4

3.3.12 SP800-90B Section 3.2.1 Requirement 5

1. Switch the LRNG into raw entropy generation mode. This implies that each raw entropy event is fed to the raw entropy collection interface and not processed by the per-CPU collection pool or otherwise used.
2. When an interrupt event is received, forward the time stamp holding the entropy to a ring buffer. This operation is performed repeatedly until the ring buffer is full or the user space application read that ring buffer.
3. When an application requests the reading of the ring buffer, the data is extracted from the kernel and the ring buffer is cleared.

3.3.13 SP800-90B Section 3.2.1 Requirement 6

3.3.14 SP800-90B Section 3.2.1 Requirement 7

3.3.15 SP800-90B Section 3.2.2 Requirement 1

3.3.16 SP800-90B Section 3.2.2 Requirement 2

3.3.17 SP800-90B Section 3.2.2 Requirement 3

3.3.18 SP800-90B Section 3.2.2 Requirement 4

3.3.19 SP800-90B Section 3.2.2 Requirement 5

3.3.20 SP800-90B Section 3.2.2 Requirement 6

3.3.21 SP800-90B Section 3.2.2 Requirement 7

3.3.22 SP800-90B Section 3.2.3 Requirement 1

3.3.23 SP800-90B Section 3.2.3 Requirement 2

3.3.24 SP800-90B Section 3.2.3 Requirement 3

3.3.25 SP800-90B Section 3.2.3 Requirement 4

3.3.26 SP800-90B Section 3.2.3 Requirement 5

3.3.27 SP800-90B Section 3.2.4 Requirement 1

3.3.28 SP800-90B Section 3.2.4 Requirement 2

3.3.29 SP800-90B Section 3.2.4 Requirement 3

3.3.30 SP800-90B Section 3.2.4 Requirement 4

3.3.31 SP800-90B Section 3.2.4 Requirement 5

3.3.32 SP800-90B Section 3.2.4 Requirement 6

3.3.33 SP800-90B Section 3.2.4 Requirement 7

3.3.34 SP800-90B Section 4.3 Requirement 1

3.3.35 SP800-90B Section 4.3 Requirement 2

• Emits a failure log,
• Resets the noise source, and
• Restarts the SP800-90B startup health tests.

3.3.36 SP800-90B Section 4.3 Requirement 3

• RCT: The false positive rate is α = 2^− 30 and therefore complies with the recommended false positive probability.
• APT: The cut-off value is set to 325 compliant to SP800-90B section 4.4.2 for non-binary data at a significance level of α = 2^− 30 with time stamp is assumed to at least provide one bit of entropy, i.e. H = 1 [X]  [X] Note, the referenced Excel function seems to be imprecise when calculating the value. The data has been obtained using R-Project with the formula of 1 + qbinom(1 − 2^− 30, 512, 2^− 1)..

3.3.37 SP800-90B Section 4.3 Requirement 4

3.3.38 SP800-90B Section 4.3 Requirement 5

3.3.39 SP800-90B Section 4.3 Requirement 6

3.3.40 SP800-90B Section 4.3 Requirement 7

• During startup, the RCT and the APT are applied to 1,024 samples. The startup test can be triggered again when the caller reboots the kernel.
• At runtime, the RCT is applied to each received time stamp. The APT collects 512 time stamps. The APT is calculated over all 512 time stamps. If the test fails, the entire LRNG is reset to drop all existing entropy and the startup testing is performed again.

3.3.41 SP800-90B Section 4.3 Requirement 8

3.3.42 SP800-90B Section 4.3 Requirement 9

3.3.43 SP800-90B Section 4.4

• When the RCT passes, the counter is set to zero for the next time delta to arrive. In mathematical terms, the verification of back-to-back values being not identical is the calculation of the first discrete derivative of the time stamp to show that it is not zero. In addition, the LRNG enhances the RCT by calculating also the second and third discrete derivative of the time stamp to be concatenated with the per-CPU collection pool. With that, up to 8 consecutive time stamp values are assessed. All derivatives must always be non-zero in order to pass the RCT. If one discrete derivative shows a zero, the RCT counter is increased. Thus, the addition of the second and third derivative makes the RCT even more conservative. Hence, the first discrete derivative is considered to be identical to the ‘‘approved’’ RCT specified in SP800-90B section 4.4. In addition, linear and exponential patterns are identified with the second and third discrete derivative, respectively. As the additional pattern recognition do not invalidate the mandatory pattern recognition, this RCT approach therefore is considered to be an enhanced version of the ‘‘approved’’ RCT and thus meets the requirement (a) of SP800-90B section 4.5.

3.4 NIST Clarification Requests

3.4.1 Sensitivity of Interrupt Timing Measurements

3.4.2 Dependency Between Interrupt Timing Measurements

3.5 SP800-90B Compliant Configuration

• CONFIG_LRNG must be set to Y.
• CONFIG_LRNG_IRQ must be set to Y to enable the interrupt entropy source to which the entropy discussion of this chapter applies to.
• CONFIG_LRNG_HEALTH_TESTS must be set to Y.
• Set the configuration option of CONFIG_LRNG_IRQ_ENTROPY_RATE to the rate resulting from the entropy assessment outlined in section 3.6↓.

• The kernel must be booted with the kernel command line option of fips=1 to enable the SP800-90B health test.

• All requirements for SP800-90B documented in section 3.5↑ must be met.
• The Linux kernel configuration option of CONFIG_LRNG_DRBG must either be set to Y or to M. If it is set to M (compile the code as loadable kernel module), the kernel module lrng_drbg.ko must be loaded into the kernel before any caller to the LRNG requiring SP800-90A compliance is active.

• /dev/random,
• getrandom system call invoked with a zero flag value,
• invoking the in-kernel get_random_bytes_full when the callback registered with add_random_ready_callback was invoked.

3.6 Reuse of SP800-90B Analysis

1. Obtain raw noise data through the raw noise source interface on the intended target platform as explained in section 3.3.3↑. The obtained raw noise data must be processed by the SP800-90B tool to obtain an entropy rate which must be above 1 bit ofthe entropy rate per time delta that is configured with CONFIG_LRNG_IRQ_ENTROPY_RATE: the entropy rate must be above ²⁵⁶⁄_{CONFIG_LRNG_IRQ_ENTROPY_RATE}.
2. Obtain the restart noise data through the raw noise source interface on the intended target platform as explained in section 3.3.3↑. The obtained raw noise data must be processed by the SP800-90B tool to verify:
   1. the sanity test to apply to the noise restart data must pass, and
   2. the minimum of the row-wise and column-wise entropy rate must not be less than half of the entropy rate from measurement (1) and the entropy assessment of the noise source based on the restart data must be at least 1 bit of entropy rate per time stamp mentioned in (1).

4 LRNG Specific Configurations

4.1 SP800-90C Compliance

• The LRNG follows the construction of RBG2(NP) with the following entropy sources whose outputs are concatenated:
  • Auxiliary external entropy sources, such as user-space rngd or the in-kernel add_hwgenerator_randomness API, if available. The administrator is responsible to guarantee that this entropy source is compliant to SP800-90B if it alters the entropy estimator maintained by the LRNG via the RNDADDENTROPY IOCTL or by providing an entropy estimate via add_hwgenerator_randomness. Depending on the selected entropy source, this may be a physical or non-physical entropy source. Note, all data maintained by the auxiliary pool are processed with a vetted conditioning component. Thus, to achieve full SP800-90C compliance for such entropy sources, only one should feed data credited with entropy into the auxiliary pool.
  • Interrupt entropy source is the only entropy source that is fully maintained as part of the LRNG and is subject to a full entropy analysis following section 3.3↑. Furthermore, it is claimed to be fully SP800-90B compliant.
  • The Jitter RNG entropy source is used by the LRNG. This entropy source is a fully self-contained SP800-90B entropy source. Its SP800-90B compliance must be assessed separately. If SP800-90B compliance cannot be demonstrated, it must be awarded to credit zero bits of entropy with the configuration documented in section 2.8.1↑ or by completely disabling it by not selecting the kernel configuration option of CONFIG_LRNG_JENT.
  • The CPU entropy source is used by the LRNG, if available. On Intel, this uses RDSEED. This entropy source is a fully self-contained SP800-90B entropy source. Its SP800-90B compliance must be assessed separately. If SP800-90B compliance cannot be demonstrated, it must be awarded to credit zero bits of entropy with the configuration documented in section 2.9.1↑ or by completely disabling it by not selecting the kernel configuration option of CONFIG_LRNG_CPU.
  By applying Method 2 of section 3.3 in SP800-90C, the entropy provided by all entropy sources can be added which is applied when the LRNG constructs the temporary seed buffer as shown with equation 20↑.
• During instantiation of the DRBG, the LRNG tries to seed the DRBG with at least (DRBG security strength) + 128 bits = 384 bits of entropy. Only when this amount of entropy was obtained to seed the DRBG is considered to be fully seeded and is allowed to produce output. Note, the the following DRBG types are provided by the LRNG:
  • CTR DRBG with AES 256 using a derivation function (selected by default)
  • Hash DRBG with SHA2-512
  • HMAC DRBG with SHA2-512
  If the SP800-90C construction is to be used as the ‘‘randomness source’’ following bullet 5 of section ‘‘Note to Reviewer’’ in the SP800-90C document to seed another DRBG with a security strength of 256 bits, either the hash or HMAC DRBG should be used as they are capable of transporting up to 512 bits of entropy and are initially seeded with 384 bits of entropy. Thus, the SP800-90C seeding requirement of providing 384 bits of entropy can be satisfied.
• Reseeding of the DRBG can be triggered by either writing data into /dev/random or by the RNDRESEEDCRNG IOCTL. The LRNG guarantees that the reseed operation is only performed if at least 128 bits of entropy is available. If this is not available, the reseed is attempted during the next generate operation. Yet, the generate operation is conducted in any case. Nonwithstanding, the LRNG always attempts to obtain 256 bits of entropy for reseeding. This is considered appropriate because the upper limit when a reseed is ultimately triggered is 2²⁰2²⁰ generate operations or after 10 minutes, whatever is reached earlier. If the DRNG cannot be reseeded it will continue to operate until the next time this threshold is reached. The DRNG will revert to an unseeded stage if it cannot be reseeded by the time it serviced 2³⁰ generate requests since the last successful seeding operation. As this is much less than the ultimate SP800-90A requirement of at most 2⁴⁸ generate operations, the chosen approach is considered safe assuming that for one reseed operation until reaching 2⁴⁸, 256 bits of entropy are obtained from the entropy sources.

1. The administrator must use the SP800-90A DRBG LRNG extension as mentioned above to satisfy the requirement.
2. The DRBG can be ACVTS-tested to show compliance to SP800-90A. The entropy sources are to be assessed pursuant to SP800-90B as outlined in the above listing.
3. See the above listing for the reseeding support.
4. If an entropy source is not validated, its entropy estimation must be set to zero as outlined in the above listing.
5. N/A as the LRNG is claimed to conform with RBG2(NP).
6. The entropy sources are listed above. By using concatenation of the output of all entropy sources, the Method 2 SP800-90C is implemented. The entropy of all entropy sources are added.
7. Technically it is possible that all DRBG security strengths can be chosen as the DRBG supports all security strengths. Yet, the LRNG interfaces currently only support the highest security strength of 256 bits to ensure that it can be used for all use cases.
8. The entropy source output is destroyed immediately after it was used to (re)seed the DRBG. Note, the use of the seed for backward secrecy by injecting it into the auxiliary pool via the vetted conditioning operation is considered to not violate the requirement as the seed data is unrecoverable. Furthermore, the seed data is not credited with any entropy during the backward secrecy operation. Therefore, the seed data is only used to further mix the internal state of the LRNG.
9. N/A as the LRNG does not use a CTR DRBG without derivation function.
10. The LRNG attempts to instantiate a DRBG with 3/2s bits of entropy. Only if this succeeds, the DRBG becomes available. The LRNG attempts to reseed a DRBG with s bits of entropy. See the rationale above for the discussion about the minimum entropy size of the reseeding operation of 128 bits.
11. The DRBG only provides output once it is fully seeded as mandated by SP800-90C.
12. An error occurring in the interrupt entropy source triggers a full reset of the LRNG as outlined in section 2.5.2↑. If the other entropy sources are subject to a health test failures, SP800-90B mandates that they do not produce entropy. Before the first initialization of the DRBG, it is subject to a power-on self test. The LRNG performs power-up self tests as outlined in section 2.14↑.
13. This requirement is implicitly met by the fact that the LRNG only provides DRBGs with the maximum security strength of 256 bits.

4.1.1 RBG2(P) Construction Method

• Configure the interrupt entropy source to not credited entropy: bootcompile the kernel with the kernel configuration option of CONFIG_LRNG_IRQ_ENTROPY_RATE=4294967295. This setting ensures that the interrupt entropy source still collects data, but it is not credited with entropy. If it shall be completely disabled, the compile time option of CONFIG_LRNG_IRQ must be unset.
• Configure the Jitter RNG entropy source to not credit entropy: bootcompile the kernel with the kernel configuration option of CONFIG_LRNG_JENT_ENTROPY_RATE=0. If the value is set to 0, the entropy source is disabled. This option can also be set at runtimestill collects data, but it is not credited with entropy. If it shall be completely disabled, the compile time option of CONFIG_LRNG_JENT must be unset.
• Adjust the entropy rate of the CPU entropy source as needed: bootcompile the kernel with the kernel configuration option of CONFIG_LRNG_CPU_ENTROPY_RATE=256 when full entropy is assumed to be provided by the CPU entropy source. In general, set any value between 0 and 256 if the default value is not appropriate. If the value is set to 0, the entropy source is disabledstill collects data, but it is not credited with entropy. This option can also be set at runtime.If it shall be completely disabled, the compile time option of CONFIG_LRNG_CPU must be unset.
• If other hardware entropy sources are considered deliver entropy, they may inject data into the LRNG via either the add_hwgenerator_randomness or via the IOCTL RNDADDENTROPY. Note, only physical entropy sources must provide data that is credited with entropy. Any other data fed into the LRNG via those interfaces must not be credited with entropy.

• Requirement 5: With the required configuration mentioned before the LRNG will only count the physical entropy sources towards fulfilling the requested amount of entropy.

4.1.2 SP800-90C Compliant Configuration

• The kernel configuration option CONFIG_LRNG_OVERSAMPLE_ENTROPY_SOURCES is set. This option guarantees the following:
  • The final conditioning operation applied to the interrupt entropy source as well as to the auxiliary pool require 64 additional bits of entropy when obtaining data for the temporary seed buffer. This complies with the requirement specified in section 4.3.2 SP800-90C about vetted conditioning components. This ensures the conditioning components provide full entropy.
  • When the DRNG is initially seeded, it is attempted to be seeded with 384 bits of entropy at least. This complies with the requirement specified in section 6.2.1 bullet 2 of SP800-90C requiring 3/2s bits of entropy for the initial seeding. Note, the LRNG applies a step-wise seeding of 32, 128 and 256 bits of entropy during initialization. When the final step of 256 bits is to be performed, the LRNG will guarantee that at least 384 bits of entropy are collectively pulled from all entropy sources. Only if this is achieved, the SP800-90C compliant-marked interfaces of the LRNG specified in section 3.5↑ will produce random numbers.
• The option CONFIG_LRNG_DRBG must be either set to yes or module. This option ensures:
  • The used hash for the conditioning function must be capable of maintaining at least 384 bits of entropy. This is commonly only achieved with SHA-384 or SHA-512. With this option, SHA-512 is used.
  • SP800-90C implies that the DRNG is always SP800-90A compliant which is provided with this option.
• CONFIG_LRNG_ARCHRANDOM_TRUST_CPU_STRENGTH must not be set unless the CPU-based noise sourceentropy source (e.g. RDSEED on Intel) have an SP800-90B compliant entropy assessment and comply with all requirements from SP800-90B.
• CONFIG_RANDOM_TRUST_BOOTLOADER must not be set unless the data provided by the boot loader have an SP800-90B compliant entropy assessment and comply with all requirements from SP800-90B.
• Enable CONFIG_LRNG_IRQ configure the interrupt entropy source compliant to SP800-90B as outlined in section 3.5↑ if the interrupt entropy source is considered to be compliant to SP800-90B by accepting the assessment in chapter 3↑ and by applying the testing of the entropy source as outlined in section 3.6↑ on the target system.
• The kernel must be compiled with the kernel configuration option of CONFIG_LRNG_CPU_ENTROPY_RATE=0 or unset the option CONFIG_LRNG_CPU unless the CPU-based noise sourceentropy source (e.g. RDSEED on Intel) have an SP800-90B compliant entropy assessment and comply with all requirements from SP800-90B.
• The kernel must be compiled with the kernel configuration option of CONFIG_LRNG_JENT_ENTROPY_RATE=0 or unset the option CONFIG_LRNG_JENT unless the Jitter RNG noise sourceentropy source has an SP800-90B compliant entropy assessment and comply with all requirements from SP800-90B [Y]  [Y] At the time of writing, the user space Jitter RNG is SP800-90B compliant. Patches ensuring the in-kernel variant is SP800-90B compliant as well when into the kernel for version 5.8..

• The kernel must be booted in FIPS mode to ensure the oversampling for the conditioning and the initial seeding of the DRBG is applied. This is achieved with the kernel command line option of fips=1.
• If the lrng_drbg kernel module is compiled (i.e. CONFIG_LRNG_DRBG was set to module), the administrator must ensure the lrng_drbg kernel module is loaded into the kernel before the first user of the LRNG accessing the SP800-90C compliant interfaces appears. Note: it is permissible to implement a separate kernel module that provides the DRBG and the hash operation following the API defined with the lrng.h header file. However, in this case the following conditions must hold:
  • The DRBG must be SP800-90A compliant and provide 256 bits of security strength. It is permissible that the invocation of this DRBG may cause the caller to sleep. The DRBG is never called in atomic contexts.
  • If the CTR DRBG is used, it must provide a derivation function.
  • The hash that is specified with the kernel module must provide at least 384 bits of output size and security strength (i.e. either one of the following SHA2-384, SHA2-512, SHA3-384 or SHA3-512). The implementation of the hashes must not sleep or use a mutex. The hash is called in atomic contexts.
• All kernel code that uses the add_hwgenerator_randomness must either invoke the function with a zero for the entropy_bits parameter or must have an SP800-90B compliant entropy assessment and comply with all requirements from SP800-90B. For example, this call is invoked by the ATH9K driver or the hardware random number generator driver framework.
• Filling up the LRNG with entropy using either a user-space RNGD via the IOCTL RNDADDENTROPY or a kernel-space via the function add_hwgenerator_randomness is allowed. However, the caller is only allowed to claim entropy associated with the data and thus increase the LRNG entropy estimation if the noise sourceentropy source is SP800-90B compliant with its own entropy assessment.

4.2 AIS 20 / 31

5 LRNG Comparison to legacy /dev/random

5.1 Time Until Fully Initialized

$ dmesg | grep "LRNG minimally seeded"
[  1.718705] lrng_es_mgr: LRNG minimally seeded with 128 bits of entropy
--- 0 sm@x86-64 ~ --------------------------------------------------------------
$ dmesg | grep "LRNG fully seeded"
[  2.056685] lrng_es_mgr: LRNG fully seeded with 256 bits of entropy
--- 0 sm@x86-64 ~ --------------------------------------------------------------
$ dmesg | grep "random: crng init done"
[  20.932050] random: random: crng init done

$ cat /sys/module/lrng_es_archrandom/parameters/archrandom 
0
--- 0 sm@x86-64 ~ --------------------------------------------------------------
$ dmesg | grep "LRNG minimally seeded"
[  1.683981] lrng_es_mgr: LRNG minimally seeded with 128 bits of entropy
--- 0 sm@x86-64 ~ --------------------------------------------------------------
$ dmesg | grep "LRNG fully seeded"
[  2.110482] lrng_es_mgr: LRNG fully seeded with 256 bits of entropy
--- 0 sm@x86-64 ~ --------------------------------------------------------------
[  3.075414] lrng_drng: force reseed of DRNG on node 0
​

5.2 Interrupt Handler Performance

Figure 13 Average Cycle Count To Process One Interrupt Depending on Collection Size

5.3 LRNG Output Performance And DRNG Type

5.4 ChaCha20 Random Number Generator

• whether the self-feeding RNG ensures backward secrecy, and
• whether the absence of the CPU noise sourceentropy source still produces white noise.

--- 0 sm@x86-64 ~ --------------------------------------------------------------
$ dd if=/dev/urandom of=file count=1000
1000+0 Datensätze ein
1000+0 Datensätze aus
512000 bytes (512 kB, 500 KiB) copied, 0,00341658 s, 150 MB/s
--- 0 sm@x86-64 ~ --------------------------------------------------------------
$ ent file
Entropy = 7.999639 bits per byte.
​
Optimum compression would reduce the size
of this 512000 byte file by 0 percent.
​
Chi square distribution for 512000 samples is 257.07, and randomly
would exceed this value 45.19 percent of the times.
​
Arithmetic mean value of data bytes is 127.4761 (127.5 = random).
Monte Carlo value for Pi is 3.147902921 (error 0.20 percent).
Serial correlation coefficient is 0.001163 (totally uncorrelated = 0.0).
--- 0 sm@x86-64 ~ --------------------------------------------------------------
$ ent -b file
Entropy = 1.000000 bits per bit.
​
Optimum compression would reduce the size
of this 4096000 bit file by 0 percent.
​
Chi square distribution for 4096000 samples is 0.12, and randomly
would exceed this value 73.24 percent of the times.
​
Arithmetic mean value of data bits is 0.5001 (0.5 = random).
Monte Carlo value for Pi is 3.147902921 (error 0.20 percent).
Serial correlation coefficient is 0.000028 (totally uncorrelated = 0.0).

5.5 Legacy /dev/random Non-Compliance with SP800-90B

• Some form of LSFR is implemented in the function crng_slow_load.
• The LFSR applied to the fast_pool state with 4 words when injecting new data must be assessed.
• The LFSR used for the input_pool must be assessed.
• The conditioning component provided with the SHA-1 operation reading the input_pool whose output is folded in half must be assessed. This operation is almost a vetted conditioning component compliant to [5] section 3.1.5.1.1 with the exception that the output of the SHA-1 operation is folded in half. Although this document does not contain any analysis of the legacy conditioning components, the reader is reminded of table 1 of [5] section 3.1.5.1.1 which outlines the narrowest internal width of a vetted conditioning component. For the hash operation it is marked as the hash-function output size. Considering that the used operation is almost a vetted conditioning component where only the output size is 80 bits due to the folding operation, a careful analysis must be applied whether the SHA-1 operation and its output-folding operation only delivers 80 bits of output length as listed in table 1. If this is the case, it is very likely that the legacy /dev/random entropy rate is limited to 80 bits of entropy due to this operation. It is also to be noted that the SHA-1 operation does not comply to the specification, such as that it does not use the correct initialization vector and it does not perform the finalization operation including the padding specified in section 5.1.1 [6].
• The ChaCha20 DRNG used to provide random numbers via the output interfaces must be assessed as well.

A Thanks

• DJ Johnston
• Yi Mao
• Sandy Harris
• Dr. Matthias Peter
• Quentin Gouchet

B Source Code Availability

C SP800-90B Entropy Measurements

D Auxiliary Testing

• use of automated test harness validating the different LRNG configurations
• use of the kernel-internal KASAN test framework,
• use of the kernel-internal UBSAN test framework,
• use of the kernel-internal lockdep test framework,
• use of the kernel-internal Sparse test framework,
• use of the kernel-internal memory leak detector test framework,
• use of the LRNG without compiling the kernel crypto API,
• syscall validation testing,
• test of the LRNG in atomic contexts,
• the regression test suite provided with the LRNG showing that the LRNG operation with different configurations is as expected.

E Bibliographic Reference

F License

1. Redistributions of source code must retain the above copyright notice, and the entire permission notice in its entirety, including the disclaimer of warranties.
2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
3. The name of the author may not be used to endorse or promote products derived from this software without specific prior written permission.

G Change Log