/dev/random - a new approach

Hi,

The following patch set provides a complete production-
ready and yet different approach to /dev/random which is called Linux Random Number Generator (LRNG) to collect entropy within the Linux kernel. It provides the same API and ABI and can be used as a drop-in replacement. A general overview is given with [6].

The LRNG was presented at the Linux Security Summit 2021. The video of the presentation can be found at [7].

Patches 1 through 5 provide the solution that is functionality equivalent with the existing /dev/random implementation. Those patches can be applied all by themselves and provide a fully functional LRNG. Each subsequent patch provides a stand-alone additional function.

The LRNG implements at least all features of the existing /dev/random such as NUMA-node-local DRNGs. The following advantages compared to the existing /dev/random implementation are present:

* Sole use of crypto for data processing:

- Exclusive use of a hash operation for conditioning entropy data with a clear mathematical description as given in [2] 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 existing /dev/random implementation.

- 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
[2] section 2.2 compared to the large variation of different post-processing steps in the existing /dev/random implementation that have no apparent mathematical description (see [2] section 4.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 - the default is now set such that the highest performance is achieved as outlined in [2] section 4.2.

- 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 existing /dev/random as demonstrated with [2] table 2.

- Faster entropy collection during boot time to reach fully seeded level, including on virtual systems or systems with SSDs as outlined in [2] section 4.1.

- Faster processing of external data added to LRNG via /dev/random or add_hwgenerator_randomness.

* Testing

- Availability of run-time health tests of the raw unconditioned entropy source data of the interrupt entropy source to identify degradation of the available entropy as documented in [2] 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 is based on quantitative measurements and analysis following SP800-90B and not on coincidental underestimation of entropy applied by the existing /dev/random as outlined in [4] 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 [2] 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 [2] section 2.15.

- Fully testable ChaCha20 DRNG via a userspace ChaCha20 DRNG implementation [3].

- 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 [2] 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 regression tests verifying the different options provided with the LRNG.

* Entropy collection of the internal interrupt entropy source

- The LRNG is shipped with test tools allowing the collection of raw unconditioned entropy during runtime and boot time available at [1].

- Full entropy assessment and description is provided with [2] chapter 3, specifically section 3.3.6.

- Guarantee that entropy events are not credited with entropy twice (the existing /dev/random implementation credits HID/disk and interrupt events with entropy which are a derivative of each other).

* Configurable

- LRNG kernel configuration allows configuration that is functionally equivalent to the existing /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 an SP800-90A DRBG.

+ Selectively enabling of each entropy source and configuring their entropy rate.

+ Enabling of interrupt entropy source health tests.

+ Enabling of test interface allowing to enable each test interface individually.

+ Enabling of the power-up self test.

+ At compile 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 in [2]. 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 [2] section 2.5.2.

- Configurable seeding strategies are provided following different concepts.

* Run-time pluggable cryptographic implementations used for all data processing steps specified in [2] 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 access to the following types of non-sleeping 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 existing /dev/random which means that users who are conservative can use the unchanged existing /dev/random implementation.

- Back-port patches are available at [5] to apply the LRNG to LTS Linux kernel versions of 5.10, 5.4, 4.19, 4.14, and 4.4. In addition, backport patches for the kernel version 5.8, 4.12 and 4.10 are provided. Patches for other kernel versions are easily derived from the existing ones.

Booting the patch with the kernel command line option "dyndbg=file drivers/char/lrng/* +p" generates logs indicating the operation of the LRNG. Each log is pre-pended with "lrng".

An entropy analysis is performed on the following systems - details are given in [2] appendix C:

* x86 KVM virtualized guest 32 and 64 bit systems

* x86 bare metal

* older and newer ARMv7 system

* ARM64

* POWER7 LE and POWER 8 BE

* IBM Z System mainframe

* old MIPS embedded device

* RISC-V

* testing with GCC and Clang

[1] https://www.chronox.de/lrng.html - If the patch is accepted, I would be volunteering to convert the documentation into RST format and contribute it to the Linux kernel documentation directory.

[2] https://www.chronox.de/lrng/doc/lrng.pdf

[3] https://www.chronox.de/chacha20_drng.html

[4] https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publications/Studies/
LinuxRNG/LinuxRNG_EN_V4_1.pdf

[5] https://github.com/smuellerDD/lrng/tree/master/backports

[6] https://www.chronox.de/lrng/doc/lrng_presentation_v43.pdf

[7] https://www.youtube.com/watch?v=8DuhbwWkMQw&list=PLbzoR-pLrL6owx0I6v2MSwjxhtsRdtFzG&index=16

Changes (compared to the previous patch set) - individual patches are visible at https://github.com/smuellerDD/lrng/commits/master:

- Replace '/**' with '/*' in comments

- Jitter RNG ES: if configured to have zero entropy, it still returns data

- CPU ES: if configured to have zero entropy, it still returns data; allow disabling it with config option - extract CPU ES into its own patch for better assessment (patch 5)

- IRQ ES: if configured to have zero entropy, it still returns data; allow disabling it with config option - extract IRQ ES into its own patch for better assessment (patch 2)

- use hash lock only when LRNG switching support is enabled

- write_wakeup now contains the wakeup threshold in bits and is updated when the hash is updated

- fix: do not expect user space to provide entropy if it is woken up - this allows haveged to fully work

- rearrange patch set: patches 01 through 05 are the baseline to get the LRNG running covering all use cases currently available. Even this base would provide better functionality than the existing /dev/random implementation considering the use of SHA-256 and a much faster IRQ handler.

- fix: ensure that applying the oversampling rate implies a larger or equal interrupt collection in case no highres timer is present

- fix: PowerISA DARN specifies that it only delivers 0.5 bits of entropy -> CPU ES takes this into account when configured to trust CPU

- add compression support for CPU entropy sources without full entropy

Stephan Mueller (15):
Linux Random Number Generator
LRNG - IRQ entropy source
LRNG - sysctls and /proc interface
LRNG - allocate one DRNG instance per NUMA node LRNG - CPU entropy source
LRNG - add switchable DRNG support
LRNG - add common generic hash support
crypto: DRBG - externalize DRBG functions for LRNG LRNG - add SP800-90A DRBG extension
LRNG - add kernel crypto API PRNG extension
crypto: move Jitter RNG header include dir LRNG - add Jitter RNG fast noise source LRNG - add SP800-90B compliant health tests LRNG - add interface for gathering of raw entropy LRNG - add power-on and runtime self-tests

 MAINTAINERS                                   |   7 +
 crypto/drbg.c                                 |  16 +-
 crypto/jitterentropy-kcapi.c                  |   3 +-
 crypto/jitterentropy.c                        |   2 +-
 drivers/char/Kconfig                          |   2 +
 drivers/char/Makefile                         |   9 +-
 drivers/char/lrng/Kconfig                     | 589 +++++++++++++
 drivers/char/lrng/Makefile                    |  21 +
 drivers/char/lrng/lrng_aux.c                  | 136 +++
 drivers/char/lrng/lrng_chacha20.c             | 321 +++++++
 drivers/char/lrng/lrng_chacha20.h             |  25 +
 drivers/char/lrng/lrng_drbg.c                 | 198 +++++
 drivers/char/lrng/lrng_drng.c                 | 451 ++++++++++
 drivers/char/lrng/lrng_es_archrandom.c        | 226 +++++
 drivers/char/lrng/lrng_es_aux.c               | 294 +++++++
 drivers/char/lrng/lrng_es_irq.c               | 823 ++++++++++++++++++
 drivers/char/lrng/lrng_es_irq.h               |  71 ++
 drivers/char/lrng/lrng_es_jent.c              |  97 +++
 drivers/char/lrng/lrng_es_mgr.c               | 373 ++++++++
 drivers/char/lrng/lrng_health.c               | 410 +++++++++
 drivers/char/lrng/lrng_interfaces.c           | 654 ++++++++++++++
 drivers/char/lrng/lrng_internal.h             | 485 +++++++++++
 drivers/char/lrng/lrng_kcapi.c                | 227 +++++
 drivers/char/lrng/lrng_kcapi_hash.c           | 103 +++
 drivers/char/lrng/lrng_kcapi_hash.h           |  20 +
 drivers/char/lrng/lrng_numa.c                 | 122 +++
 drivers/char/lrng/lrng_proc.c                 | 199 +++++
 drivers/char/lrng/lrng_selftest.c             | 386 ++++++++
 drivers/char/lrng/lrng_switch.c               | 226 +++++
 drivers/char/lrng/lrng_testing.c              | 689 +++++++++++++++
 include/crypto/drbg.h                         |   7 +
 .../crypto/internal}/jitterentropy.h          |   0
 include/linux/lrng.h                          |  81 ++
 33 files changed, 7263 insertions(+), 10 deletions(-)
 create mode 100644 drivers/char/lrng/Kconfig
 create mode 100644 drivers/char/lrng/Makefile
 create mode 100644 drivers/char/lrng/lrng_aux.c
 create mode 100644 drivers/char/lrng/lrng_chacha20.c
 create mode 100644 drivers/char/lrng/lrng_chacha20.h
 create mode 100644 drivers/char/lrng/lrng_drbg.c
 create mode 100644 drivers/char/lrng/lrng_drng.c
 create mode 100644 drivers/char/lrng/lrng_es_archrandom.c
 create mode 100644 drivers/char/lrng/lrng_es_aux.c
 create mode 100644 drivers/char/lrng/lrng_es_irq.c
 create mode 100644 drivers/char/lrng/lrng_es_irq.h
 create mode 100644 drivers/char/lrng/lrng_es_jent.c
 create mode 100644 drivers/char/lrng/lrng_es_mgr.c
 create mode 100644 drivers/char/lrng/lrng_health.c
 create mode 100644 drivers/char/lrng/lrng_interfaces.c
 create mode 100644 drivers/char/lrng/lrng_internal.h
 create mode 100644 drivers/char/lrng/lrng_kcapi.c
 create mode 100644 drivers/char/lrng/lrng_kcapi_hash.c
 create mode 100644 drivers/char/lrng/lrng_kcapi_hash.h
 create mode 100644 drivers/char/lrng/lrng_numa.c
 create mode 100644 drivers/char/lrng/lrng_proc.c
 create mode 100644 drivers/char/lrng/lrng_selftest.c
 create mode 100644 drivers/char/lrng/lrng_switch.c
 create mode 100644 drivers/char/lrng/lrng_testing.c
 rename {crypto => include/crypto/internal}/jitterentropy.h (100%)
 create mode 100644 include/linux/lrng.h

2.31.1

In an effort to provide a flexible implementation for a random number generator that also delivers entropy during early boot time, allows replacement of the deterministic random number generation mechanism, implement the various components in separate code for easier maintenance, and provide compliance to SP800-90[A|B|C], introduce the Linux Random Number Generator (LRNG) framework.

The LRNG framework provides a flexible random number generator which allows developers and system integrators to achieve different goals by ensuring that each solution establishes a secure state.

The general design is as follows. Additional implementation details are given in [1]. The LRNG consists of the following components:

1. The LRNG implements a DRNG. The DRNG always generates the requested amount of output. When using the SP800-90A terminology it operates without prediction resistance. The 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.

In case the Linux kernel detects a NUMA system, one DRNG instance per NUMA node is maintained.

2. The DRNG is seeded by concatenating the data from the following sources which deliver data and are credited with entropy if enabled:

(a) the output of the IRQ per-CPU entropy pools,

(b) the auxiliary entropy pool,

(c) the Jitter RNG if available and enabled, and

(d) the CPU-based noise source such as Intel RDSEED.

The entropy estimate of the data of all noise sources are added to form the entropy estimate of the data used to seed the DRNG with. The LRNG ensures, however, that the DRNG after seeding is at maximum the security strength of the DRNG.

The LRNG is designed such that none of these noise sources can dominate the other noise sources to provide seed data to the DRNG during due to the following:

(a) During boot time, the amount of received entropy at the different entropy sources are the trigger points to (re)seed the DRNG.

(b) At runtime, the available entropy from the slow noise source is concatenated with a pre-defined amount of data from the fast noise sources. In addition, each DRNG reseed operation triggers external noise source providers to deliver one block of data.

3. The IRQ entropy pool collects noise data from interrupt timing. Any data received by the LRNG from the interrupt noise sources is inserted into a per-CPU entropy pool using a hash operation that can be changed during runtime. Per default, SHA-256 is used.

(a) When an interrupt occurs, the 8 least significant bits of the high-resolution time stamp divided by the greatest common divisor (GCD) is mixed into the per-CPU entropy pool. This time stamp is credited with heuristically implied entropy.

(b) HID event data like the key stroke or the mouse coordinates are mixed into the per-CPU entropy pool. This data is not credited with entropy by the LRNG.

5. Any data provided from user space by either writing to /dev/random, /dev/urandom or the IOCTL of RNDADDENTROPY on both device files are always injected into the auxiliary pool. Also, device drivers may provide data that is mixed into an auxiliary pool using the same hash that is used to process the per-CPU entropy pool. This data is not credited with entropy by the LRNG.

In addition, when a hardware random number generator covered by the Linux kernel HW generator framework wants to deliver random numbers, it is injected into the auxiliary pool as well. HW generator noise source is handled separately from the other noise source due to the fact that the HW generator framework may decide by itself when to deliver data whereas the other noise sources always requested for data driven by the LRNG operation. Similarly any user space provided data is inserted into the entropy pool.

When seed data for the DRNG is to be generated, all per-CPU entropy pools are hashed. The message digest forms the data used for seeding the DRNG.

To speed up the interrupt handling code of the LRNG, the time stamp collected for an interrupt event is divided by the greatest common divisor to eliminate fixed low bits and then truncated to the 8 least significant bits. 1024 truncated time stamps are concatenated and then jointly inserted into the per-CPU entropy pool. During boot time, until the fully seeded stage is reached, each time stamp with its 32 least significant bits is are concatenated. When 1024/32 = 32 such events are received, they are injected into the per-CPU entropy pool.

The LRNG allows the DRNG mechanism to be changed at runtime. Per default, a ChaCha20-based DRNG is used. The ChaCha20-DRNG implemented for the LRNG is also provided as a stand-alone user space deterministic random number generator. The LRNG also offers an SP800-90A DRBG based on the Linux kernel crypto API DRBG implementation.

The processing of entropic data from the noise source before injecting them into the DRNG is performed with the following mathematical operations:

1. Truncation: The received time stamps divided by the GCD are truncated to 8 least significant bits (or 32 least significant bits during boot time)

2. Concatenation: The received and truncated time stamps as well as auxiliary 32 bit words are concatenated to fill the per-CPU data array that is capable of holding 64 8-bit words.

3. Hashing: A set of concatenated time stamp data received from the interrupts are hashed together with the current existing per-CPU entropy pool state. The resulting message digest is the new per-CPU entropy pool state.

4. Hashing: When new data is added to the auxiliary pool, the data is hashed together with the auxiliary pool to form a new auxiliary pool state.

5. Hashing: A message digest of all per-CPU entropy pools and the is calculated which forms the new auxiliary pool state.

6. 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 slow noise source output buffer.

7. Concatenation: The temporary seed buffer used to seed the DRNG is a concatenation of the slow noise source buffer, the Jitter RNG output, the CPU noise source output, and the current time.

The DRNG always tries to seed itself with 256 bits of entropy, except during boot. In any case, if the noise sources cannot deliver that amount, the available entropy is used and the DRNG keeps track on how much entropy it was seeded with. The entropy implied by the LRNG available in the entropy pool may be too conservative. To ensure that during boot time all available entropy from the entropy pool is transferred to the DRNG, the hash_df function always generates 256 data bits during boot to seed the DRNG. During boot, the DRNG is seeded as follows:

1. The DRNG is reseeded from the entropy sources if the entropy sources collectively have at least 32 bits of entropy. The goal of this step is to ensure that the DRNG receives some initial entropy as early as possible.

2. The DRNG is reseeded from the entropy sources if all entropy sources collectively can provide at least 128 bits of entropy.

3. The DRNG is reseeded from the entropy sources if all entropy sources collectively can provide at least 256 bits.

At the time of the reseeding steps, the DRNG requests as much entropy as is available in order to skip certain steps and reach the seeding level of 256 bits. This may imply that one or more of the aforementioned steps are skipped.

Before the DRNG is seeded with 256 bits of entropy in step 3, requests of random data from /dev/random and the getrandom system call are not processed.

The reseeding of the DRNG always ensures that all entropy sources collectively can deliver at least 128 entropy bits during runtime once the DRNG is fully seeded.

The DRNG operates as deterministic random number generator with the following properties:

* 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 backtracking resistance.

* The DRNG is reseeded with whatever entropy is available - in the worst case where no additional entropy can be provided by the entropy 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:

- If the last reseeding of the DRNG is more than 600 seconds ago, or

- 2^20 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.

- If the DRNG was not successfully reseeded after 2^30 generate requests, the DRNG reverts back to an unseeded stage implying that the blocking interfaces of /dev/random and getrandom will block again.

The chosen values prevent high-volume requests from user space to cause frequent reseeding operations which drag down the performance of the DRNG.

With the automatic reseeding after 600 seconds, the LRNG is triggered to reseed itself before the first request after a suspend that put the hardware to sleep for longer than 600 seconds.

To support smaller devices including IoT environments, this patch allows reducing the runtime memory footprint of the LRNG at compile time by selecting smaller collection data sizes.

When selecting the compilation of a kernel for a small environment, prevent the allocation of a buffer up to 4096 bytes to serve user space requests. In this case, the stack variable of 64 bytes is used to serve all user space requests.

The LRNG has the following properties:

* internal noise source: interrupts timing with fast boot time seeding

* high performance of interrupt handling code: The LRNG impact on the interrupt handling has been reduced to a minimum. On one example system, the LRNG interrupt handling code in its fastest configuration executes within an average 55 cycles whereas the existing /dev/random on the same device takes about 97 cycles when measuring the execution time of add_interrupt_randomness().

* use of almost never contended lock for hashing operation to collect raw entropy supporting concurrency-free use of massive parallel systems - worst case rate of contention is the number of DRNG reseeds, usually: number of NUMA nodes contentions per 5 minutes.

* use of standalone ChaCha20 based RNG with the option to use a different DRNG selectable at compile time

* instantiate one DRNG per NUMA node

* support for runtime switchable output DRNGs

* use of runtime-switchable hash for conditioning implementation following widely accepted approach

* compile-time selectable collection size

* support of small systems by allowing the reduction of the runtime memory needs

Further details including the rationale for the design choices and properties of the LRNG together with testing is provided at [1]. In addition, the documentation explains the conducted regression tests to verify that the LRNG is API and ABI compatible with the existing /dev/random implementation.

Note, this patch covers the entropy sources manager, the API implementation, the built-in ChaCha20 DRNG and the auxiliary entropy pool.

[1] https://www.chronox.de/lrng.html

Mathematical aspects Reviewed-by: "Peter, Matthias" <[email protected]>

---
 MAINTAINERS                         |   7 +
 drivers/char/Kconfig                |   2 +
 drivers/char/Makefile               |   9 +-
 drivers/char/lrng/Kconfig           |  58 +++
 drivers/char/lrng/Makefile          |   8 +
 drivers/char/lrng/lrng_aux.c        | 136 ++++++
 drivers/char/lrng/lrng_chacha20.c   | 321 ++++++++++++++
 drivers/char/lrng/lrng_chacha20.h   |  25 ++
 drivers/char/lrng/lrng_drng.c       | 451 +++++++++++++++++++
 drivers/char/lrng/lrng_es_aux.c     | 294 +++++++++++++
 drivers/char/lrng/lrng_es_mgr.c     | 373 ++++++++++++++++
 drivers/char/lrng/lrng_interfaces.c | 656 ++++++++++++++++++++++++++++
 drivers/char/lrng/lrng_internal.h   | 485 ++++++++++++++++++++
 include/linux/lrng.h                |  81 ++++
 14 files changed, 2905 insertions(+), 1 deletion(-)
 create mode 100644 drivers/char/lrng/Kconfig
 create mode 100644 drivers/char/lrng/Makefile
 create mode 100644 drivers/char/lrng/lrng_aux.c
 create mode 100644 drivers/char/lrng/lrng_chacha20.c
 create mode 100644 drivers/char/lrng/lrng_chacha20.h
 create mode 100644 drivers/char/lrng/lrng_drng.c
 create mode 100644 drivers/char/lrng/lrng_es_aux.c
 create mode 100644 drivers/char/lrng/lrng_es_mgr.c
 create mode 100644 drivers/char/lrng/lrng_interfaces.c
 create mode 100644 drivers/char/lrng/lrng_internal.h
 create mode 100644 include/linux/lrng.h

index c79388b78818..ea4f88da1601 100644
@@ -10817,6 +10817,13 @@ F:	Documentation/litmus-tests/
 F:	Documentation/memory-barriers.txt
 F:	tools/memory-model/
 
+LINUX RANDOM NUMBER GENERATOR (LRNG) DRIVER
+M:	Stephan Mueller <[email protected]>
+S:	Maintained
+W:	https://www.chronox.de/lrng.html
+F:	drivers/char/lrng/*
+F:	include/linux/lrng.h
+
 LIS3LV02D ACCELEROMETER DRIVER
 M:	Eric Piel <[email protected]>
 S:	Maintained

index 740811893c57..a52d575ca756 100644
@@ -451,4 +451,6 @@ config RANDOM_TRUST_BOOTLOADER
 	pool. Otherwise, say N here so it will be regarded as device input that
 	only mixes the entropy pool.
 
+source "drivers/char/lrng/Kconfig"
+
 endmenu

index 264eb398fdd4..7371f7464a49 100644
@@ -3,7 +3,14 @@
 # Makefile for the kernel character device drivers.
 #
 
-obj-y				+= mem.o random.o
+obj-y				+= mem.o
+
+ifeq ($(CONFIG_LRNG),y)
+  obj-y				+= lrng/
+else
+  obj-y				+= random.o
+endif
+
 obj-$(CONFIG_TTY_PRINTK)	+= ttyprintk.o
 obj-y				+= misc.o
 obj-$(CONFIG_ATARI_DSP56K)	+= dsp56k.o

new file mode 100644
index 000000000000..6f4603f897cd
@@ -0,0 +1,8 @@
+# SPDX-License-Identifier: GPL-2.0
+#
+# Makefile for the Linux Random Number Generator.
+#
+
+obj-y				+= lrng_es_mgr.o lrng_aux.o \
+				   lrng_drng.o lrng_chacha20.o \
+				   lrng_interfaces.o lrng_es_aux.o

new file mode 100644
index 000000000000..bd0c0bee38f3
@@ -0,0 +1,25 @@
+/* SPDX-License-Identifier: GPL-2.0 OR BSD-2-Clause */
+/*
+ * LRNG ChaCha20 definitions
+ *
+ * Copyright (C) 2016 - 2021, Stephan Mueller <[email protected]>
+ */
+
+#include <crypto/chacha.h>
+
+/* State according to RFC 7539 section 2.3 */
+struct chacha20_block {
+	u32 constants[4];
+	union {
+#define CHACHA_KEY_SIZE_WORDS (CHACHA_KEY_SIZE / sizeof(u32))
+		u32 u[CHACHA_KEY_SIZE_WORDS];
+		u8  b[CHACHA_KEY_SIZE];
+	} key;
+	u32 counter;
+	u32 nonce[3];
+};
+
+static inline void lrng_cc20_init_rfc7539(struct chacha20_block *chacha20)
+{
+	chacha_init_consts(chacha20->constants);
+}

2.31.1

[]

Hi Stephan,

You've posted it again, and yet I still believe this is not the correct design or direction. I do not think the explicit goal of extended configurability ("flexibility") or the explicit goal of being FIPS compatible represent good directions, and I think this introduces new problems rather than solving any existing ones. While there are ways the current RNG could or even should be improved -- or rewritten -- this approach is still not that, no matter how many times you post it. It is almost as though you hope this somehow gets accepted through a general apathy that might develop by the 1000th revision, when cranks like me and others no longer have the motivation to keep responding with the same thing. But here we are again.

My own experience pushing something that didn't have substantial enough buy-in from existing maintainers (the Zinc crypto library) ultimately led me to stop pushing in order to not alienate folks, step back, and listen a bit. Eventually somebody reached out to work with me (Ard) and we submitted a good compromise collaboration that we all generally felt better about. In this case, your cryptographic design tastes are sufficiently divergent from mine that I'm not sure how far such a thing would go, but it also seems to me that continually pushing the same thing over and over isn't winning you any points here either. Submission by attrition is not an outcome anybody should want.

Sorry to be so blunt. It's just that my, "I don't like this" is the same as it was the last time, and I'm not aware of anything significant in that area changing this time.

Jason

Am Sonntag, 21. November 2021, 23:42:33 CET schrieb Jason A. Donenfeld:

Hi Jason,

The members from the Linux distributions that are on copy on this may tell you a different story. They all developed their own downstream patches to somehow add the flexibility that is needed for them. So, we have a great deal of fragmentation at the resting-foundation of Linux cryptography.

Then the implementation of the flexibility in the LRNG is done such that irrespecitve of which options are selected, the LRNG operates always at a secure state.

I have received numerous technical comments from various Linux developers. All were integrated. None of these comments hinted to requestes in changing the design.

That said, even when you refer to already suggested architectural differnces, I yet have to first receive them,

Ciao
Stephan

What distros specifically have patches in their kernels that do different things to the random code path? Do you have pointers to those patches anywhere? Why have the distros not submitted their changes upstream?

thanks,

greg k-h

Am Montag, 22. November 2021, 07:02:14 CET schrieb Greg Kroah-Hartman:

Hi Greg,

I will leave the representatives from the distros to chime in and point to these patches.

Yet, these changes are commonly a band-aid only that have some additional drawbacks. Bottom line, there is no appropriate way with the current code to allow vendors what they want to achieve. One hint to what changes vendors are attempting can be found in [1] slide 20.

[1] https://www.chronox.de/lrng/doc/lrng_presentation_v43.pdf

Ciao
Stephan

Then why not work with the distros to get these changes merged into the kernel tree? They know that keeping things out-of-the-tree costs them time and money, so why are they keeping them there?

I recommend getting the distros to chime in on what their requirements are for the random code would probably be best as they are the ones that take on the "random fips requirement of the day" more than anyone else.

What exactly do vendors "want to achieve"? Where are they saying this?

I see nothing on that slide that mentions actual requirements other than "the current code does not match this random government regulation".

Please provide valid reasons, from distros.

thanks,

greg k-h

I can speak for my distro.
We have not proposed them because they are hacks, we know they are hacks, and we know they are not the long term solution.
Yet we have no better way (in our products, today) so far to deal with these issues because what is needed is an effort like LRNG (does not have to be this specific implementation), because hacks will not cut it in the long term.

Greg,
I think you can takes Stephan's introduction and supporting material from this patchset to see what are the requirements. These patches have not been maturing in a void, but Stephan basically distilled discussions between multiple vendors as well as regulatory bodies (as you can see he has reviews from BSI and NIST requirements are also fully represented here).

He addressed a few aspects I can mention but are not the only ones:
performance (esp on NUMA systems), not blocking at boot due to lack of entropy, NIST/BSI conformance, flexibility so that future regulatory requirements can be easily integrated and upstreamed.

Please let me know in what format you want to see these requirements, and I will work with other to provide them.

Simo.

Simo Sorce
RHEL Crypto Team
Red Hat, Inc

Kernel support for FIPS validated crypto would be very useful, IMHO.

Currently most folks I know and consult with use CentOS because CentOS is free and includes the FIPS canister for OpenSSL. Several folks I know and consult with don't have a solution because they use Debian derivatives, like Ubuntu. They use Ubuntu because Ubuntu offers the image processing packages they need out of the box.

Moving the validated crypto into the kernel would be useful since all distros can provide it without the need for one-off patches.

What I am less clear about.... NIST is only one standard body, and not everyone trusts the US. There are other bodies that should probably be represented, like KISA. So the big question becomes, how does the kernel offer "approved" crypto for different consumers? (where "approved" means blessed by some agency like NIST or KISA).

Jeff

Am Montag, 22. November 2021, 22:06:55 CET schrieb Jeffrey Walton:

Hi Jeffrey,

IMHO that is where the flexibility of the LRNG comes in. I am currently in discussion with the German BSI on their requirements and these requirements can be covered by a few extra lines since it only affects a different initial seeding of the DRNG.

In any case, the LRNG supports other approaches by:

- select one or more entropy sources (or provide one from external) that are considered appropriate

- if needed, adjust the initial seeding operation

- if needed, adjust the crypto primitives that are in use.

Ciao
Stephan

Ciao
Stephan

Hacks that work today are the step toward a real solution.

So please, propose them and we can evolve from that.

So you want to ship this separate driver instead? Great, but as I said elsewhere, doing a wholesale replacement is almost never the right thing to do.

Work off of those known-working-and-certified hacks. Submit them and let's go from there please.

thanks,

greg k-h

We (Oracle) are carrying such a patch at the moment. We want this patch to be a temporary workaround simply to get FIPS certification in the current kernel.

We're carrying this patch simply because the certification requirements changed and this was the quickest and easiest way to workaround today's problem. It won't fix tomorrow's problem and next time we, and others, attempt FIPS certification then we, and others, will need a different /dev/random because neither the old one nor our quick and dirty workaround will actually be acceptable.

The commit we're carrying at the moment is here: https://github.com/oracle/linux-uek/commit/5ebe83413c7573d566e581461bc95f9f139c5d4d -- you'll notice that we have a different RNG in fips mode compared to normal mode.

We really don't want to have to work out a new hack for future FIPS certifications and I'm sure no other distros want to do that either.

Personally, I'd far rather have any fips-certifiable /dev/random drivers be in mainline where everyone gets the same thing. I don't like carrying out-of-tree patches like this, it's not healthy.

jch

Now that's a much smaller and simpler and easier to understand change, compared to "rewrite the whole random number generator".

Why not work to get FIPS support merged properly upstream? I know there are many people working to get FIPS certification, and while the requirements seem to constantly change and are vague and random, it would be great to stop duplicating all of this effort all the time.

Great, why not work to solve this within what we have?

Remember, wholesale replacement is NOT how kernel development happens. It's incremental evolution based on external need. It's not a "kill the existing code and replace it from scratch" process.

Great, please work to make this happen within what we have today.

But adding a stand-alone separate random subsystem just for this is not a good idea and is one huge reason why this patch set keeps being ignored by the kernel developers.

thanks,

greg k-h

Jason,
have you previously produced a list of reasoned concerns with this patchset and direction?

This specific email is not really useful to me to understand the concerns as it does not contain actionable suggestion or critique.

I personally find the direction fine, and with my distribution hat on I can say that FIPS is essential for us and any design must include an option to be FIPS certifiable.

As NIST keeps improving their testing capabilities and rigorous cryptographic design of the CSPRNGs as well as entropy sources the kernel must also adapt.

Stephan is providing a path forward, and I haven't seen any other proposal, let alone code, that provide improvements in this area. I am pretty sure the design can be improved if there is detailed and actionable feedback on what to change.

I hope the path forward can be one of collaboration rather then mere opposition.

HTH,
Simo.

Simo Sorce
RHEL Crypto Team
Red Hat, Inc

Replacement of the existing code to cut over to the new one is not collaboration, it's the exact opposite.

Submitting patches to the existing codebase to implement the "requirements" is the proper way forward, why has that never been done.

Remember, evolution is the correct way of kernel development, not intelligent design :)

thanks,

greg k-h

Am Freitag, 26. November 2021, 16:44:17 CET schrieb Greg Kroah-Hartman:

Hi Greg,

It has been attempted by Nikolai Stange without avail - no comments were received, let alone it was integrated.

Ciao
Stephan

Links to the patches and discussion please?

thanks,

greg k-h

Am Freitag, 26. November 2021, 17:22:14 CET schrieb Greg Kroah-Hartman:

Hi Greg,

Please consider https://lkml.org/lkml/2020/9/21/157

One side note: the LRNG patch set does not replace random.c, but provides an additional implementation that can be selected at compile time. I am under the impression that is an equal approach considering other areas of the kernel like file systems, memory allocators, and similar.

Thanks
Stephan

That's a load of patches, some of them seem sane, what ever happened to them? Seems like the conversation got derailed by people with email server issues that prevented them from participating in public :(

But that patch set is a nice way to do this, incremental changes working with the existing codebase, not trying to ignore the current code and create a separate implementation.

Also, minor note, please use lore.kernel.org links, we don't have any control over lkml.org, nor can we take patches out of that site with any of our normal tools.

Sometimes, yes, it is valid to have different implementations for things that do different things in the same area (like filesystems), but for a core function of the kernel, so far the existing random maintainer has not wanted to have multiple implementations. Same goes for other parts of the kernel, it's not specific only to this one very tiny driver.

As a counterpoint, we do not allow duplicate drivers that control the same hardware types in the tree. We have tried that in the past and it was a nightmare to support and maintain and just caused massive user confusion as well. One can argue that the random driver is in this same category.

thanks,

greg k-h

Am Montag, 29. November 2021, 17:25:24 CET schrieb Greg Kroah-Hartman:

Hi Greg,

Nothing was discussed, nothing was picked up.

Apologies, will do for the next time.

Ciao
Stephan

I think an argument could be made that they are different drivers since they have different requirements and security goals. I don't think it matters where the requirements came from, whether it was ad hoc from the developer, NIST, KISA, CRYPTREC, NESSIE, or another organization.

Maybe the problem is with the name of the driver? Perhaps the current driver should be named random-linux, Stephan's driver should be named random-nist, and the driver should be wired up based on a user's selection. That should sidestep the problems associated with the "duplicate drivers" policy.

Jeff

The "problem" here is that the drivers/char/random.c file has three users, the userspace /dev/random and syscall api, the in-kernel "here's some entropy for the random core to use" api, and the in-kernel "give me some random data" api.

Odds are, you REALLY do not want the in-kernel calls to be pulling from the "random-government-crippled-specification" implementation, right?

Again, just try evolving the existing code to meet the needs that you all have, stop trying to do wholesale reimplementations. Those never succeed, and it's pretty obvious that no one wants a "plugin a random random driver" interface, right?

thanks,

greg k-h

You really *do* want that.
When our customers are mandated to use FIPS certified cryptography, they want to use it for kernel cryptography as well, and in general they want to use a certified randomness source as well.

I do not get why you call the implementation crippled? The specification is quite thorough and provides well reasoned requirements as well as self-test that insure coding mistakes won't end up returning non-random values.

I understand the mistrust vs gov agencies due to past mishaps like the Dual-DRBG thing, but we are not talking about something like that in this case. NIST is not mandating any specific algorithmic implementation, the requirement set forth allow to use a variety of different algorithms so that everyone can choose what they think is sane.

I think one of the issues is that the number of changes required against the current random driver amount essentially to a re- implementation. Sure, you can do it as a series of patches that transform the current code in something completely different.

And the main question here is, how can we get there, in any case, if the maintainer of the random device doesn't even participate in discussions, does not pick obvious bug fixes and is simply not engaging at all?

Your plan requires an active maintainer that guides these changes and interact with the people proposing them to negotiate the best outcome. But that is not happening so that road seem blocked at the moment.

HTH,
Simo.

Simo Sorce
RHEL Crypto Team
Red Hat, Inc

There are huge numbers of internal kernel calls that use random data for non-crypto things.

Which specification are you talking about exactly? There are loads of different ones it seems that people wish to follow, so it's hard to claim that they all are sane :)

That is how kernel development works, it is nothing new.

What obvious bug fixes have been dropped?

We need working patches that fit with the kernel development model first before people can start blaming maintainers :)

I see almost 300 changes accepted for this tiny random.c file over the years we have had git (17 years). I think that's a very large number of changes for a 2300 line file that is relied upon by everyone.

thanks,

greg k-h

I think the confusion comes from the use of cryptography to hide the internal state and provide non-predictable sequences, and not from the use of this source to perform cryptography elsewhere. But crypto here, when used, is not a goal but a means. We could call this a "reduction" function or a "whitening" function. Its importance solely depends on how much we want to protect the internal state from being guessed, which first comes back to how long the knowledge of this internal state is useful. If we'd mix completely independent and unpredictable sources like cosmic microwave background noise and sea-level beta radiations, these are constantly renewed, their knowledge doesn't bring anything and there's no need for crypto to protect them. That's not necessarily what we're using and we have to deal with more durable source whose disclosure could have more impact for some time frame, thus would need some protection.

As such there is probably a broad spectrum between "we must use strong cryptography on this source hence abide with authorities' decisions" and "we just need this short-lived state not to be trivially guessable till the next call". In this case do we *really* care about what crypto functions are used to hide the internal state ? I guess not really, and that could possibly be configurable at run time. After all, in practice the jitter entropy and other sources might add sufficient uncertainty to complicate analysis of even a weak algorithm and render the internal state hardly guessable.

I'm also having some concerns about this. It seems to me that it's always difficult to *simplify* what we have and that each time we try to replace something in that area we end up with multiple versions. Look at the recent prandom32 stuff for example. We got a new algo used for IP IDs, in a rush, hoping to generalize it to replace the existing Tausworthe one. I had a look a few months ago to try to finish the job... hundreds of callers that make use of the internal state for unit tests :-( Basically unfeasible without breaking lots of driver I have no idea how to test. So by trying to replace something we just ended up with two implementations (and if I remember well there were already a few more, mostly variants of the former).

A replacement ought to be an observation, a conclusion of a work well done, not a goal. If the changes manage to move everyone in the right direction and at the end everything is seamlessly replaced for good, that's awesome. But changing for changing is hard. And if we end up with build time options to decide between one solution and the other, we fragment the testability :-/

Just my two cents,
Willy

Sure, but it makes little sense to use different random implementations unless there are specific issues in terms of performance. It is also not always easy to establish if a certain use of random numbers is actually security relevant, may be context dependent, so it is generally safer to just use the certified implementation for everything if possible.

Well, given I am interested primarily in FIPS certifications I was referring specifically to SP800-90A/B/C:
https://csrc.nist.gov/publications/detail/sp/800-90a/rev-1/final
https://csrc.nist.gov/publications/detail/sp/800-90b/final
https://csrc.nist.gov/publications/detail/sp/800-90c/draft

Stephan posted you the link a few days ago for one of the examples. If you look at the last year you also will see that multiple patches have gone in w/o the maintainer interacting, which is fine for obvious stuff, but does not work for stuff that requires more feedback.

This is a Catch-22, the maintainer is mum in what would be acceptable, and whenever there are patches sent, there is no feedback on whether they are acceptable or not. It's not like I like blaming anyone, but it would be nice to have at least one word that gives a direction to follow that the maintainer is willing to then engage with and review or at least accept with proper third party review.

Seem like a lot more are desired too :-)

Simo.

Simo Sorce
RHEL Crypto Team
Red Hat, Inc

The RNDRESEEDCRNG ioctl was totally broken, and I sent out a patch to fix it which was ignored for months:
https://lore.kernel.org/linux-crypto/[email protected]/

Reminders didn't help:

First ping: https://lore.kernel.org/linux-crypto/[email protected]/
Second ping: https://lore.kernel.org/linux-crypto/[email protected]/
Third ping: https://lore.kernel.org/linux-crypto/[email protected]/
Fourth ping: https://lore.kernel.org/linux-crypto/X%[email protected]/
Resent to Andrew Morton: https://lore.kernel.org/linux-crypto/[email protected]/
Pinged Andrew: https://lore.kernel.org/linux-crypto/[email protected]/

Finally *you* took the patch: https://lore.kernel.org/linux-crypto/[email protected]/

Here's another random.c bug fix which was ignored, this one for 6 months before Herbert Xu finally took it through the crypto tree:
https://lore.kernel.org/linux-crypto/[email protected]/

Here's a dead code cleanup which was ignored for 6 months before being taken by Herbert Xu through the crypto tree:
https://lore.kernel.org/linux-crypto/[email protected]/

Here's a patch to random.c which was taken by the arm64 maintainers due to being ignored by the random.c maintainer:
https://lore.kernel.org/lkml/[email protected]/

So unfortunately, as far as I can tell, Ted is not maintaining random.c anymore.

- Eric

I am happy to step up here. Feel free to CC me on random.c fixes and I'll review them promptly.

Jason

Jason,
are you also volunteering to review the patches needed to reach compliance with the NIST documents I mentioned in the thread?

Simo.

Simo Sorce
RHEL Crypto Team
Red Hat, Inc

Hi Simo,

I think various folks have said this during the various discussions on this topic over the years, in addition to myself, but I suppose I'll reiterate my general views on FIPS in this context.

FIPS is about compliance and certification. From a cryptographic point of view, there might be some good ideas, some dated ideas, some superfluous but harmless ideas, and so forth. But the reason that you want it for your customers is because you think your product will become more valuable or useful to customers if it checks that green compliance checkbox. I don't think we disagree about this being the motivation.

Now typically the kernel interoperates with lots of things and implements many different specifications. It supports scores of network protocols, IPsec cipher suites, USB quirks, SCSI hacks, you name it. The implementation of these drivers is always up to the author and hopefully kernel developers at large do the best job they can with the implementation, but the hardware or protocol they're interfacing with is not up to the author, by virtue of it being external to the kernel. It's not like instantiating IPsec with single DES and MD4, or SM3 and SM4, etc. is so great, and it's not like the compendium of brilliant hacks in drivers/usb/host/pci-quirks.c is so great either. But these things all exist to talk to something *outside* of the kernel, and so we grit our teeth, and as I said, do the best we can to implement it well.

But the RNG isn't like that. In fact, the RNG is logically *required* to be not anything like that: it returns random bytes, and they must not have any distinguishing quality with other random bytes; otherwise we have a serious problem that needs fixing. And so, we carry things out according to the usual kernel developer mindset: we implement it as best as we can, using the best algorithms we can find, in a way most suitable for the kernel.

Then FIPS comes along and starts dictating things about *how* we implement it, and those things it dictates might not be exactly the same as what we would would be doing when doing best that we can, using the best algorithms we can find, and in the most suitable way for the kernel. And so it would seem that the goal of implementing the RNG as best as we can might potentially be at odds with the goal of getting that green compliance checkbox, because that checkbox oversteps its bounds a bit.

That's not to say, of course, that we shouldn't accept input on how we implement our algorithms from elsewhere. On the contrary, I think random.c has a *lot* to gain from incorporating newer ideas, and that the formalism and guidance from academic cryptographers is less "academic" than it once was and much more real world, implementable, and suitable for our uses. But, again, incorporating new ideas and accepting input on how to improve our code is very much not the same thing as following the FIPS laundry list for that green compliance checkbox. Maybe some parts do overlap -- and I'd love patches that improve the code alongside compelling cryptographic arguments -- but, again, we're talking about compliance here, and not a more welcome, "hey check out this document I found with a bunch of great ideas we should implement."

I would like the kernel to have an excellent CSPRNG, from a cryptographic point of view, from a performance point of view, from an API point of view. I think these motivations are consistent with how the kernel is generally developed. And I think front loading the motivations with an external compliance goal greatly deviates and even detracts from the way the kernel is generally developed.

Now the above is somewhat negative on FIPS, but the question can still be
posed: does FIPS have a path forward in the RNG in the kernel? It's obviously not a resounding "yes", but I don't think it's a totally certain "no" either. It might be possible to find some wiggle room. I'm not saying that it is certainly possible to do that, but it might be.

Specifically, I think that if you change your perspective from, "how can we change the algorithms of the RNG to be FIPS" to "how can we bend FIPS within its limits so that having what customers want would minimally impact the quality of the RNG implementation or introduce undue maintenance burdens." This means: not refactoring the RNG into some large abstraction layer that's pluggable and supports multiple different implementations, not rewriting the world in a massive patchset, not adding clutter. Instead, perhaps there's a very, very minimal set of things that can be done that would be considerably less controversial. That will probably require from you and other FIPS enthusiasts some study and discussion at what the truly most minimal set of things required are to get you that green compliance checkbox. And hey -- maybe it's still way too much and it doesn't work out here. But maybe it's not that much, or, as Greg suggested, maybe it winds up that your needs are actually satisfied just fine by something in userspace or userspace-adjacent.

So I don't know whether the FIPS has a path forward here, but if it does, I think the above is the general shape it would take. And in the mean time, I'm of course open to reviewing patches that improve the RNG in a cryptographic or algorithmic sense, rather than a purely compliance one.

Hopefully that helps you understand more about where we're coming from.

Regards,
Jason

Hi Jason,
thanks for your reply, I appreciate when there is a clear exchange of ideas.

Comment inline.

I have to say that although there is clearly a great deal of "because we need the certification" I do not fully agree that FIPS is just a checkbox to be ticked for me. Of course for customers that do not care that much it is, and it is a required one. However having worked a lot on this I can tell you there is actually real cryptographic value in the requirements FIPS introduced over the years. If anything my complaint is that the list of accepted constructs is restrictive, but other than that most of the requirements have real world sense, and the certification process do uncover issue that otherwise would linger as the testing is rather thorough.

Well I think most of the requirements are sane practices, hopefully controversial stuff will be minimal. I fully believe we can work to have the best we can as well as having it FIPS compliant, because the intent of FIPS requirements here is exactly to have the best guarantees for randomness.

I happen to think quite a few of the requirements are actually good ideas to implement to improve the guarantees of randomness, but there may definitely be contentious ideas of what is "good" and what is an "arbitrary request".

I would agree is compliance meant arbitrary/capricious requirements. Hopefully most of the requirements are reasonable and we can find a reasonable way to fulfill them.

We always operate with this mindset to be quite frank. The kernel is just one of many crypto modules we certify, and we always try to find the least invasive options in all the crypto modules we certify. We also normally try to get all changes upstream because we think they are a benefit to everyone.

I think the reason to propose this is to deal with cases where the kernel community and the FIPS requirement diverge. A pluggable system allows to provide a downstream module and in general will provide clear entry-points where to apply downstream patches that minimally deviate from the general structure.

Unfortunately, regardless of what the kernel community find of its liking we have a business need to provide FIPS certifications to our customers. So for us it is also a matter of pragmatically reducing to the maximum extent possible any necessary deviation from upstream kernels.

As long as there is actual feedback and a willingness to reach a compromise on both sides when a change does not materially cause issues, I think this is certainly reasonable.

Unfortunately userspace is not an option for kernel's own cryptography.

Hopefully we can take both into account.

It does,
thanks.

Simo.

Simo Sorce
RHEL Crypto Team
Red Hat, Inc

Hi Jason, Greg,

a lot of the issues LRNG address are related to RNG and FIPS on embedded/IoT devices.

The problem we have is that /dev/random as it stands today in many cases does not generate enough entropy to support cryptography on embedded/IoT devices. Embedded devices in most cases have limited interrupt and IO activity, they do have in many cases aggressive power management where device is up and running few seconds at a time and fallbacks into suspend mode, this is done to preserve power (battery and otherwise), and now such operation even the legal mandate in EU (we are going green).

What options do we have here:

Use hardware random number if CPU supports it. Yes, some people do not trust it, but it's better than nothing. /dev/random currently does not allow to mix in Hardware RNG unless quality parameter is set, and none of the kernel Hardware RNG have it set out of the box.

Not all CPUs have hardware RNG to use or have non-compliant Hardware RNG (which is after 90C was adopted most of the older ones, 90C requires runtime test on raw entropy which is not exposed outside of the IC), what to do now? This is one of the areas where Jitter RNG comes in. It has fast entropy collection, meets FIPS requirements and could be run on any CPU, provided it has High Resolution Timer, does not require storing seed on the file system that is prohibited by FIPS. There is no option as of today to mix in or flood Jitter entropy into /dev/random inside kernel.

I am aware that there are userspace daemons that take entropy from Hardware RNG or Jitter and feed into /dev/random, but is it really the best approach? Now let get into FIPS on such systems.

I hoped I explained earlier why existing /dev/random is unusable.
If userspace solution to /dev/random is used, one has to demonstrate that entropy fed by userspace daemon floods /dev/random to the point where other sources of entropy statistically does not matter. That increases cost of FIPS certification by about 30% last time we checked.

This is why it would help a lot if one can choose from kernel configuration which RNG is appropriate for the system at hand, and this exactly what LRNG does.

Thank you,
Boris
THIS MESSAGE, ANY ATTACHMENT(S), AND THE INFORMATION CONTAINED HEREIN MAY BE PROPRIETARY TO LAIRD CONNECTIVITY, INC. AND/OR ANOTHER PARTY, AND MAY FURTHER BE INTENDED TO BE KEPT CONFIDENTIAL. IF YOU ARE NOT THE INTENDED RECIPIENT, PLEASE DELETE THE EMAIL AND ANY ATTACHMENTS, AND IMMEDIATELY NOTIFY THE SENDER BY RETURN EMAIL. THIS MESSAGE AND ITS CONTENTS ARE THE PROPERTY OF LAIRD CONNECTIVITY, INC. AND MAY NOT BE REPRODUCED OR USED WITHOUT THE EXPRESS WRITTEN CONSENT OF LAIRD CONNECTIVITY, INC.

Now deleted.

If you think there are good ways to improve the RNG, of course send patches for this, justifying why, taking into account recent research into the topic you wish to patch, etc. Don't write, "because FIPS"; instead argue rationale for each patch. And if you _do_ feel the need to appeal to authority, perhaps links to the various eprint papers you consulted would be worthwhile. Preferably you're able to do this in a small, incremental way, with small standalone patchsets, instead of gigantic series.

I may be parsing things incorrectly, but you seem to be rejecting the NIST requirements, and then positioning your personal opinion as superior. It sounds like one authority is being replaced by another. Perhaps I am missing something.

I am also guessing you've never read the relevant NIST documents. The documents state the security goals and provide the steps to achieve them in an implementation.

Jeff

Ok, I think this thread has gone on long enough without any real patches.

Please, if you want to support NIST, or any other type of thing, submit patches that implement what you think will help achieve this. Absent of that, we have no idea what NIST or any other random document aims to require or wish.

thanks,

greg k-h

Part of the problem here is that NIST (and the concomitant fips certification) is a moving target. A couple of years ago, we were fine. Today's requirements are different, tomorrow's will be different again. Today's requirements being different are what resulted in the small patch I mentioned earlier.

You suggested, Greg, that I submit that and see what happens. I can take a hint :) so I'm working on that as a possible way forward to decouple things a bit without too much churn.

jch

I'm actually sort of curious to learn which specific uses of get_random_bytes you're concerned about. ECC keygen? What else?

Now deleted.

Hi, Jason. How do you think we could approach that then?

Are you willing to discuss the FIPS 140-3 requirements that random.c doesn't currently meet so we can dive deeper on how we could implement them in a way that would improve the kernel other then simply providing compliance to FIPS?

I believe that several requirements would be beneficial to random.c (ie, health test, oversampling, entropy data collection). But so far we lack proper direction on how to proceed and it would be better for us to have a clear notion of what could be accepted before putting more effort on yet another patch set.

I believe all the distros are interested in making progress on that, but without a general guidance it makes very hard for us to collaborate and we end up in the current situation in which each distro is carrying its own "hack", as Simo mentioned before. Canonical is in the same situation as the other distros and we are carrying an workaround to wire up the crypto DRBG to random.c in order to archive compliance.

We could also concentrate all the discussion in the linux-crypto mailing list to facilitate this process, since right now I believe the MAINTAINERS file doesn't have a specific mailing list associate to random.c

Regards,
Marcelo

Discussing things doesn't usually work well. Let's see some working patches first, that solve problems that you have with the current random code, and we can go from there.

Again, like any other kernel patch submission, nothing new here at all.

If everyone seems to think their patches are hacks, and are not worthy of being submitted, then why do they think that somehow they are viable for their users that are actually using them?

{sigh}

greg k-h

Hi, Greg. I understand your point but we had plenty of patch submissions already from Stephan, Nicolai and others and that didn't work. So I am expecting that anybody taking over as the random.c maintainer can at least provide some direction on that.

Because although some people dislike it, FIPS is still a requirement for many users. That's the reality and that will not change just because there are some resistance against it.

The patches that distros are carrying are hacks because they try to minimize risks while keeping the code as close as possible to upstream. But that has several drawbacks, such as performance, limited entropy sources an so on, that to me makes them not suitable for upstream.

Regards,
Marcelo

Then submit patches to be reviewed! This patch series was commented on why it is not acceptable, so it's done with for now.

We can't go back in time and dig up old patch series to be reviewed now unless they are actually refreshed and resubmitted.

Why isn't anyone doing that?

In other words, "the hacks we made to the random code are so bad we do not want to submit them upstream for everyone to review as our names would be on them and we would have to justify them to the world"? :)

Given that there are no patches here to review by anyone, why is this email thread still persisting?

Again, the only way forward is to submit changes that meet our well-documented development process. There's nothing "special" about this very tiny .c file that is any different than the other 30 million lines of kernel code we support that warrants a different process at all.

greg k-h

I think people would at least like to know they are not spending a bunch of time and work to have another patch series go into the void, or be rejected again, *after* all the hard work is done, without a foreword of what is acceptable.

Our patches are all public in our respective tress, with names and all. The hacks are not necessarily *bad*, but they are changes made because we could not put in what we think would be a better solution. They can definitely be sent upstream.

There is a will and a need to "improve" things, but given past absence of feedback, people are trying to understand if there is any point in trying to submit patches. Patches are work, and people like to know they are not wasting their time completely before committing many more hours.

This very thread shows that there is an issue, people are not asking for exceptions to the process, they are only asking for direction from the maintainer so they can work productively and get some result, that is all the "special" there is here.

Simo.

Simo Sorce
RHEL Crypto Team
Red Hat, Inc

It is obviously natural to think this way, but you can also understand that reviewing patches is extremely time consuming. And it's extremely difficult to review a patch series which says "replace all that infrastructure with a new one", especially when the motivations are "comply with this or that standard" without the benefits being obvious at all for those having to review those patches. And keep in mind that those who you expect to review the code will have to maintain it, so if the benefit is not obvious, why would they take the risk of breaking something that's been working well enough or that has been easy enough to improve or fix over time ?

My feeling from the beginning is that nobody felt brave enough to go through these series because of this.

The normal way to propose changes is to say "some of our customers ask for FIPS, we've looked at *what is missing* to accomplish that, first it suggests/requires/mandates properties X, Y and Z which are currently not supported, so these patches improve the current code by adding such properties". And you don't patch "for FIPS", you patch to make the existing code evolve to support such missing properties or features, till the point you figure that nothing is missing anymore, and you can tell your customers "now we comply with FIPS". And if it takes several versions to reach that point, no problem, because each version continues to work like before, possibly better, possibly not.

It's not different from supporting a new hardware. You don't bring in a big patch series implementing all of the machine's device drivers in an isolated area specific to that device. Instead you bring the various parts this machine relies on (serial, pcie, usb, network etc), possibly by improving existing drivers that are already very close or share some common parts, and at the end you figure you have everything you need and then you can proudly say "now we fully support this device".

This way of proceeding incrementally allows submitters not to waste time coding for nothing, and those reviewing changes to make sure they're not breaking everything, or to ask for some changes to stay safe.

But this does mean that a list of incremental changes/additions has to be established on the submitter's side, not a list of replacements. Sometimes it is required to replace a part, but the justification has to be technical, not "this part doesn't meet standard X or Y, let's reinvent it". And such replacements need to be minimal so that it's obvious they continue to provide exactly the same services and it's almost impossible that a bisect lands on such a patch when something stops working (i.e. if it happens it's just a coding bug and not a design mistake).

At least it's visible in this very thread's subject that it's addressed in a special way: "/dev/random - a new approach", i.e. "trash all what we have and restart from scratch". This is exactly what is causing the problem from the beginning in my opinion. But at this point I think that Jason, Greg and others have already been saying it, so I'll stop.

Hoping this helps,

Willy

Am Samstag, 11. Dezember 2021, 08:06:10 CET schrieb Willy Tarreau:

Hi Willy,

I am so surprised by such statements. Patch 00/15 lists in a bullet list the significant benefits of the LRNG. But seemingly nobody reads the introduction with its concise bullet list or the documentation. The FIPS bits are a tiny aspect of the whole effort (which even can be completely compiled out based on config options), the more significant aspects that have nothing to do with FIPS and benefit all are testability, performance, use of contemporary cryptography, and flexibility.

Before I started the endeavor of the stand-alone patch of the LRNG, I developed cleanup patches to random.c in 2014 and 2015. I got massively discouraged to continue working on random.c as I did not get feedback from the maintainer. Some patches were taken, some were not without a comment...

Ciao
Stephan

Hi Stephan,

But this is where the problem is. You're not proposing to improve the current one but to replace it. Who has enough energy to review some new code that claims to be compatible with older one ? It requires to perform a mental "diff" which is extremely complicated. There are possibly corner cases in the current code that nobody knows about and that some code currently relies on. Who wlil detect that you're not going to break them with a fresh new implementation ?

Incremental changes allow to focus on the changes. You don't need to know how everything else works, just that the modifications do not break the part they are inserted into. This makes a huge difference, and this is why everyone constantly insists on seeing small incremental changes. Sometimes you'll notice that you can even see review from different people for very close parts in the same file.

We all know that this is extremely irritating. It happens everywhere and in every project. Sometimes lack of time, lost messages, flipped priorities, or lack of interest, or a combination of all of this. I do it myself from time to time by accident and I really feel bad when this happens. That's not much different than when you're reminding a coworker that you need their help and they forget because of other priorities. And this must never discourage one from pinging again and asking why there's no response. But one thing is certain to me, it's that if a maintainer, for any reason, doesn't respond to tiny patches to their code, there's hardly any chance to see a response to a whole replacement.

Here Jason offered to invest time reviewing changes. If you have changes to propose, why not try ? And even if it takes one year to get everything done, who cares ? You seem to have been working on this for 7 years already, it might be worth trying another approach.

Regards,
Willy

Hoping that might help with the discussion and to explain why I do consider those solutions a "hack", that's the patch we've been using so far to achieve SP 800-90B compliance:

https://kernel.ubuntu.com/~mhcerri/0001-UBUNTU-SAUCE-random-Use-Crypto-API-DRBG-for-urandom-.patch

Regards,
Marcelo

Hi Marcelo,

Thanks for sending this in response to my request for it in our private thread.

Just to confirm, this little patch here gives you FIPS certification?

Jason

There might be some FIPS certification labs that might be willing to be taken in by the jitterentropy story, but when I've had private communications from people who are familiar with the Intel microarchitecture saying that jitterentropy is mostly "security by obscurity", I'd be strongly opposed to replacing the current scheme with something which is purely jitteretropy.

Perhaps an build-time option where one of the seeds into the CRNG is "jitterentropy", but we keep everything else. That way, jitterentropy can still be TSA-style "security theatre", but we're not utterly dependant on the "the CPU microarchitecture is SOOOOOOO complicated, it *must* be unpredictable".

- Ted

Hi Ted,

Yea, I'm not really compelled by it as something real that we'd actually want to have for something serious. Keep in mind: this thread isn't really about cryptography, but just about compliance nonsense. BUT, if it turns out that the path to these people getting their green compliance checkbox stamp isn't actually thousands of lines of new code, but rather some glue bridging the /dev/urandom / getrandom(2) API into the blah cryptoapi thing, that's... interesting news to me. I'm not even saying, at this stage anyhow, that I want to do this, but I do find it a very interesting data point. As I wrote in [1]:

We're now starting to get some idea about how this FIPS stuff bends.

Jason

[1] https://lore.kernel.org/lkml/CAHmME9qP9eYfPH+8eRvpx_tW8iAtDc-byVMvh4tFL_cABdsiOA@mail.gmail.com/

The last time I had the displeasure of looking into the FIPS certification, which granted, was over a decade ago when I was in IBM's Linux Technology Center, what I learned was it all depends on the FIPS certification lab. NIST writes the documentation, but what really matters is the FIPS certification lab that a hardware or software vendor pays $$$$ to in order to get the magic certificate which allows you to sell into *some* government contracts. (When I had to go through the all of the nonsense to get a TS/SCI clearance to support the real-time kernel for all of the IBM servers for the DDG/1000 Zumwalt Class destroyer, they didn't care about getting FIPS certified. I've also seen tighter security measures for computer rooms at NYC financial companies than at a Top Secret machine root at said defense contractor. Go figure....)

The other thing I learned for those customers who *did* care, was that the only thing that got certified was a specific binary image. If you replace the kernel or OpenSSL library with, say, a bugfixed version that fixed an actively exploited zero day, *boom*, that would break the certification and the system would no longer be FIPS certified.

Some FIPS labs would allow you to certify the "cryptographic core" of the OpenSSL library, which the OpenSSL library would then dlopen, and so as long as the bugfix was in, say, the ASN.1 parser, and you didn't need to change the "cryptographic core" it was OK --- and you just needed to hope that there weren't any bugs in the cryptographic core, since then you wouldn't be allowed to fix it --- since FIPS compliance was more important than, say, the *actual* security of the system in question.

So yeah, as I said, it's all about TSA-style security theatre, and when I worked for IBM and there was millions of dollars on the line, I might have cared. For upstream development, (and blessedly, this is not something that my current employer has needed to worry about) I care far less about it.

If we want to add a CONFIG_RANDOM_SECURITY_THEATRE build option which diverts getrandom and /dev/urandom to use crypto/drbg, I'm going to think it's a waste of time, and there are some things about crypto/drbg that I'm not psyched about such as the fact that only reseed after 2**20 calls to drbg_generate(), and the drbg statemachine will initialize itself from get_random_bytes() in early boot, when the CRNG is least likely to be securely initialized. So **I** wouldn't want to use it for my own personal security, but if it allows Ubuntu to sell into the US govnerment market, my only hope is that this wouldn't be inflicted on all of their customers, but only those US Government customers who care (and as near as I can tell, this is *not* all USG customers).

Well, if we optionally (if jitterentropy_rng is compiled in), we would periodically pull from it as one additional entropy source into the input_pool, it won't do any harm --- other than the CPU overhead consumed by jitterentropy, of course. Maybe that would make some people happy, including some FIPS Labs?

I've also seen some FIPS certifications which didn't care about what the kernel did, but only cared about what was in the OpenSSL library. (Which is where the story about segregating out the cryptographic core so that you could actually patch most zero-days without having to go back to the FIPS certification lab, pay $$$, and wait months for the updated binary to be certified.)

So I suspect that there will be a lot of anecdotal evidence, but the only thing we can probably say with any amount of certainity is Your Mileage May Vary.

Cheers,

- Ted

So just a few thoughts:

Ubuntu, Red Hat, and Oracle all have patches which do this. They differ slightly; e.g., Ubuntu's patch only changes /dev/urandom while the others change /dev/random and getrandom() too. But the idea is the same: the userspace interfaces to the RNG are changed to get output from a SP800-90A DRBG (crypto/drbg.c) rather than the Linux RNG directly. The SP800-90A DRBG in turn is seeded from from two entropy sources combined: the Linux RNG (get_random_bytes()) and jitterentropy (crypto/jitterentropy.c).

My understanding (and I could be totally wrong -- I am still trying to reverse engineer all the requirements for this certification stuff) is that the reason that these distros need this is they are certifying the whole kernel image as a FIPS cryptographic module, and that implies that cryptographic random numbers must conform to the SP800-90{A-C} documents. The problem is that ChaCha20 isn't considered an approved DRBG algorithm, nor do Linux's entropy sources have SP800-90B continuous health-tests. Therefore, get_random_bytes() is considered to provide no entropy. crypto/drbg.c works around this by using an approved DRBG algorithm and by using jitterentropy which has SP800-90B tests.

I think the reason people are considering this to be a hack is because on paper it ignores Linux's main RNG. It's still *used* as an extra entropy input, but on paper it's credited with no entropy. That seems a bit odd.

However, even Stephan's patchset has the same issues, IIUC. Stephan's patchset still keeps get_random_bytes() using ChaCha20, and it provides an option to layer crypto/drbg.c on top of it for userspace output. So I'm not sure how much of a hack it really is, if the supposed non-hack is basically the same.

Now, the idea of certifying the whole kernel as a FIPS cryptographic module is stupid, given that it prevents the kernel from being updated to fix security vulnerabilities. However, I've been told that essentially the same RNG issues also arise for NIAP certification of mobile devices
(https://www.niap-ccevs.org/MMO/PP/PP_MDF_V3.2.pdf), which looks at entropy system-wide. NIAP similarly doesn't consider ChaCha20 to be an allowed DRBG algorithm, so they consider the entropy to be constantly depleting, and it "runs out". (There have been devices that passed NIAP despite this, but I've been told that this was an oversight.) Wiring up /dev/{u,}random and getrandom() to crypto/drbg.c would avoid this issue too.

So again, I could be totally wrong, as I am trying to reverse engineer the requirements here --- but to me it seems that a small patch to provide an option to use crypto/drbg.c could solve both the FIPS and NIAP certification problems.

If Stephan could elaborate on what his patchset does that is better (as far as certification is concerned, at least -- I know his patchset has some other advantages such as eliminating non-cryptographic entropy processing), that would be helpful to illuminate anything I may be missing.

- Eric

Alright, so if that's the case, then what you ostensibly want is:
a) Some cryptoapi users to use crypto_rng_get_bytes, as they already do now. (In a private thread with Simo, I pointed out a missing place and encouraged him to send a patch for that but none has arrived.)
b) Userspace to use some other RNG.

(a) is basically already done.

(b) can be accomplished in userspace by just (i) disabling getrandom() (making it return ENOSYS), and then (ii) replacing the /dev/urandom path with a CUSE device or similar.

I suppose (b.i) might be able to be done with some bpf seccomp cgroup situation. Or, if that's problematic, somebody could propose a "disable getrandom(2)" cmdline option. That doesn't seem very hard. And (b.ii) could use combined inputs from /dev/urandom and whatever FIPSy userspace jitter entropy daemon you have.

In order to prevent the actual security from regressing on this, all you have to do is ensure that you're always using at least 32 bytes from the kernel's real /dev/urandom, and then whatever you add on top of that becomes just for the certification aspect. As your various green compliance checkboxes change over time and per region, you can just swap out the extra-paper-pushing-bytes-on-top with whatever the particular requirements of a certification body are. And you get to do this all in userspace.

Marcelo/Simo - could you tell me what you find deficient about that plan? It strikes me that this would give you maximum flexibility and pretty much accomplish the goals?

Thanks,
Jason

Not that it is not the whole kernel, but a "module boundary" is drawn around the crypto API and vicinity.
It would be really nice if this whole "boundary" could be built as a single binary module to be loaded in the kernel in fips mode. That way we could update the rest of the kernel w/o rebuilding the module, but we are not there.

Rebuilding the kernel does technically invalidate certification however NIST themselves tells people to care first about the security of the systems as long as the vendor is undergoing or promising certification of the patched kernel.

There is an assumption of good faith.

I noted your point, just haven' had time to act on it.

While this is technically possible it is not very helpful, as it requires downstream patching of userspace programs, most of which do not have either runtime nor compile time switches to change the used random device.

It is simply easier to just patch /dev/[u]random/getrandom() to use a certified DRBG in FIPS mode, although we also considered all the options you mentioned we couldn't really find a good reason to add more work, and make a more complicated solution when it is simple to wire up the correct DRBG to the random device userspace applications use and is the de facto standard API for obtaining good random numbers.

You can do the whole jitterbug in userspace, but that is simply not efficient and too disruptive (the above patching of all downstream usage).

My goal is to deviate as little as possible both in kernel and user- space from what upstreams do. Creating new interfaces is easy, making people use them is almost impossible. Witness the process in getting people to use getrandom()

Let me also add that NIST requirements are not capricious, they are written by people that study entropy sources and random generation as their job and know what they are doing, I err on the side of giving them credit. The requirements set by the various 90A/90B/90C documents are about raising the bar, to guarantee that random number generators are actually "certifiably" good. There are entropy assessment performed by the labs as part of the certification process to insure the random source is a good source and does produce output that passes randomness tests. I personally think the kernel would benefit from implementing those "checkboxes", it is basically like implementing a sane CI/CD and testing environment.

To answer to Ted,
every certification program necessarily requires a certain amount of bureaucracy, especially when governments are involved, but that doesn't mean that it's all security theater.

The FIPS certification process has changed over the years as well not just the requirements. Until a few years ago the requirement to use FIPS certified cryptography could be waived, and because very few consumer programs were certified a lot of agencies considered it just a burden and didn't care much. That has changed, it is now required as a matter of law for most government agencies, and the waiver process has been discontinued. So we really need to provide FIPS certification to our public sector customers, moreover various other security standards now reference FIPS standards, so it is extending beyond government agencies and their contractors.

FIPS is painful for us undergoing certification, but as a program it also does have positive effects. We scrutinize all cryptographic modules a lot more than we used to, we have a lot more testing than we used to and a lot more confidence in the solidity of the provided cryptography in the Linux world also thanks to this scrutiny. I wish the certification process was less painful for sure, but I believe it does add value when done sensibly.

Simo.

Simo Sorce
RHEL Crypto Team
Red Hat, Inc

FWIW, the "FIPS module as a loadable kernel module" approach was implemented in the Android kernel; grep for "fips140" in branch "android13-5.10" of
https://android.googlesource.com/kernel/common. It's a lot of work for nothing IMO, but the FIPS certification lab being used is happy with the approach. Note that random.c is outside of the FIPS module with this approach.

- Eric

I don't think you even need to do this. In general, you need FIPS certification for some specific use cases / application. For example, if you're going for PCI compliance, then you might only need FIPS compliance for your OpenSSL library. What the FIPS certification lab might consider acceptable for its entropy for its DRBG is an interesting question. For some, simply having the OpenSSL library use RDSEED or RDRAND might be sufficient. Or it could talk to an actual physical RNG device.

So disabling getrandom() is probably not necessary, just so long as you can demonstrate that the FIPS cryptographic module --- i.e., the OpenSSL library --- is getting its entropy from an acceptable source.

I suspect what's actually going on is that some enterprise customers have FIPS complaince on a check-off list, and they aren't actually getting a formal FIPS certification. Or they only need something to wave under the noses of their PCI certification company, and so the question is what makes them happy.

Going into the details of whether ChaCha20 is blessed by FIPS is probably more into technical weeds than most of the people who *say* they want FIPS certification actually will go. After all, the in-kernel DRBG is using as its "entropy source" the timing instructions from a bunch of x86 assembly instructions which is **soooo** complicated that people are willing to drink from the snake oil and claim that it is secure. Is it really? Has FIPS said that it's OK? Not any more than they've said anything about ChaCha20!

And this is why some FIPS certification have gotten by just *fine* with a pure userspace OpenSSL library as their FIPS cryptographic module. Where you draw the line between a "blessed" entropy source and one that's just hand-waving is really at the discretion of the certification lab.

Personally, if I was doing something that I really, *really* wanted to be secure, I'd be mixing in several hardware RNG's. Given that most server and client platforms have a TPM, or some other hardened security module, using that is probably the best bet of I was architecting some that *really* needed to be secure. But of course, we're not talking about real security in this thread; we're talking about whatever security theater will make the FIPS certification labs, and the people who say they want FIPS on their check-off list, happy. :-)

- Ted

I don't know exactly what these people think they want, but what you say seems probably correct.

Right.

Hah, probably correct.

So, seen this way, and combined with the solution provided at [1] (or similar) for people who think they need something there, it seems like the FIPS people can likely get what they need without really needing to involve the kernel anyway.

Jason

[1] https://lore.kernel.org/lkml/[email protected]/

Hmm, cute, but I think we can do a bit better. After all, this hack involves trusting a whole lot of code that is *not* intended for secrets to avoid having side channels.

So let’s solve it for real. Have a driver (in a module) that exposes a /dev/urandom compatible interface to the CryptoAPI DRBG. We can do a really nice job of it, and maybe it’ll be 100 lines of code. People can do whatever they like with it in their container manager or boot scripts. And if it has a problem (where it’s *less* secure than the real urandom), we can say “I told you so”.

We can go one step farther: add an LSM hook to getrandom(). Then someone can hack up a fips_t policy for SELinux that turns off getrandom.

These are both dangerous. The first means creating a new device node which effectively is /dev/drbg-random which could be bind mounted or mknod'ed to be /dev/urandom. But if the user boots a kernel that doesn't support this new device node, it will mean opening /dev/urandom will get ENODEV.

Similarly, getrandom(2) never fails. By allowing a SELinux policy to force it to fail with ENOSYS, or some other error, it means exposing userspace code to a failure path that may not be as well tested. Sure, *sane* code might fall back to opening /dev/urandom; but the whole point of getrandom(2) was that it was a dumb, stupid interface interface that could be safely used by application programmers. Not paranoid OS crypto engineers that carefully check the error returns of all system calls, with appropriate fallbacks and making sure that code always "fails safe".

Right now, the enterprise distros are doing their own thing, and quite frankly, I don't see a problem with that. If it turns out DRBG is less secure (and there are some things that fill me with disquiet), then let them take the economic consequences, since they are the ones who are doing this for the economic advantages of trying to claim FIPS compliance.

If we must support this in the upstream kernel, then configure it via CONFIG_RANDOM_SECURITY_THEATRE which redirects getrandom(2) and /dev/[u]random to DRBG. I'd prefer that it be possible for someone to put "random_security_theatre=0" on the boot command line which would disable redirecting the interfaces to DRBG so if it turns out that DRBG *is* less secure, we can give advice on how to turn it off without requiring a patched kernel. :-)

- Ted

In this case, why not do it the other way around ? Instead of having yet-another config option, just indicate that fips-like randoms are enabled at boot via "random_security_theatre=1". Distros have their solution which can even be documented for their customers and that's done. Nobody uses it by default, the name is discouraging enough, but for those who know they want it, it's easy to turn it on, and at the same time it delivers them the reminder about what all this really is.

Willy

The goal is to identify a solution that avoids the enterprise kernels needing to do their own thing. They're in a position to globally LD_PRELOAD something to thunk getrandom() to improve compatibility if they want to, and they're also able to define the expected level of breakage if you enable FIPS mode. An approach that allows a single kernel to provide different policies in different contexts (eg, different namespaces could have different device nodes providing /dev/random) makes it easier to configure that based on customer requirements.

The majority of enterprise customers don't need FIPS compliance, so all that would happen in that case is that the vendors would flip the sense of that config option and the docs for enterprise distros and mainline would be out of sync. I understand that this is a situation where a niche case is making life miserable for everyone else, and I understand that this is a hole that the enterprise world has dug for itself, but where there are people expressing a real tangible use case that exists for reasons outside their control, it really feels like we should try to find a solution that works for everyone.

(resending without HTML this time, sorry for a possible duplicate) вт, 11 янв. 2022 г. в 09:13, Matthew Garrett <[email protected]>:

LD_PRELOAD is not a solution because of containers (that need to be modified to make use of the preloadable library) and statically-linked binaries.

Alexander E. Patrakov

No, it doesn't solve all problems, but the question is whether it needs to. We're talking about the scenario where:

a) a customer requires FIPS compliance, and
b) the customer has an app that calls getrandom() and doesn't fallback, and
c) they're doing so with statically linked binaries or container infrastructure that doesn't allow injection of other libraries

How common is this? Does the kernel need to solve this scenario?

Hi Ted,

I agree with you. I think enterprise distros ought to keep doing their own thing here, and there's a clear solution that does this in userspace, and also a pretty non-invasive patch from Marcelo to patch the crap into the kernel need be.

I spent some time reading about FIPS certification, compliance, and the requirements of various customers. One thing in particular leapt out at me, which I think you've been saying over and over in this thread but I didn't fully understand until this morning:

The goal is generally to have particular pieces of software or particular solutions FIPS certified. And to do this, they start from the top of the stack and move onward down. Most OSS software out there today isn't really FIPS ready and oftentimes a full solution needs modifications in one place or another. Other times, it's enough to plug in the right userspace crypto libraries. And I noticed in looking at things that are FIPS certified that random number generation tends to go through a userspace abstraction layer. And, it looks like these abstraction layers all have FIPS-able RNG hooks. You mentioned OpenSSL earlier, and it looks like even libgcrypt and wolfSSL have an abstraction layer for this.

In other words, it's not even so clear that people who need FIPS compliance really need /dev/urandom and such to be FIPS compliant as part of that. And the ones who think they do for whatever security theater nonsense can happily load up that CUSE thing I made, apply a deliberately-downstream patch, or whatever other clever solution.

So indeed it really doesn't seem like this is something the kernel needs to be doing.

Jason

I know this thread is about security theatre, not real security, but there's an even more important reason why the FIPS cryptographic module should be as high in the stack as possible (e.g., in userspace). Let's consider as, Albert Einstein would put it, the following gedanken experiment:

Let's presume that in 2008, there was a FIPS-140 certified OS designating the Linux kernel as the "cryptographic module", and so /dev/urandom was hacked to be "FIPS certified". Huzzah! Now let's assume that OS was using Ubuntu, which, being derived from Debian, was subject to a distribution "value add" where in blind obedience to a valgrind warning, there was a distro-level change which resulted in OpenSSL on Debian and Debian derivitives generating extremely predictable keys[1]. This caused fairly massive security problems for any use of OpenSSL, including ssh, certificate generation, etc. --- despite the FIPS 140 certification of the OS. Oops!

[1] https://en.wikinews.org/wiki/Predictable_random_number_generator_discovered_in_the_Debian_version_of_OpenSSL

It might be *cheaper* to claim that your OS is FIPS 140 certified by hacking /dev/urandom. Otherwise, you might have to have a responsible security engineer audit the various userspace cryptographic libraries, and that would be way more expensive. It's much easier for a product manager to say, "my work here is done" after applying a patch to the Linux kernel for /dev/urandom, and not bothering to get an engineer to certify the rest of the cryptographic stack.

And, if enterprise customers just care that an enterprise distro can claim "FIPS 140 compliance", and they can push that claim of FIPS compliance to the PCI certification authorities, they're happy. So ultimately, this is really an economic requirement, not a security requirement. And given that enterprise distros are the ones getting paid $$$ in order to claim FIPS 140 compliance, then from an upstream perspective, if our gaols is to optimzie the speed of getrandom(2) and /dev/urandom, and to encourage application programmers to do the right thing --- and *not* security theare for the sake of economic goals, we should make technical decisions accordingly.

Cheers,

- Ted

Hi Andy,

Um, let's not. This really isn't something the kernel needs to solve here at all. There's a viable userspace solution. I see that the discussion of something finally slightly technical (as opposed to just compliance BS) has nerd sniped you a bit, but keep in mind what the actual overall picture is. This isn't something that needs to be done. My little CUSE thing (which I'm happy to develop out a bit more, even) has the intent of fulfilling a compliance checkbox and nothing more.

Jason

Can you develop your CUSE thing enough that it’s credibly safe against side channels? If so, fine.

I admit this is all rather absurd. FIPS aware userspace can do whatever it wants, and
It should be aware that /dev/urandom IS NOT FIPS. What’s the problem? rand(3) isn’t FIPS either, but no one puts person-years of effort into trying to paint it FIPS-colored

Just in case you were curious...

The below took all of 5 minutes to write. Should be easy to tweak this for whatever flavors required.

====

/* Copyright (C) 2022 Jason A. Donenfeld <[email protected]>. All Rights Reserved.
*
* Usage:

 *   # gcc -O2 jrandom.c `pkg-config fuse3 --cflags --libs` -o jrandom
 *   # ./jrandom
 *   # chmod 666 /dev/jrandom
 *   # ln -sf jrandom /dev/urandom
 *   # ln -sf jrandom /dev/random

*/

#define FUSE_USE_VERSION 31

#include <cuse_lowlevel.h>
#include <fuse_opt.h>
#include <sys/types.h>
#include <sys/socket.h>
#include <linux/if_alg.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <errno.h>

static int rng;

static void fipsrng_open(fuse_req_t req, struct fuse_file_info *fi)

{
	fuse_reply_open(req, fi);
}

static void fipsrng_read(fuse_req_t req, size_t size, off_t off,
struct fuse_file_info *fi)

{
	char random[128];
	ssize_t ret_bytes;

	if (size > sizeof(random))
		size = sizeof(random);

	ret_bytes = read(rng, random, size);
	if (ret_bytes < 0)
		fuse_reply_err(req, errno);
	else
		fuse_reply_buf(req, random, ret_bytes);
}

static void fipsrng_write(fuse_req_t req, const char *buf, size_t size,
off_t off, struct fuse_file_info *fi)

{
	/* Swallow it, we don't care. */
	fuse_reply_write(req, size);
}

static void fipsrng_ioctl(fuse_req_t req, int cmd, void *arg,
struct fuse_file_info *fi, unsigned flags, const void *in_buf, size_t in_bufsz, size_t out_bufsz)

{
	/* TODO: implement the various RNG ioctls */
	fuse_reply_err(req, ENOSYS);
}

static const struct cuse_lowlevel_ops fipsrng_clop = {
	.open		= fipsrng_open,
	.read		= fipsrng_read,
	.write		= fipsrng_write,
	.ioctl		= fipsrng_ioctl,
};

int main(int argc, char **argv)

{
	static const struct sockaddr_alg sa = {
		.salg_family = AF_ALG,
		.salg_type = "rng",
		.salg_name = "jitterentropy_rng"
	};
	static const char *dev_info_argv[] = { "DEVNAME=jrandom" };
	static const struct cuse_info ci = {
		.dev_info_argc = 1,
		.dev_info_argv = dev_info_argv,
		.flags = CUSE_UNRESTRICTED_IOCTL
	};
	struct fuse_args args = FUSE_ARGS_INIT(argc, argv);
	int ret = 1, afalg;

	if (fuse_opt_parse(&args, NULL, NULL, NULL)) {
		fprintf(stderr, "failed to parse options\n");
		goto out;
	}

	afalg = socket(AF_ALG, SOCK_SEQPACKET, 0);
	if (afalg < 0) {
		perror("socket(AF_ALG)");
		goto out;
	}
	if (bind(afalg, (const struct sockaddr *)&sa, sizeof(sa)) < 0) {
		perror("bind(\"rng\", \"jitterentropy_rng\")");
		goto out;
	}
	rng = accept(afalg, NULL, 0);
	if (rng < 0) {
		perror("accept()");
		goto out;
	}
	ret = cuse_lowlevel_main(args.argc, args.argv, &ci, &fipsrng_clop, NULL);
out:
	fuse_opt_free_args(&args);
	return ret;
}

No problem. And sorry for the delay.

It does because it basically replaces everything in random.c (for urandom in this case) with the Crypto API DRBG, which is compliant. Although it might be wiser to replace both urandom and random in this case.

Hi, Theodore.

I might be missing something, but the Crypto API DRBG is seeded by jitterentropy_rng and by get_random_bytes(), their outputs are both concatenated and used as the seed. So I don't think that should be a concern, right?

Regards,
Marcelo

It's not a question of whether some folks want it or not. They have to accept it due to policy. They have no choice in the matter.

I hope I don't sound argumentative. It's not my intention. But I know what it's like to have to comply with policies, even ones I don't like.

Jeff

I strongly doubt that policy dictates all of the current calls to get_random_*() require that they return data that is dictated by that policy. If so, that's not a valid specification for a variety of reasons (i.e. it will break other specification requirements...)

thanks,

greg k-h

I think I understand Ted's objections & I'm inclined to agree with them. See also this comment from Jon Callas:

" The NIST AES_CTR_DRBG is mostly-okay. It's got a few issues " (see <https://eprint.iacr.org/2020/619.pdf>), but you can get " around them. I don't like that it takes a simple concept (a good block " cipher is a good PRP/PRF) and throws enough scaffolding around it " to make it hard to understand. I understand the reasons .., it just " bugs me.

That said, people do want compliance with FIPS or various other standards. That raises a number of questions.

One is for Stephan: would you care to submit patches for the current driver that ONLY make it FIPS (and/or European standards) compliant? No jitter, no stuff to allow different crypto, no choice to replace the driver, ..., just FIPS. Some of those might be good ideas, but they would not belong in a FIPS patch.

I think that would have a much better chance of acceptance than your patches to date.

There are also more general questions:

The FIPS requirements for a deterministic RNG include a whole rat's nest of extras, notably various self-tests, which Stephan's patches might deal with. Or do any of the vendors have patches for that?

FIPS defines DRNGs using either a block cipher or a hash, but we use a stream cipher. According to Wikipedia, several of the *BSD distros do the same.
https://en.wikipedia.org/wiki/Salsa20#ChaCha20_adoption
This seems reasonable to me, but could we persuade NIST to add that option? I've added John Kelsey (one of the FIPS authors) to the cc list in hopes of that.

Failing that, the Blake hash function is based on Chacha
https://en.wikipedia.org/wiki/BLAKE_(hash_function)
Should we use that to get a more easily certified DRNG? Would that be as fast as Chacha alone?

The FIPS also require that all the entropy inputs to the DRNG be certified. I think we have a problem there.

I suspect that many of the random number instructions enabled by CONFIG_ARCH_RANDOM or the hardware RNGs enabled by CONFIG_HW_RANDOM could be certified, but that would need to be done by the vendors and the costs might be substantial. Are any already certified? Is there any vendor interest?

Apart from those, the current driver gets entropy in several places. The comments have:

* The current exported interfaces for gathering environmental noise
* from the devices are:
*
* void add_device_randomness(const void *buf, unsigned int size);
* void add_input_randomness(unsigned int type, unsigned int code,
* unsigned int value);
* void add_interrupt_randomness(int irq, int irq_flags);
* void add_disk_randomness(struct gendisk *disk);
*
* add_device_randomness() is for adding data to the random pool that
* is likely to differ between two devices (or possibly even per boot).
* This would be things like MAC addresses or serial numbers, ... *
* add_input_randomness() uses the input layer interrupt timing, as well as
* the event type information from the hardware.
*
* add_interrupt_randomness() uses the interrupt timing as random
* inputs to the entropy pool. Using the cycle counters and the irq source
* as inputs, it feeds the randomness roughly once a second.
*
* add_disk_randomness() uses what amounts to the seek time of block
* layer request events, ... Note that high-speed solid state drives with
* very low seek times do not make for good sources of entropy, ...

I think we should eliminate add_disk_randomness() since it does not work well on current hardware. Also, FIPS requires that entropy sources be independent & add_interrupt_randomness() depends on the same disk events so these sources may not be.

A similar argument could be made for getting rid of add_input_randomness() but that would lose the event type information. Does that matter?

The current driver also uses other sources, at least fast_mix(), add_timer_randomness(), random_get_entropy() and the gcc latent entropy plugin. Could/should those be simplified to get more easily audited or certified code?

The driver also allows input of external data which is mixed into the pool & provides an ioctl to let a user with root privileges change the pool's entropy estimate. Do either of those violate the FIPS requirement that only certified entropy sources be used? I'd be happy to lose the ioctl (or better, all the entropy estimation machinery) but those have been part of the system for decades. I'd definitely want to keep the option to use external inputs.

This whole "may not be" guessing game when it comes to FIPS certification is a huge problem. I have heard of different vendors getting different feedback and different implementations "passing" in different ways that totally contradict each other. It seems that there is a whole certification industry built up that you can use to try to pass these tests, but those tests are different depending on the vendor you use for this, making a total mess.

So perhaps getting solid answers, and having the FIPS people actually implement (or at least review) the changes and submit them (this is all open for everyone to see and work on), would be the best thing as that would at least let us know that this is what they require.

Otherwise, it's a total guess as you state many times in this email, and that is going to get us nowhere fast as the "requirements" end up contradicting themselves all the time.

Also, why does any of this have to be in the kernel at all? If FIPS requires a deterministic random number generator that will not allow entropy to be acquired from hardware or external inputs, why does the kernel care at all? Just write a fips_random.so library and get it certified and have any userspace code that cares about such a crazy thing to use that instead.

thanks,

greg k-h

Am Dienstag, 30. November 2021, 08:55:53 CET schrieb Greg Kroah-Hartman:

Hi Greg,

Just as a note: I am working as FIPS tester. I am part of the NIST entropy working group which oversees the entropy related requirements. The LRNG's FIPS compliant implementation is directly based on those requirements. The LRNG was even reviewed by NIST personnel who mentioned that they do not see any contradiction to the specification. Finally, we are pursuing to get a separate ENT validation from NIST for the LRNG which would indicate that the LRNG meets all their requirements.

Besides, the LRNG can be configured to have no FIPS bits included at all as documented in the patches and in the separately provided documentation. Yet, it offers a streamlined conditioning operation and a combination of different entropy source data which is obvious to not destroy entropy.

Ciao
Stephan

That's great, so you would be one of the best people to help submit changes to the existing code to have it be compliant, instead of replacing it entirely :)

thanks,

greg k-h

The kernel has had random(4) since Ted invented it sometime in the 90s. There's no question it's a good idea; that's why all the BSDs & some others have copied it. The only questions here are whether it could be made FIPS compliant & whether it should be.

It doesn't require that at all; in fact their DRNG design requires an external source of random bits. However, it requires that the source be certified & that would be a problem for us. Intel & others might be able to get their random number instructions certified and vendors of crypto or SOC chips might get theirs certified, but the kernel community could not do that.

I think the kernel's entropy collection routines are good enough that they could, in principle, be certified, but that would involve some work & considerable money.

That does not solve the problem. The library would also need a certified source of random inputs, so to get it certified you'd have to get something else certified first -- random(4), an instruction or a hardware rng.

Am Montag, 22. November 2021, 11:33:26 CET schrieb kernel test robot:

Hi,

Thanks for the notification.

I think this is a false-positive discussed before. __latent_entropy is seemingly allowed for an entire linear buffer as seen in the declaration of the variable input_pool_data in driver/char/random.c which is an array of u32.

The struct chacha20_state is a linear buffer of u32 words.

struct chacha20_block {
        u32 constants[4];
        union {
                u32 u[CHACHA_KEY_SIZE_WORDS];
                u8  b[CHACHA_KEY_SIZE];
        } key;
        u32 counter;
        u32 nonce[3];
};

Therefore it should be identical to the aforementioned example. The __latent_entropy marker therefore seems to be appropriate for this structure.

Ciao
Stephan

Hi Stephan,

Thanks for the explanation, we'll add the error to the ignore list.

Best Regards,
Rong Chen

No. It is a struct & there's no guarantee all compilers will lay it out as you expect. There might even be a gap in the layout since nonce[] has an odd number of elements.

First, this is completely unnecessary since the input pool is marked for latent entropy & changes there will affect the chacha context.

Also, if I'm reading the docs right, the __latent_entropy attribute on a data structure only gets it initialised somewhat randomly. If you want a continuous effect at runtime, then you need to make the code mix the latent_entropy global variable into the data structure.

Am Dienstag, 30. November 2021, 03:55:12 CET schrieb Sandy Harris:

Hi Sandy,

Thank you very much for your explanation. I will change my code accordingly.

Note, the LRNG does not have an input_pool.

Ciao
Stephan

The interrupt entropy source hooks into the interrupt handler via the add_interrupt_randomness function callback. Every interrupt received by the kernel is also sent to the LRNG for processing.

The IRQ entropy source performs the following processing:

1. Record a time stamp

2. Divide the time stamp by its greatest common divisor to eliminate fixed least significant bits.

3. Insert the 8 LSB of the result from step 2 into the collection pool.

4. When the collection pool is full, it is hashed into the per-CPU entropy pool (if continuous compression is enabled) or the latest time stamps overwrite the oldest entries in the collection pool.

If entropy is requested from the IRQ entropy pool, a message digest over all per-CPU entropy pool digests is calculated.

The GCD calculation is performed for the first 100 interupt time stamps. Until the GCD value is calculated, the full 32 bit time stamp is inserted into the collection pool.

Mathematical aspects Reviewed-by: "Peter, Matthias" <[email protected]>

---
 drivers/char/lrng/Kconfig       | 162 +++++++
 drivers/char/lrng/Makefile      |   2 +
 drivers/char/lrng/lrng_es_irq.c | 823 ++++++++++++++++++++++++++++++++
 drivers/char/lrng/lrng_es_irq.h |  71 +++
 4 files changed, 1058 insertions(+)
 create mode 100644 drivers/char/lrng/lrng_es_irq.c
 create mode 100644 drivers/char/lrng/lrng_es_irq.h

index 655d873480b0..a9ae35d9f648 100644
@@ -55,4 +55,166 @@ config LRNG_SEED_BUFFER_INIT_ADD_BITS
 
 endmenu # "Specific DRNG seeding strategies"
 
+menu "Entropy Source Configuration"
+
+comment "Interrupt Entropy Source"
+
+config LRNG_IRQ
+	bool "Enable Interrupt Entropy Source as LRNG Seed Source"
+	default y
+	help
+	  The LRNG models an entropy source based on the timing of the
+	  occurrence of interrupts. Enable this option to enable this
+	  IRQ entropy source.
+
+	  The IRQ entropy source is triggered every time an interrupt
+	  arrives and thus causes the interrupt handler to execute
+	  slightly longer. Disabling the IRQ entropy source implies
+	  that the performance penalty on the interrupt handler added
+	  by the LRNG is eliminated. Yet, this entropy source is
+	  considered to be the internal entropy source of the LRNG.
+	  Thus, only disable it if you ensured that other entropy
+	  sources are available that supply the LRNG with entropy.
+
+	  If you disable the IRQ entropy source, you MUST ensure
+	  one or more entropy sources collectively have the
+	  capability to deliver sufficient entropy with one invocation
+	  at a rate compliant to the security strength of the DRNG
+	  (usually 256 bits of entropy). In addition, if those
+	  entropy sources do not deliver sufficient entropy during
+	  first request, the reseed must be triggered from user
+	  space or kernel space when sufficient entropy is considered
+	  to be present.
+
+	  If unsure, say Y.
+
+choice
+	prompt "Continuous entropy compression boot time setting"
+	default LRNG_CONTINUOUS_COMPRESSION_ENABLED
+	depends on LRNG_IRQ
+	help
+	  Select the default behavior of the interrupt entropy source
+	  continuous compression operation.
+
+	  The Linux RNG collects entropy data during each interrupt.
+	  For performance reasons, a amount of entropy data defined by
+	  the LRNG entropy collection pool size is concatenated into
+	  an array. When that array is filled up, a hash is calculated
+	  to compress the entropy. That hash is calculated in
+	  interrupt context.
+
+	  In case such hash calculation in interrupt context is deemed
+	  too time-consuming, the continuous compression operation
+	  can be disabled. If disabled, the collection of entropy will
+	  not trigger a hash compression operation in interrupt context.
+	  The compression happens only when the DRNG is reseeded which is
+	  in process context. This implies that old entropy data
+	  collected after the last DRNG-reseed is overwritten with newer
+	  entropy data once the collection pool is full instead of
+	  retaining its entropy with the compression operation.
+
+	config LRNG_CONTINUOUS_COMPRESSION_ENABLED
+		bool "Enable continuous compression (default)"
+
+	config LRNG_CONTINUOUS_COMPRESSION_DISABLED
+		bool "Disable continuous compression"
+endchoice
+
+config LRNG_ENABLE_CONTINUOUS_COMPRESSION
+	bool
+	default y if LRNG_CONTINUOUS_COMPRESSION_ENABLED
+	default n if LRNG_CONTINUOUS_COMPRESSION_DISABLED
+
+config LRNG_SWITCHABLE_CONTINUOUS_COMPRESSION
+	bool "Runtime-switchable continuous entropy compression"
+	depends on LRNG_IRQ
+	help
+	  Per default, the interrupt entropy source continuous
+	  compression operation behavior is hard-wired into the kernel.
+	  Enable this option to allow it to be configurable at boot time.
+
+	  To modify the default behavior of the continuous
+	  compression operation, use the kernel command line option
+	  of lrng_sw_noise.lrng_pcpu_continuous_compression.
+
+	  If unsure, say N.
+
+choice
+	prompt "LRNG Entropy Collection Pool Size"
+	default LRNG_COLLECTION_SIZE_1024
+	depends on LRNG_IRQ
+	help
+	  Select the size of the LRNG entropy collection pool
+	  storing data for the interrupt entropy source without
+	  performing a compression operation. The larger the
+	  collection size is, the faster the average interrupt
+	  handling will be. The collection size represents the
+	  number of bytes of the per-CPU memory used to batch
+	  up entropy event data.
+
+	  The default value is good for regular operations. Choose
+	  larger sizes for servers that have no memory limitations.
+	  If runtime memory is precious, choose a smaller size.
+
+	  The collection size is unrelated to the entropy rate
+	  or the amount of entropy the LRNG can process.
+
+	config LRNG_COLLECTION_SIZE_32
+	depends on LRNG_CONTINUOUS_COMPRESSION_ENABLED
+	depends on !LRNG_SWITCHABLE_CONTINUOUS_COMPRESSION
+	depends on !LRNG_OVERSAMPLE_ENTROPY_SOURCES
+		bool "32 interrupt events"
+
+	config LRNG_COLLECTION_SIZE_256
+	depends on !LRNG_OVERSAMPLE_ENTROPY_SOURCES
+		bool "256 interrupt events"
+
+	config LRNG_COLLECTION_SIZE_512
+		bool "512 interrupt events"
+
+	config LRNG_COLLECTION_SIZE_1024
+		bool "1024 interrupt events (default)"
+
+	config LRNG_COLLECTION_SIZE_2048
+		bool "2048 interrupt events"
+
+	config LRNG_COLLECTION_SIZE_4096
+		bool "4096 interrupt events"
+
+	config LRNG_COLLECTION_SIZE_8192
+		bool "8192 interrupt events"
+
+endchoice
+
+config LRNG_COLLECTION_SIZE
+	int
+	default 32 if LRNG_COLLECTION_SIZE_32
+	default 256 if LRNG_COLLECTION_SIZE_256
+	default 512 if LRNG_COLLECTION_SIZE_512
+	default 1024 if LRNG_COLLECTION_SIZE_1024
+	default 2048 if LRNG_COLLECTION_SIZE_2048
+	default 4096 if LRNG_COLLECTION_SIZE_4096
+	default 8192 if LRNG_COLLECTION_SIZE_8192
+
+config LRNG_IRQ_ENTROPY_RATE
+	int "Interrupt Entropy Source Entropy Rate"
+	depends on LRNG_IRQ
+	range 256 4294967295
+	default 256
+	help
+	  The LRNG will collect the configured number of interrupts to
+	  obtain 256 bits of entropy. This value can be set to any between
+	  256 and 4294967295. The LRNG guarantees that this value is not
+	  lower than 256. This lower limit implies that one interrupt event
+	  is credited with one bit of entropy. This value is subject to the
+	  increase by the oversampling factor, if no high-resolution timer
+	  is found.
+
+	  In order to effectively disable the interrupt entropy source,
+	  the option has to be set to 4294967295. In this case, the
+	  interrupt entropy source will still deliver data but without
+	  being credited with entropy.
+
+endmenu # "Entropy Source Configuration"
+
 endif # LRNG

index 6f4603f897cd..d321d6d21a44 100644
@@ -6,3 +6,5 @@
 obj-y				+= lrng_es_mgr.o lrng_aux.o \
 				   lrng_drng.o lrng_chacha20.o \
 				   lrng_interfaces.o lrng_es_aux.o
+
+obj-$(CONFIG_LRNG_IRQ)		+= lrng_es_irq.o

2.31.1

The LRNG sysctl interface provides the same controls as the existing /dev/random implementation. These sysctls behave identically and are implemented identically. The goal is to allow a possible merge of the existing /dev/random implementation with this implementation which implies that this patch tries have a very close similarity. Yet, all sysctls are documented at [1].

In addition, it provides the file lrng_type which provides details about the LRNG:

- the name of the DRNG that produces the random numbers for /dev/random, /dev/urandom, getrandom(2)

- the hash used to produce random numbers from the entropy pool

- the number of secondary DRNG instances

- indicator whether the LRNG operates SP800-90B compliant

- indicator whether a high-resolution timer is identified - only with a high-resolution timer the interrupt noise source will deliver sufficient entropy

- indicator whether the LRNG has been minimally seeded (i.e. is the secondary DRNG seeded with at least 128 bits of entropy)

- indicator whether the LRNG has been fully seeded (i.e. is the secondary DRNG seeded with at least 256 bits of entropy)

[1] https://www.chronox.de/lrng.html

---
 drivers/char/lrng/Makefile          |   1 +
 drivers/char/lrng/lrng_interfaces.c |   2 -
 drivers/char/lrng/lrng_proc.c       | 199 ++++++++++++++++++++++++++++
 3 files changed, 200 insertions(+), 2 deletions(-)
 create mode 100644 drivers/char/lrng/lrng_proc.c

index d321d6d21a44..d7df72a702e4 100644
@@ -8,3 +8,4 @@ obj-y				+= lrng_es_mgr.o lrng_aux.o \
 				   lrng_interfaces.o lrng_es_aux.o
 
 obj-$(CONFIG_LRNG_IRQ)		+= lrng_es_irq.o
+obj-$(CONFIG_SYSCTL)		+= lrng_proc.o

index 6316a534bb54..b656aaf0c6cb 100644
@@ -38,8 +38,6 @@ static DECLARE_WAIT_QUEUE_HEAD(lrng_write_wait);
 static DECLARE_WAIT_QUEUE_HEAD(lrng_init_wait);
 static struct fasync_struct *fasync;
 
-struct ctl_table random_table[];
-
 /********************************** Helper ***********************************/
 
 /* Is the DRNG seed level too low? */

2.31.1

In order to improve NUMA-locality when serving getrandom(2) requests, allocate one DRNG instance per node.

The DRNG instance that is present right from the start of the kernel is reused as the first per-NUMA-node DRNG. For all remaining online NUMA nodes a new DRNG instance is allocated.

During boot time, the multiple DRNG instances are seeded sequentially. With this, the first DRNG instance (referenced as the initial DRNG in the code) is completely seeded with 256 bits of entropy before the next DRNG instance is completely seeded.

When random numbers are requested, the NUMA-node-local DRNG is checked whether it has been already fully seeded. If this is not the case, the initial DRNG is used to serve the request.

---
 drivers/char/lrng/Makefile    |   1 +
 drivers/char/lrng/lrng_numa.c | 122 ++++++++++++++++++++++++++++++++++
 2 files changed, 123 insertions(+)
 create mode 100644 drivers/char/lrng/lrng_numa.c

index d7df72a702e4..1e722e0967e0 100644
@@ -9,3 +9,4 @@ obj-y				+= lrng_es_mgr.o lrng_aux.o \
 
 obj-$(CONFIG_LRNG_IRQ)		+= lrng_es_irq.o
 obj-$(CONFIG_SYSCTL)		+= lrng_proc.o
+obj-$(CONFIG_NUMA)		+= lrng_numa.o

2.31.1

Certain CPUs provide instructions giving access to an entropy source (e.g. RDSEED on Intel/AMD, DARN on POWER, etc.). The LRNG can utilize the entropy source to seed its DRNG from.

Mathematical aspects Reviewed-by: "Peter, Matthias" <[email protected]>

---
 drivers/char/lrng/Kconfig              |  38 +++++
 drivers/char/lrng/Makefile             |   1 +
 drivers/char/lrng/lrng_es_archrandom.c | 226 +++++++++++++++++++++++++
 3 files changed, 265 insertions(+)
 create mode 100644 drivers/char/lrng/lrng_es_archrandom.c

index a9ae35d9f648..d3abdfa28493 100644
@@ -215,6 +215,44 @@ config LRNG_IRQ_ENTROPY_RATE
 	  interrupt entropy source will still deliver data but without
 	  being credited with entropy.
 
+comment "CPU Entropy Source"
+
+config LRNG_CPU
+	bool "Enable CPU Entropy Source as LRNG Seed Source"
+	default y
+	help
+	  Current CPUs commonly contain entropy sources which can be
+	  used to seed the LRNG. For example, the Intel RDSEED
+	  instruction, or the POWER DARN instruction will be sourced
+	  to seed the LRNG if this option is enabled.
+
+	  Note, if this option is enabled and the underlying CPU
+	  does not offer such entropy source, the LRNG will automatically
+	  detect this and ignore the hardware.
+
+config LRNG_CPU_FULL_ENT_MULTIPLIER
+	int
+	default 1 if !LRNG_TEST_CPU_ES_COMPRESSION
+	default 123 if LRNG_TEST_CPU_ES_COMPRESSION
+
+config LRNG_CPU_ENTROPY_RATE
+	int "CPU Entropy Source Entropy Rate"
+	depends on LRNG_CPU
+	range 0 256
+	default 8
+	help
+	  The option defines the amount of entropy the LRNG applies to 256
+	  bits of data obtained from the CPU entropy source. The LRNG
+	  enforces the limit that this value must be in the range between
+	  0 and 256.
+
+	  When configuring this value to 0, the CPU entropy source will
+	  provide 256 bits of data without being credited to contain
+	  entropy.
+
+	  Note, this option is overwritten when the option
+	  CONFIG_RANDOM_TRUST_CPU is set.
+
 endmenu # "Entropy Source Configuration"
 
 endif # LRNG

index 1e722e0967e0..1e18e2c1016b 100644
@@ -10,3 +10,4 @@ obj-y				+= lrng_es_mgr.o lrng_aux.o \
 obj-$(CONFIG_LRNG_IRQ)		+= lrng_es_irq.o
 obj-$(CONFIG_SYSCTL)		+= lrng_proc.o
 obj-$(CONFIG_NUMA)		+= lrng_numa.o
+obj-$(CONFIG_LRNG_CPU)		+= lrng_es_archrandom.o

2.31.1

Am Montag, 22. November 2021, 08:09:59 CET schrieb kernel test robot:

Hi,

Thank you for the note, this will be fixed.

Ciao
Stephan

The DRNG switch support allows replacing the DRNG mechanism of the LRNG. The switching support rests on the interface definition of include/linux/lrng.h. A new DRNG is implemented by filling in the interface defined in this header file.

In addition to the DRNG, the extension also has to provide a hash implementation that is used to hash the entropy pool for random number extraction.

Note: It is permissible to implement a DRNG whose operations may sleep. However, the hash function must not sleep.

The switchable DRNG support allows replacing the DRNG at runtime. However, only one DRNG extension is allowed to be loaded at any given time. Before replacing it with another DRNG implementation, the possibly existing DRNG extension must be unloaded.

The switchable DRNG extension activates the new DRNG during load time. It is expected, however, that such a DRNG switch would be done only once by an administrator to load the intended DRNG implementation.

It is permissible to compile DRNG extensions either as kernel modules or statically. The initialization of the DRNG extension should be performed with a late_initcall to ensure the extension is available when user space starts but after all other initialization completed. The initialization is performed by registering the function call data structure with the lrng_set_drng_cb function. In order to unload the DRNG extension, lrng_set_drng_cb must be invoked with the NULL parameter.

The DRNG extension should always provide a security strength that is at least as strong as LRNG_DRNG_SECURITY_STRENGTH_BITS.

The hash extension must not sleep and must not maintain a separate state.

---
 drivers/char/lrng/Kconfig       |   7 +
 drivers/char/lrng/Makefile      |   1 +
 drivers/char/lrng/lrng_switch.c | 226 ++++++++++++++++++++++++++++++++
 3 files changed, 234 insertions(+)
 create mode 100644 drivers/char/lrng/lrng_switch.c

index d3abdfa28493..9fea73b72f88 100644
@@ -255,4 +255,11 @@ config LRNG_CPU_ENTROPY_RATE
 
 endmenu # "Entropy Source Configuration"
 
+menuconfig LRNG_DRNG_SWITCH
+	bool "Support DRNG runtime switching"
+	help
+	  The Linux RNG per default uses a ChaCha20 DRNG that is
+	  accessible via the external interfaces. With this configuration
+	  option other DRNGs can be selected and loaded at runtime.
+
 endif # LRNG

index 1e18e2c1016b..2202aa78b63f 100644
@@ -11,3 +11,4 @@ obj-$(CONFIG_LRNG_IRQ)		+= lrng_es_irq.o
 obj-$(CONFIG_SYSCTL)		+= lrng_proc.o
 obj-$(CONFIG_NUMA)		+= lrng_numa.o
 obj-$(CONFIG_LRNG_CPU)		+= lrng_es_archrandom.o
+obj-$(CONFIG_LRNG_DRNG_SWITCH)	+= lrng_switch.o

2.31.1

The LRNG switchable DRNG support also allows the replacement of the hash implementation used as conditioning component. The common generic hash support code provides the required callbacks using the synchronous hash implementations of the kernel crypto API.

All synchronous hash implementations supported by the kernel crypto API can be used as part of the LRNG with this generic support.

The generic support is intended to be configured by separate switchable DRNG backends.

---
 drivers/char/lrng/Kconfig           |   8 +++
 drivers/char/lrng/Makefile          |   1 +
 drivers/char/lrng/lrng_kcapi_hash.c | 103 ++++++++++++++++++++++++++++
 drivers/char/lrng/lrng_kcapi_hash.h |  20 ++++++
 4 files changed, 132 insertions(+)
 create mode 100644 drivers/char/lrng/lrng_kcapi_hash.c
 create mode 100644 drivers/char/lrng/lrng_kcapi_hash.h

index 9fea73b72f88..531b34b9ae65 100644
@@ -262,4 +262,12 @@ menuconfig LRNG_DRNG_SWITCH
 	  accessible via the external interfaces. With this configuration
 	  option other DRNGs can be selected and loaded at runtime.
 
+if LRNG_DRNG_SWITCH
+
+config LRNG_KCAPI_HASH
+	bool
+	select CRYPTO_HASH
+
+endif # LRNG_DRNG_SWITCH
+
 endif # LRNG

index 2202aa78b63f..cb9b03bdfd00 100644
@@ -12,3 +12,4 @@ obj-$(CONFIG_SYSCTL)		+= lrng_proc.o
 obj-$(CONFIG_NUMA)		+= lrng_numa.o
 obj-$(CONFIG_LRNG_CPU)		+= lrng_es_archrandom.o
 obj-$(CONFIG_LRNG_DRNG_SWITCH)	+= lrng_switch.o
+obj-$(CONFIG_LRNG_KCAPI_HASH)	+= lrng_kcapi_hash.o

new file mode 100644
index 000000000000..2f94558d2dd6
@@ -0,0 +1,20 @@
+/* SPDX-License-Identifier: GPL-2.0 OR BSD-2-Clause */
+/*
+ * Copyright (C) 2020 - 2021, Stephan Mueller <[email protected]>
+ */
+
+#ifndef _LRNG_KCAPI_HASH_H
+#define _LRNG_KCAPI_HASH_H
+
+#include <linux/module.h>
+
+void *lrng_kcapi_hash_alloc(const char *name);
+u32 lrng_kcapi_hash_digestsize(void *hash);
+void lrng_kcapi_hash_dealloc(void *hash);
+int lrng_kcapi_hash_init(struct shash_desc *shash, void *hash);
+int lrng_kcapi_hash_update(struct shash_desc *shash, const u8 *inbuf,
+			   u32 inbuflen);
+int lrng_kcapi_hash_final(struct shash_desc *shash, u8 *digest);
+void lrng_kcapi_hash_zero(struct shash_desc *shash);
+
+#endif /* _LRNG_KCAPI_HASH_H */

2.31.1

This patch allows several DRBG functions to be called by the LRNG kernel code paths outside the drbg.c file.

---
 crypto/drbg.c         | 16 ++++++++++------
 include/crypto/drbg.h |  7 +++++++
 2 files changed, 17 insertions(+), 6 deletions(-)

index ea85d4a0fe9e..74a9dca67698 100644
@@ -114,7 +114,7 @@
  * the SHA256 / AES 256 over other ciphers. Thus, the favored
  * DRBGs are the latest entries in this array.
  */
-static const struct drbg_core drbg_cores[] = {
+const struct drbg_core drbg_cores[] = {
 #ifdef CONFIG_CRYPTO_DRBG_CTR
 	{
 		.flags = DRBG_CTR | DRBG_STRENGTH128,

@@ -191,6 +191,7 @@ static const struct drbg_core drbg_cores[] = {
 	},
 #endif /* CONFIG_CRYPTO_DRBG_HMAC */
 };
+EXPORT_SYMBOL(drbg_cores);
 
 static int drbg_uninstantiate(struct drbg_state *drbg);
 

@@ -206,7 +207,7 @@ static int drbg_uninstantiate(struct drbg_state *drbg);
  * Return: normalized strength in *bytes* value or 32 as default
  *	   to counter programming errors
  */
-static inline unsigned short drbg_sec_strength(drbg_flag_t flags)
+unsigned short drbg_sec_strength(drbg_flag_t flags)
 {
 	switch (flags & DRBG_STRENGTH_MASK) {
 	case DRBG_STRENGTH128:

@@ -219,6 +220,7 @@ static inline unsigned short drbg_sec_strength(drbg_flag_t flags)
 		return 32;
 	}
 }
+EXPORT_SYMBOL(drbg_sec_strength);
 
 /*
  * FIPS 140-2 continuous self test for the noise source

@@ -1215,7 +1217,7 @@ static int drbg_seed(struct drbg_state *drbg, struct drbg_string *pers,
 }
 
 /* Free all substructures in a DRBG state without the DRBG state structure */
-static inline void drbg_dealloc_state(struct drbg_state *drbg)
+void drbg_dealloc_state(struct drbg_state *drbg)
 {
 	if (!drbg)
 		return;

@@ -1236,12 +1238,13 @@ static inline void drbg_dealloc_state(struct drbg_state *drbg)
 		drbg->fips_primed = false;
 	}
 }
+EXPORT_SYMBOL(drbg_dealloc_state);
 
 /*
  * Allocate all sub-structures for a DRBG state.
  * The DRBG state structure must already be allocated.
  */
-static inline int drbg_alloc_state(struct drbg_state *drbg)
+int drbg_alloc_state(struct drbg_state *drbg)
 {
 	int ret = -ENOMEM;
 	unsigned int sb_size = 0;

@@ -1322,6 +1325,7 @@ static inline int drbg_alloc_state(struct drbg_state *drbg)
 	drbg_dealloc_state(drbg);
 	return ret;
 }
+EXPORT_SYMBOL(drbg_alloc_state);
 
 /*************************************************************************
  * DRBG interface functions

@@ -1891,8 +1895,7 @@ static int drbg_kcapi_sym_ctr(struct drbg_state *drbg,
  *
  * return: flags
  */
-static inline void drbg_convert_tfm_core(const char *cra_driver_name,
-					 int *coreref, bool *pr)
+void drbg_convert_tfm_core(const char *cra_driver_name, int *coreref, bool *pr)
 {
 	int i = 0;
 	size_t start = 0;

@@ -1919,6 +1922,7 @@ static inline void drbg_convert_tfm_core(const char *cra_driver_name,
 		}
 	}
 }
+EXPORT_SYMBOL(drbg_convert_tfm_core);
 
 static int drbg_kcapi_init(struct crypto_tfm *tfm)
 {

index c4165126937e..71d53e028e6d 100644
@@ -278,4 +278,11 @@ enum drbg_prefixes {
 	DRBG_PREFIX3
 };
 
+extern int drbg_alloc_state(struct drbg_state *drbg);
+extern void drbg_dealloc_state(struct drbg_state *drbg);
+extern void drbg_convert_tfm_core(const char *cra_driver_name, int *coreref,
+				  bool *pr);
+extern const struct drbg_core drbg_cores[];
+extern unsigned short drbg_sec_strength(drbg_flag_t flags);
+
 #endif /* _DRBG_H */

2.31.1

Using the LRNG switchable DRNG support, the SP800-90A DRBG extension is implemented.

The DRBG uses the kernel crypto API DRBG implementation. In addition, it uses the kernel crypto API SHASH support to provide the hashing operation.

The DRBG supports the choice of either a CTR DRBG using AES-256, HMAC DRBG with SHA-512 core or Hash DRBG with SHA-512 core. The used core can be selected with the module parameter lrng_drbg_type. The default is the CTR DRBG.

When compiling the DRBG extension statically, the DRBG is loaded at late_initcall stage which implies that with the start of user space, the user space interfaces of getrandom(2), /dev/random and /dev/urandom provide random data produced by an SP800-90A DRBG.

---
 drivers/char/lrng/Kconfig     |  10 ++
 drivers/char/lrng/Makefile    |   1 +
 drivers/char/lrng/lrng_drbg.c | 198 ++++++++++++++++++++++++++++++++++
 3 files changed, 209 insertions(+)
 create mode 100644 drivers/char/lrng/lrng_drbg.c

index 531b34b9ae65..d06d0417b025 100644
@@ -268,6 +268,16 @@ config LRNG_KCAPI_HASH
 	bool
 	select CRYPTO_HASH
 
+config LRNG_DRBG
+	tristate "SP800-90A support for the LRNG"
+	depends on CRYPTO
+	select CRYPTO_DRBG_MENU
+	select CRYPTO_SHA512
+	select LRNG_KCAPI_HASH
+	help
+	  Enable the SP800-90A DRBG support for the LRNG. Once the
+	  module is loaded, output from /dev/random, /dev/urandom,
+	  getrandom(2), or get_random_bytes_full is provided by a DRBG.
 endif # LRNG_DRNG_SWITCH
 
 endif # LRNG

index cb9b03bdfd00..c00e15b6396e 100644
@@ -13,3 +13,4 @@ obj-$(CONFIG_NUMA)		+= lrng_numa.o
 obj-$(CONFIG_LRNG_CPU)		+= lrng_es_archrandom.o
 obj-$(CONFIG_LRNG_DRNG_SWITCH)	+= lrng_switch.o
 obj-$(CONFIG_LRNG_KCAPI_HASH)	+= lrng_kcapi_hash.o
+obj-$(CONFIG_LRNG_DRBG)		+= lrng_drbg.o

2.31.1

Add runtime-pluggable support for all PRNGs that are accessible via the kernel crypto API, including hardware PRNGs. The PRNG is selected with the module parameter drng_name where the name must be one that the kernel crypto API can resolve into an RNG.

This allows using of the kernel crypto API PRNG implementations that provide an interface to hardware PRNGs. Using this extension, the LRNG uses the hardware PRNGs to generate random numbers. An example is the S390 CPACF support providing such a PRNG.

The hash is provided by a kernel crypto API SHASH whose digest size complies with the seedsize of the PRNG.

---
 drivers/char/lrng/Kconfig      |  13 ++
 drivers/char/lrng/Makefile     |   1 +
 drivers/char/lrng/lrng_kcapi.c | 227 +++++++++++++++++++++++++++++++++
 3 files changed, 241 insertions(+)
 create mode 100644 drivers/char/lrng/lrng_kcapi.c

index d06d0417b025..25684c54d6a9 100644
@@ -278,6 +278,19 @@ config LRNG_DRBG
 	  Enable the SP800-90A DRBG support for the LRNG. Once the
 	  module is loaded, output from /dev/random, /dev/urandom,
 	  getrandom(2), or get_random_bytes_full is provided by a DRBG.
+
+config LRNG_KCAPI
+	tristate "Kernel Crypto API support for the LRNG"
+	depends on CRYPTO
+	depends on !LRNG_DRBG
+	select CRYPTO_RNG
+	select LRNG_KCAPI_HASH
+	help
+	  Enable the support for generic pseudo-random number
+	  generators offered by the kernel crypto API with the
+	  LRNG. Once the module is loaded, output from /dev/random,
+	  /dev/urandom, getrandom(2), or get_random_bytes is
+	  provided by the selected kernel crypto API RNG.
 endif # LRNG_DRNG_SWITCH
 
 endif # LRNG

index c00e15b6396e..85abeaa68136 100644
@@ -14,3 +14,4 @@ obj-$(CONFIG_LRNG_CPU)		+= lrng_es_archrandom.o
 obj-$(CONFIG_LRNG_DRNG_SWITCH)	+= lrng_switch.o
 obj-$(CONFIG_LRNG_KCAPI_HASH)	+= lrng_kcapi_hash.o
 obj-$(CONFIG_LRNG_DRBG)		+= lrng_drbg.o
+obj-$(CONFIG_LRNG_KCAPI)	+= lrng_kcapi.o

2.31.1

To support the LRNG operation which uses the Jitter RNG separately from the kernel crypto API, the header file must be accessible to the LRNG code.

---
 crypto/jitterentropy-kcapi.c                        | 3 +--
 crypto/jitterentropy.c                              | 2 +-
 {crypto => include/crypto/internal}/jitterentropy.h | 0
 3 files changed, 2 insertions(+), 3 deletions(-)
 rename {crypto => include/crypto/internal}/jitterentropy.h (100%)

index e8a4165a1874..c90e60910827 100644
@@ -43,8 +43,7 @@
 #include <linux/fips.h>
 #include <linux/time.h>
 #include <crypto/internal/rng.h>
-
-#include "jitterentropy.h"
+#include <crypto/internal/jitterentropy.h>
 
 /***************************************************************************
  * Helper function

index a11b3208760f..f36a391319e1 100644
@@ -117,7 +117,7 @@ struct rand_data {
 #define JENT_EHEALTH		9 /* Health test failed during initialization */
 #define JENT_ERCT		10 /* RCT failed during initialization */
 
-#include "jitterentropy.h"
+#include <crypto/internal/jitterentropy.h>
 
 /***************************************************************************
  * Adaptive Proportion Test

similarity index 100%
rename from crypto/jitterentropy.h
rename to include/crypto/internal/jitterentropy.h

2.31.1

The Jitter RNG fast noise source implemented as part of the kernel crypto API is queried for 256 bits of entropy at the time the seed buffer managed by the LRNG is about to be filled.

---
 drivers/char/lrng/Kconfig        | 29 ++++++++++
 drivers/char/lrng/Makefile       |  1 +
 drivers/char/lrng/lrng_es_jent.c | 97 ++++++++++++++++++++++++++++++++
 3 files changed, 127 insertions(+)
 create mode 100644 drivers/char/lrng/lrng_es_jent.c

index 25684c54d6a9..478b12839907 100644
@@ -215,6 +215,35 @@ config LRNG_IRQ_ENTROPY_RATE
 	  interrupt entropy source will still deliver data but without
 	  being credited with entropy.
 
+comment "Jitter RNG Entropy Source"
+
+config LRNG_JENT
+	bool "Enable Jitter RNG as LRNG Seed Source"
+	depends on CRYPTO
+	select CRYPTO_JITTERENTROPY
+	help
+	  The Linux RNG may use the Jitter RNG as noise source. Enabling
+	  this option enables the use of the Jitter RNG. Its default
+	  entropy level is 16 bits of entropy per 256 data bits delivered
+	  by the Jitter RNG. This entropy level can be changed at boot
+	  time or at runtime with the lrng_base.jitterrng configuration
+	  variable.
+
+config LRNG_JENT_ENTROPY_RATE
+	int "Jitter RNG Entropy Source Entropy Rate"
+	depends on LRNG_JENT
+	range 0 256
+	default 16
+	help
+	  The option defines the amount of entropy the LRNG applies to 256
+	  bits of data obtained from the Jitter RNG entropy source. The
+	  LRNG enforces the limit that this value must be in the range
+	  between 0 and 256.
+
+	  When configuring this value to 0, the Jitter RNG entropy source
+	  will provide 256 bits of data without being credited to contain
+	  entropy.
+
 comment "CPU Entropy Source"
 
 config LRNG_CPU

index 85abeaa68136..c797fbd10a98 100644
@@ -15,3 +15,4 @@ obj-$(CONFIG_LRNG_DRNG_SWITCH)	+= lrng_switch.o
 obj-$(CONFIG_LRNG_KCAPI_HASH)	+= lrng_kcapi_hash.o
 obj-$(CONFIG_LRNG_DRBG)		+= lrng_drbg.o
 obj-$(CONFIG_LRNG_KCAPI)	+= lrng_kcapi.o
+obj-$(CONFIG_LRNG_JENT)		+= lrng_es_jent.o

2.31.1

Implement health tests for LRNG's slow noise sources as mandated by SP-800-90B The file contains the following health tests:

- stuck test: The stuck test calculates the first, second and third discrete derivative of the time stamp to be processed by the hash for the per-CPU entropy pool. Only if all three values are non-zero, the received time delta is considered to be non-stuck.

- SP800-90B Repetition Count Test (RCT): The LRNG uses an enhanced version of the RCT specified in SP800-90B section 4.4.1. Instead of counting identical back-to-back values, the input to the RCT is the counting of the stuck values during the processing of received interrupt events. The RCT is applied with alpha=2^-30 compliant to the recommendation of FIPS 140-2 IG 9.8. During the counting operation, the LRNG always calculates the RCT cut-off value of C. If that value exceeds the allowed cut-off value, the LRNG will trigger the health test failure discussed below. An error is logged to the kernel log that such RCT failure occurred. This test is only applied and enforced in FIPS mode, i.e. when the kernel compiled with CONFIG_CONFIG_FIPS is started with fips=1.

- SP800-90B Adaptive Proportion Test (APT): The LRNG implements the APT as defined in SP800-90B section 4.4.2. The applied significance level again is alpha=2^-30 compliant to the recommendation of FIPS 140-2 IG 9.8.

The aforementioned health tests are applied to the first 1,024 time stamps obtained from interrupt events. In case one error is identified for either the RCT, or the APT, the collected entropy is invalidated and the SP800-90B startup health test is restarted.

As long as the SP800-90B startup health test is not completed, all LRNG random number output interfaces that may block will block and not generate any data. This implies that only those potentially blocking interfaces are defined to provide random numbers that are seeded with the interrupt noise source being SP800-90B compliant. All other output interfaces will not be affected by the SP800-90B startup test and thus are not considered SP800-90B compliant.

At runtime, the SP800-90B APT and RCT are applied to each time stamp generated for a received interrupt. When either the APT and RCT indicates a noise source failure, the LRNG is reset to a state it has immediately after boot:

- all entropy counters are set to zero

- the SP800-90B startup tests are re-performed which implies that getrandom(2) would block again until new entropy was collected

To summarize, the following rules apply:

• SP800-90B compliant output interfaces

- /dev/random

- getrandom(2) system call

- 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

- 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

If either the RCT, or the APT health test fails irrespective whether during initialization or runtime, the following actions occur:

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 of the startup tests. 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.

Further details on the SP800-90B compliance and the availability of all test tools required to perform all tests mandated by SP800-90B are provided at [1].

The entire health testing code is compile-time configurable.

The patch provides a CONFIG_BROKEN configuration of the APT / RCT cutoff values which have a high likelihood to trigger the health test failure. The BROKEN APT cutoff is set to the exact mean of the expected value if the time stamps are equally distributed (512 time stamps divided by 16 possible values due to using the 4 LSB of the time stamp). The BROKEN RCT cutoff value is set to 1 which is likely to be triggered during regular operation.

---
 drivers/char/lrng/Kconfig       |  58 +++++
 drivers/char/lrng/Makefile      |   1 +
 drivers/char/lrng/lrng_health.c | 410 ++++++++++++++++++++++++++++++++
 3 files changed, 469 insertions(+)
 create mode 100644 drivers/char/lrng/lrng_health.c

index 478b12839907..bc1b85929b94 100644
@@ -196,6 +196,64 @@ config LRNG_COLLECTION_SIZE
 	default 4096 if LRNG_COLLECTION_SIZE_4096
 	default 8192 if LRNG_COLLECTION_SIZE_8192
 
+config LRNG_HEALTH_TESTS
+	bool "Enable interrupt entropy source online health tests"
+	depends on LRNG_IRQ
+	help
+	  The online health tests applied to the interrupt entropy
+	  source validate the noise source at runtime for fatal
+	  errors. These tests include SP800-90B compliant tests
+	  which are invoked if the system is booted with fips=1.
+	  In case of fatal errors during active SP800-90B tests,
+	  the issue is logged and the noise data is discarded.
+	  These tests are required for full compliance of the
+	  interrupt entropy source with SP800-90B.
+
+	  If unsure, say Y.
+
+config LRNG_RCT_BROKEN
+	bool "SP800-90B RCT with dangerous low cutoff value"
+	depends on LRNG_HEALTH_TESTS
+	depends on BROKEN
+	default n
+	help
+	  This option enables a dangerously low SP800-90B repetitive
+	  count test (RCT) cutoff value which makes it very likely
+	  that the RCT is triggered to raise a self test failure.
+
+	  This option is ONLY intended for developers wanting to
+	  test the effectiveness of the SP800-90B RCT health test.
+
+	  If unsure, say N.
+
+config LRNG_APT_BROKEN
+	bool "SP800-90B APT with dangerous low cutoff value"
+	depends on LRNG_HEALTH_TESTS
+	depends on BROKEN
+	default n
+	help
+	  This option enables a dangerously low SP800-90B adaptive
+	  proportion test (APT) cutoff value which makes it very
+	  likely that the APT is triggered to raise a self test
+	  failure.
+
+	  This option is ONLY intended for developers wanting to
+	  test the effectiveness of the SP800-90B APT health test.
+
+	  If unsure, say N.
+
+# Default taken from SP800-90B sec 4.4.1 - significance level 2^-30
+config LRNG_RCT_CUTOFF
+	int
+	default 31 if !LRNG_RCT_BROKEN
+	default 1 if LRNG_RCT_BROKEN
+
+# Default taken from SP800-90B sec 4.4.2 - significance level 2^-30
+config LRNG_APT_CUTOFF
+	int
+	default 325 if !LRNG_APT_BROKEN
+	default 32 if LRNG_APT_BROKEN
+
 config LRNG_IRQ_ENTROPY_RATE
 	int "Interrupt Entropy Source Entropy Rate"
 	depends on LRNG_IRQ

index c797fbd10a98..f868f9fe53a6 100644
@@ -16,3 +16,4 @@ obj-$(CONFIG_LRNG_KCAPI_HASH)	+= lrng_kcapi_hash.o
 obj-$(CONFIG_LRNG_DRBG)		+= lrng_drbg.o
 obj-$(CONFIG_LRNG_KCAPI)	+= lrng_kcapi.o
 obj-$(CONFIG_LRNG_JENT)		+= lrng_es_jent.o
+obj-$(CONFIG_LRNG_HEALTH_TESTS)	+= lrng_health.o

2.31.1

The test interface allows a privileged process to capture the raw unconditioned noise that is collected by the LRNG for statistical analysis. Such testing allows the analysis how much entropy the interrupt noise source provides on a given platform. Extracted noise data is not used to seed the LRNG. This is a test interface and not appropriate for production systems. Yet, the interface is considered to be sufficiently secured for production systems.

Access to the data is given through the lrng_raw debugfs file. The data buffer should be multiples of sizeof(u32) to fill the entire buffer. Using the option lrng_testing.boot_test=1 the raw noise of the first 1000 entropy events since boot can be sampled.

This test interface allows generating the data required for analysis whether the LRNG is in compliance with SP800-90B sections 3.1.3 and 3.1.4.

In addition, the test interface allows gathering of the concatenated raw entropy data to verify that the concatenation works appropriately. This includes sampling of the following raw data:

* high-resolution time stamp

* Jiffies

* IRQ number

* IRQ flags

* return instruction pointer

* interrupt register state

* array logic batching the high-resolution time stamp

* enabling the runtime configuration of entropy source entropy rates

Also, a testing interface to support ACVT of the hash implementation is provided. The reason why only hash testing is supported (as opposed to also provide testing for the DRNG) is the fact that the LRNG software hash implementation contains glue code that may warrant testing in addition to the testing of the software ciphers via the kernel crypto API. Also, for testing the CTR-DRBG, the underlying AES implementation would need to be tested. However, such AES test interface cannot be provided by the LRNG as it has no means to access the AES operation.

Finally, the execution duration for processing a time stamp can be obtained with the LRNG raw entropy interface.

If a test interface is not compiled, its code is a noop which has no impact on the performance.

---
 drivers/char/lrng/Kconfig        | 180 ++++++++
 drivers/char/lrng/Makefile       |   1 +
 drivers/char/lrng/lrng_testing.c | 689 +++++++++++++++++++++++++++++++
 3 files changed, 870 insertions(+)
 create mode 100644 drivers/char/lrng/lrng_testing.c

index bc1b85929b94..72b572cb7df5 100644
@@ -380,4 +380,184 @@ config LRNG_KCAPI
 	  provided by the selected kernel crypto API RNG.
 endif # LRNG_DRNG_SWITCH
 
+menuconfig LRNG_TESTING_MENU
+	bool "LRNG testing interfaces"
+	depends on DEBUG_FS
+	help
+	  Enable one or more of the following test interfaces.
+
+	  If unsure, say N.
+
+if LRNG_TESTING_MENU
+
+config LRNG_RAW_HIRES_ENTROPY
+	bool "Enable entropy test interface to hires timer noise source"
+	default y
+	help
+	  The test interface allows a privileged process to capture
+	  the raw unconditioned high resolution time stamp noise that
+	  is collected by the LRNG for statistical analysis. Extracted
+	  noise data is not used to seed the LRNG.
+
+	  The raw noise data can be obtained using the lrng_raw_hires
+	  debugfs file. Using the option lrng_testing.boot_raw_hires_test=1
+	  the raw noise of the first 1000 entropy events since boot
+	  can be sampled.
+
+config LRNG_RAW_JIFFIES_ENTROPY
+	bool "Enable entropy test interface to Jiffies noise source"
+	help
+	  The test interface allows a privileged process to capture
+	  the raw unconditioned Jiffies that is collected by
+	  the LRNG for statistical analysis. This data is used for
+	  seeding the LRNG if a high-resolution time stamp is not
+	  available. If a high-resolution time stamp is detected,
+	  the Jiffies value is not collected by the LRNG and no
+	  data is provided via the test interface. Extracted noise
+	  data is not used to seed the random number generator.
+
+	  The raw noise data can be obtained using the lrng_raw_jiffies
+	  debugfs file. Using the option lrng_testing.boot_raw_jiffies_test=1
+	  the raw noise of the first 1000 entropy events since boot
+	  can be sampled.
+
+config LRNG_RAW_IRQ_ENTROPY
+	bool "Enable entropy test interface to IRQ number noise source"
+	help
+	  The test interface allows a privileged process to capture
+	  the raw unconditioned interrupt number that is collected by
+	  the LRNG for statistical analysis. This data is used for
+	  seeding the random32 PRNG external to the LRNG if a
+	  high-resolution time stamp is available or it will be used to
+	  seed the LRNG otherwise. Extracted noise data is not used to
+	  seed the random number generator.
+
+	  The raw noise data can be obtained using the lrng_raw_irq
+	  debugfs file. Using the option lrng_testing.boot_raw_irq_test=1
+	  the raw noise of the first 1000 entropy events since boot
+	  can be sampled.
+
+config LRNG_RAW_IRQFLAGS_ENTROPY
+	bool "Enable entropy test interface to IRQ flags noise source"
+	help
+	  The test interface allows a privileged process to capture
+	  the raw unconditioned interrupt flags that is collected by
+	  the LRNG for statistical analysis. This data is used for
+	  seeding the random32 PRNG external to the LRNG if a
+	  high-resolution time stamp is available or it will be used to
+	  seed the LRNG otherwise. Extracted noise data is not used to
+	  seed the random number generator.
+
+	  The raw noise data can be obtained using the lrng_raw_irqflags
+	  debugfs file. Using the option lrng_testing.boot_raw_irqflags_test=1
+	  the raw noise of the first 1000 entropy events since boot
+	  can be sampled.
+
+config LRNG_RAW_RETIP_ENTROPY
+	bool "Enable entropy test interface to RETIP value noise source"
+	help
+	  The test interface allows a privileged process to capture
+	  the raw unconditioned return instruction pointer value
+	  that is collected by the LRNG for statistical analysis.
+	  This data is used for seeding the random32 PRNG external
+	  to the LRNG if a high-resolution time stamp is available or
+	  it will be used to seed the LRNG otherwise. Extracted noise
+	  data is not used to seed the random number generator.
+
+	  The raw noise data can be obtained using the lrng_raw_retip
+	  debugfs file. Using the option lrng_testing.boot_raw_retip_test=1
+	  the raw noise of the first 1000 entropy events since boot
+	  can be sampled.
+
+config LRNG_RAW_REGS_ENTROPY
+	bool "Enable entropy test interface to IRQ register value noise source"
+	help
+	  The test interface allows a privileged process to capture
+	  the raw unconditioned interrupt register value that is
+	  collected by the LRNG for statistical analysis. Extracted noise
+	  data is not used to seed the random number generator.
+
+	  The raw noise data can be obtained using the lrng_raw_regs
+	  debugfs file. Using the option lrng_testing.boot_raw_regs_test=1
+	  the raw noise of the first 1000 entropy events since boot
+	  can be sampled.
+
+config LRNG_RAW_ARRAY
+	bool "Enable test interface to LRNG raw entropy storage array"
+	help
+	  The test interface allows a privileged process to capture
+	  the raw noise data that is collected by the LRNG
+	  in the per-CPU array for statistical analysis. The purpose
+	  of this interface is to verify that the array handling code
+	  truly only concatenates data and provides the same entropy
+	  rate as the raw unconditioned noise source when assessing
+	  the collected data byte-wise.
+
+	  The data can be obtained using the lrng_raw_array debugfs
+	  file. Using the option lrng_testing.boot_raw_array=1
+	  the raw noise of the first 1000 entropy events since boot
+	  can be sampled.
+
+config LRNG_IRQ_PERF
+	bool "Enable LRNG interrupt performance monitor"
+	help
+	  With this option, the performance monitor of the LRNG
+	  interrupt handling code is enabled. The file provides
+	  the execution time of the interrupt handler in
+	  cycles.
+
+	  The interrupt performance data can be obtained using
+	  the lrng_irq_perf debugfs file. Using the option
+	  lrng_testing.boot_irq_perf=1 the performance data of
+	  the first 1000 entropy events since boot can be sampled.
+
+config LRNG_ACVT_HASH
+	bool "Enable LRNG ACVT Hash interface"
+	help
+	  With this option, the LRNG built-in hash function used for
+	  auxiliary pool management and prior to switching the
+	  cryptographic backends is made available for ACVT. The
+	  interface allows writing of the data to be hashed
+	  into the interface. The read operation triggers the hash
+	  operation to generate message digest.
+
+	  The ACVT interface is available with the lrng_acvt_hash
+	  debugfs file.
+
+config LRNG_RUNTIME_ES_CONFIG
+	bool "Enable runtime configuration of entropy sources"
+	help
+	  When enabling this option, the LRNG provides the mechanism
+	  allowing to alter the entropy rate of each entropy source
+	  during boot time and runtime.
+
+	  The following interfaces are available:
+	  lrng_archrandom.archrandom for the CPU entropy source,
+	  lrng_jent.jitterrng for the Jitter RNG entropy source, and
+	  lrng_sw_noise.irq_entropy for the interrupt entropy source.
+
+config LRNG_RUNTIME_MAX_WO_RESEED_CONFIG
+	bool "Enable runtime configuration of max reseed threshold"
+	help
+	  When enabling this option, the LRNG provides an interface
+	  allowing the setting of the maximum number of DRNG generate
+	  operations without a reseed that has full entropy. The
+	  interface is lrng_drng.max_wo_reseed.
+
+config LRNG_TEST_CPU_ES_COMPRESSION
+	bool "Force CPU ES compression operation"
+	help
+	  When enabling this option, the CPU ES compression operation
+	  is forced by setting an arbitrary value > 1 for the data
+	  multiplier even when the CPU ES would deliver full entropy.
+	  This allows testing of the compression operation. It
+	  therefore forces to pull more data from the CPU ES
+	  than what may be required.
+
+config LRNG_TESTING
+	bool
+	default y if (LRNG_RAW_HIRES_ENTROPY || LRNG_RAW_JIFFIES_ENTROPY ||LRNG_RAW_IRQ_ENTROPY || LRNG_RAW_IRQFLAGS_ENTROPY || LRNG_RAW_RETIP_ENTROPY || LRNG_RAW_REGS_ENTROPY || LRNG_RAW_ARRAY || LRNG_IRQ_PERF || LRNG_ACVT_HASH)
+
+endif #LRNG_TESTING_MENU
+
 endif # LRNG

index f868f9fe53a6..6d5035aa611e 100644
@@ -17,3 +17,4 @@ obj-$(CONFIG_LRNG_DRBG)		+= lrng_drbg.o
 obj-$(CONFIG_LRNG_KCAPI)	+= lrng_kcapi.o
 obj-$(CONFIG_LRNG_JENT)		+= lrng_es_jent.o
 obj-$(CONFIG_LRNG_HEALTH_TESTS)	+= lrng_health.o
+obj-$(CONFIG_LRNG_TESTING)	+= lrng_testing.o

2.31.1

Parts of the LRNG are already covered by self-tests, including:

* Self-test of SP800-90A DRBG provided by the Linux kernel crypto API.

* Self-test of the PRNG provided by the Linux kernel crypto API.

* Raw noise source data testing including SP800-90B compliant tests when enabling CONFIG_LRNG_HEALTH_TESTS

This patch adds the self-tests for the remaining critical functions of the LRNG that are essential to maintain entropy and provide cryptographic strong random numbers. The following self-tests are implemented:

* Self-test of the time array maintenance. This test verifies whether the time stamp array management to store multiple values in one integer implements a concatenation of the data.

* Self-test of the software hash implementation ensures that this function operates compliant to the FIPS 180-4 specification. The self-test performs a hash operation of a zeroized per-CPU data array.

* Self-test of the ChaCha20 DRNG is based on the self-tests that are already present and implemented with the stand-alone user space ChaCha20 DRNG implementation available at [1]. The self-tests cover different use cases of the DRNG seeded with known seed data.

The status of the LRNG self-tests is provided with the selftest_status SysFS file. If the file contains a zero, the self-tests passed. The value 0xffffffff means that the self-tests were not executed. Any other value indicates a self-test failure.

The self-test may be compiled to panic the system if the self-test fails.

All self-tests operate on private state data structures. This implies that none of the self-tests have any impact on the regular LRNG operations. This allows the self-tests to be repeated at runtime by writing anything into the selftest_status SysFS file.

[1] https://www.chronox.de/chacha20.html