/dev/random - a new approach with full SP800-90B compliance

Hi,

The following patch set provides a different approach to /dev/random which is called Linux Random Number Generator (LRNG) to collect entropy within the Linux kernel. The main improvements compared to the existing /dev/random is to provide sufficient entropy during boot time as well as in virtual environments and when using SSDs. A secondary design goal is to limit the impact of the entropy collection on massive parallel systems and also allow the use accelerated cryptographic primitives. Also, all steps of the entropic data processing are testable.

The LRNG patch set allows a user to select use of the existing /dev/random or the LRNG during compile time. As the LRNG provides API and ABI compatible interfaces to the existing /dev/random implementation, the user can freely chose the RNG implementation without affecting kernel or user space operations.

This patch set provides early boot-time entropy which implies that no additional flags to the getrandom(2) system call discussed recently on the LKML is considered to be necessary. Yet, if additional flags are introduced to cover special hardware, the LRNG implementation will also provide them to be fully ABI and API compliant as already discussed on LKML.

The LRNG is fully compliant to SP800-90B requirements and is shipped with a full SP800-90B assessment and all required test tools. The existing /dev/random implementation on the other hand has architectural limitations which does not easily allow to bring the implementation in compliance with SP800-90B. The key statement that causes concern is SP800-90B section 3.1.6. This section denies crediting entropy to multiple similar noise sources. This section explicitly references different noise sources resting on the timing of events and their derivatives (i.e. it is a direct complaint to the existing existing /dev/random implementation). Therefore, SP800-90B now denies the very issue mentioned in [1] with the existing /dev/random implementation for a long time: crediting entropy to interrupts as well as crediting entropy to derivatives of interrupts (HID and disk events). This is not permissible with SP800-90B.

SP800-90B specifies various requirements for the noise source(s) that seed any DRNG including SP800-90A DRBGs. In about a year from now, SP800-90B will be mandated for all noise sources that provide entropy to DRBGs as part of a FIPS 140-[2|3] validation or other evaluation types. That means, if we there are no solutions to comply with the requirements of SP800-90B found till one year from now, any random number generation and ciphers based on random numbers on Linux will be considered and treated as not applicable and delivering no entropy! As /dev/urandom, getrandom(2) and /dev/random are the most common and prevalent noise sources for DRNGs, all these DRNGs are affected. This applies across the board for all validations of cryptography executing on Linux (kernel and user space modules).

For users that are not interested in SP800-90B, the entire code for the compliance as well as test interfaces can be deselected at compile time.

The design and implementation is driven by a set of goals described in [1] that the LRNG completely implements. Furthermore, [1] includes the full assessment of the SP800-90B compliance as well as a comparison with RNG design suggestions of SP800-90C, and AIS20/31.

The LRNG provides a complete separation of the noise source maintenance and the collection of entropy into an entropy pool from the post-processing using a pseudo-random number generator. Different DRNGs are supported, including:

* The LRNG can be compile-time enabled to replace the existing /dev/random implementation. When not selecting the LRNG at compile time (default), the existing /dev/random implementation is built.

* Built-in ChaCha20 DRNG which has no dependency to other kernel frameworks.

* SP800-90A DRBG using the kernel crypto API including its accelerated raw cipher implementations. This implies that the output of /dev/random, getrandom(2), /dev/urandom or get_random_bytes is fully compliant to SP800-90A.

* Arbitrary DRNGs registered with the kernel crypto API

* Full compliance with SP800-90B which covers the startup and runtime health tests mandated by SP800-90B as well as providing the test tools and test interfaces to obtain raw noise data securely. The test tools are provided at [1].

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

The LRNG has a flexible design by allowing an easy replacement of the deterministic random number generator component.

Compared to the existing /dev/random implementation, the compiled binary is smaller when the LRNG is compiled with all options equal to the existing /dev/random (i.e. only CONFIG_LRNG is set): random.o is 52.5 kBytes whereas all LRNG object files are in 49 kBytes in size. The fully SP800-90A/SP800-90B compliant binary code (CONFIG_LRNG, CONFIG_LRNG_DRNG_SWITCH, CONFIG_LRNG_DRBG, CONFIG_LRNG_HEALTH_TESTS) uses some 61 kBytes. In addition, the LRNG is about 50% faster in the performance critical interrupt handler code path compared to the existing /dev/random implementation.

Full SP800-90B testing 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

[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

Changes (compared to the previous patch set):

* Use of SHA-256 for hashing the entropy pool per default to ensure the LRNG can be claimed to manage 256 bits of entropy pursuant to SP800-90B (note, the required CONFIG_CRYPTO_LIB_SHA256 current depends on CONFIG_CRYPTO due to artificial Kconfig settings - technically CONFIG_CRYPTO_LIB_SHA256 could be compiled without CONFIG_CRYPTO)

* When using CTR DRBG, use SHA-256 for hashing entropy pool instead of CMAC AES to fully comply with SP800-90B to the letter of the law

* Correctly use CONFIG_BASE_SMALL in C code

* speed up add_interrupt_randomness if high-resolution time stamp is not available

* integrate patch a2541dcb51127dc31934ab93bc99ae7df458e41b

* integrate patch f227e3ec3b5cad859ad15666874405e8c1bbc1d4 and ensure that its associated design concerns documented in [2] section 2.2.5 are addressed

* add test interfaces for Jiffies, interrupt numbers, interrupt flags, and return instruction pointer supporting integration of patch f227e3ec3b5cad859ad15666874405e8c1bbc1d4 and systems with a missing high-resolution timer

As a side node: With the switchable DRNG support offered in this patch set, the following areas could be removed. As the existing /dev/random has no support for switchable DRNGs, however, this is not yet feasible though.

* remove lrng_ready_list and all code around it in lrng_interfaces.c

* remove the kernel crypto API RNG API to avoid having two random number providing APIs - this would imply that all RNGs developed for this API would be converted to the LRNG interface

Stephan Mueller (12):
Linux Random Number Generator
LRNG - allocate one DRNG instance per NUMA node LRNG - sysctls and /proc interface
LRNG - add switchable DRNG support
crypto: DRBG - externalize DRBG functions for LRNG LRNG - add SP800-90A DRBG extension
LRNG - add kernel crypto API PRNG extension
crypto: provide access to a static Jitter RNG state 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                        |  31 +-
 drivers/char/Kconfig                          |   2 +
 drivers/char/Makefile                         |   9 +-
 drivers/char/lrng/Kconfig                     | 315 +++++++++
 drivers/char/lrng/Makefile                    |  19 +
 drivers/char/lrng/lrng_archrandom.c           |  93 +++
 drivers/char/lrng/lrng_aux.c                  | 136 ++++
 drivers/char/lrng/lrng_chacha20.c             | 320 +++++++++
 drivers/char/lrng/lrng_chacha20.h             |  29 +
 drivers/char/lrng/lrng_drbg.c                 | 259 +++++++
 drivers/char/lrng/lrng_drng.c                 | 409 +++++++++++
 drivers/char/lrng/lrng_health.c               | 407 +++++++++++
 drivers/char/lrng/lrng_interfaces.c           | 647 ++++++++++++++++++
 drivers/char/lrng/lrng_internal.h             | 342 +++++++++
 drivers/char/lrng/lrng_jent.c                 |  88 +++
 drivers/char/lrng/lrng_kcapi.c                | 321 +++++++++
 drivers/char/lrng/lrng_lfsr.h                 | 152 ++++
 drivers/char/lrng/lrng_numa.c                 | 101 +++
 drivers/char/lrng/lrng_pool.c                 | 589 ++++++++++++++++
 drivers/char/lrng/lrng_proc.c                 | 163 +++++
 drivers/char/lrng/lrng_selftest.c             | 504 ++++++++++++++
 drivers/char/lrng/lrng_sw_noise.c             | 155 +++++
 drivers/char/lrng/lrng_sw_noise.h             |  57 ++
 drivers/char/lrng/lrng_switch.c               | 189 +++++
 drivers/char/lrng/lrng_testing.c              | 575 ++++++++++++++++
 include/crypto/drbg.h                         |   7 +
 .../crypto/internal}/jitterentropy.h          |   3 +
 include/linux/lrng.h                          |  63 ++
 31 files changed, 6001 insertions(+), 10 deletions(-)
 create mode 100644 drivers/char/lrng/Kconfig
 create mode 100644 drivers/char/lrng/Makefile
 create mode 100644 drivers/char/lrng/lrng_archrandom.c
 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_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_jent.c
 create mode 100644 drivers/char/lrng/lrng_kcapi.c
 create mode 100644 drivers/char/lrng/lrng_lfsr.h
 create mode 100644 drivers/char/lrng/lrng_numa.c
 create mode 100644 drivers/char/lrng/lrng_pool.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_sw_noise.c
 create mode 100644 drivers/char/lrng/lrng_sw_noise.h
 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 (84%)
 create mode 100644 include/linux/lrng.h

2.26.2

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

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

1. The LRNG implements a DRNG. The DRNG always generates the requested amount of output. When using the SP800-90A terminology it operates without prediction resistance. The secondary DRNG maintains a counter of how many bytes were generated since last re-seed and a timer of the elapsed time since last re-seed. If either the counter or the timer reaches a threshold, the secondary DRNG is seeded from the entropy pool.

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

2. The DRNG is seeded by concatenating the data from the following sources:

(a) the output of the entropy pool,

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

(c) the CPU-based noise source such as Intel RDRAND if available and enabled.

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

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

(a) During boot time, the amount of received interrupts are the trigger points to (re)seed the DRNG.

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

3. The entropy pool accumulates entropy obtained from certain events, which will henceforth be collectively called "slow noise sources". The entropy pool collects noise data from slow noise sources. Any data received by the LRNG from the slow noise sources is inserted into the entropy pool using an LFSR with a primitive and irreducible polynomial. The following sources of entropy are used:

(a) When an interrupt occurs, the high-resolution time stamp is mixed
into the LFSR. 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 LFSR. This data is not credited with entropy by the LRNG.

(c) Device drivers may provide data that is mixed into the LFSR. This
data is not credited with entropy by the LRNG.

(d) After the entropy pool is ``read'' by the DRNG, the data
used to seed the DRNG is mixed back into the entropy pool to stir the pool. This data is not credited with entropy by the LRNG.

Any data provided from user space by either writing to /dev/random, /dev/urandom or the IOCTL of RNDADDENTROPY on both device files are always injected into the entropy pool.

In addition, when a hardware random number generator covered by the Linux kernel HW generator framework wants to deliver random numbers, it is injected into the entropy 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 the DRNG requires data from the entropy pool, the entire entropy pool is processed with an SP800-90A section 10.3.1 compliant hash_df function to generate random numbers.

To speed up the interrupt handling code of the LRNG, the time stamp collected for an interrupt event is truncated to the 8 least significant bits. 64 truncated time stamps are concatenated and then jointly inserted into the LFSR. During boot time, until the fully seeded stage is reached, each time stamp with its 32 least significant bits is inserted into the LFSR at the time of arrival.

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. LFSR: The 8 least significant bits of the time stamp data received from the interrupts are processed with an LFSR. That LFSR is implemented identically to the LSFR used in the existing /dev/random implementation except that it is capable of processing an entire word and that a different polynomial is used. The reason for the different polynomial is performance in a performance sensitive code section, the interrupt handler. The chosen polynomials have 4 taps. Also, this LFSR-approach is used in the OpenBSD /dev/random equivalent.

2. Concatenation: The temporary seed buffer used to seed the DRNG is a concatenation of parts of the entropy pool data, and the CPU noise source output.

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 pool and potentially the fast noise sources if the entropy pool has collected at least 32 bits of entropy from the interrupt noise source. The goal of this step is to ensure that the DRNG receives some initial entropy as early as possible. In addition it receives the entropy available from the fast noise sources.

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

3. The DRNG is reseeded from the entropy pool and potentially the fast noise sources if all noise sources collectivel 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.

In all listed steps, the DRNG is (re)seeded with a number of random bytes from the entropy pool that is at most the amount of entropy present in the entropy pool. This means that when the entropy pool contains 128 or 256 bits of entropy, the DRNG is seeded with that amount of entropy as well.

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

The hash_df operation providing random data from the entropy pool will always require that all entropy sources collectively can deliver at least 129 entropy bits as configured with (128 bits of entropy for seeding plus one bit of entropy that is lost with the post processing as defined in SP800-90B).

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 secondary DRNG is reseeded with whatever entropy is available – in the worst case where no additional entropy can be provided by the noise 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 secondary DRNG is more than 600 seconds ago, or

- 2^20 DRNG generate operations are performed, whatever comes first, or

- the secondary DRNG is forced to reseed before the next generation of random numbers if data has been injected into the LRNG by writing data into /dev/random or /dev/urandom.

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

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.

The LRNG uses the following runtime memory using the currently smallest configuration:

* 576 bytes (512 bytes for the entropy pool and 64 for the entropy pool meta data) for the entropy pool management

* 64 bytes per CPU for the time stamp array

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

The entropy pool has support for sizes of 256, 128 and 64 bytes supported by primitive and irreducible polynomials.

The time stamp array is reduced to one atomic_t variable per CPU, i.e. 4 bytes when CONFIG_BASE_SMALL is selected during kernel configuration. This implies that after the receipt of 4 interrupts on one CPU, the data is injected into the LFSR. Depending on the behavior of the CPU caches, this may imply that the average interrupt handler execution time increases a bit, since instead of injecting 8 atomic_t values at one given time into the LFSR, only one is processed which may incur cache misses.

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 executes within an average of 65 cycles whereas the existing /dev/random on the same device takes about 97 cycles when measuring the execution time of add_interrupt_randomness().

* lockless LFSR to collect raw entropy supporing concurrency-free use of massive parallel systems

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

* "atomic" seeding of secondary DRBG to ensure full entropy transport

* instantiate one DRNG per NUMA node

* support for runtime switchable output DRNGs

* use of only well-defined entropy-preserving operations to collect, compress and forward entropy: concatenation, LFSR, SP800-90A hash_df function

* compile-time selectable entropy pool size: the choice also uses the applicable LFSR polynomial to maintain the entropy pool 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.

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

CC: "Eric W. Biederman" <[email protected]>
CC: "Alexander E. Patrakov" <[email protected]>
CC: "Ahmed S. Darwish" <[email protected]>
CC: "Theodore Y. Ts'o" <[email protected]>
CC: Willy Tarreau <[email protected]>
CC: Matthew Garrett <[email protected]>
CC: Vito Caputo <[email protected]>
CC: Andreas Dilger <[email protected]>
CC: Jan Kara <[email protected]>
CC: Ray Strode <[email protected]>
CC: William Jon McCann <[email protected]>
CC: zhangjs <[email protected]>
CC: Andy Lutomirski <[email protected]>
CC: Florian Weimer <[email protected]>
CC: Lennart Poettering <[email protected]>
CC: Nicolai Stange <[email protected]>
Mathematical aspects Reviewed-by: "Peter, Matthias" <[email protected]>

---
 MAINTAINERS                         |   7 +
 drivers/char/Kconfig                |   2 +
 drivers/char/Makefile               |   9 +-
 drivers/char/lrng/Kconfig           |  68 +++
 drivers/char/lrng/Makefile          |   9 +
 drivers/char/lrng/lrng_archrandom.c |  93 ++++
 drivers/char/lrng/lrng_aux.c        | 136 ++++++
 drivers/char/lrng/lrng_chacha20.c   | 320 ++++++++++++++
 drivers/char/lrng/lrng_chacha20.h   |  29 ++
 drivers/char/lrng/lrng_drng.c       | 409 ++++++++++++++++++
 drivers/char/lrng/lrng_interfaces.c | 648 ++++++++++++++++++++++++++++
 drivers/char/lrng/lrng_internal.h   | 333 ++++++++++++++
 drivers/char/lrng/lrng_lfsr.h       | 152 +++++++
 drivers/char/lrng/lrng_pool.c       | 589 +++++++++++++++++++++++++
 drivers/char/lrng/lrng_sw_noise.c   | 155 +++++++
 drivers/char/lrng/lrng_sw_noise.h   |  57 +++
 include/linux/lrng.h                |  63 +++
 17 files changed, 3078 insertions(+), 1 deletion(-)
 create mode 100644 drivers/char/lrng/Kconfig
 create mode 100644 drivers/char/lrng/Makefile
 create mode 100644 drivers/char/lrng/lrng_archrandom.c
 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_interfaces.c
 create mode 100644 drivers/char/lrng/lrng_internal.h
 create mode 100644 drivers/char/lrng/lrng_lfsr.h
 create mode 100644 drivers/char/lrng/lrng_pool.c
 create mode 100644 drivers/char/lrng/lrng_sw_noise.c
 create mode 100644 drivers/char/lrng/lrng_sw_noise.h
 create mode 100644 include/linux/lrng.h

index deaafb617361..74f6fd1ba1ec 100644
@@ -10084,6 +10084,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 b1bd336761b1..8a5b8a2db2c7 100644
@@ -470,6 +470,8 @@ config ADI
 	  and SSM (Silicon Secured Memory).  Intended consumers of this
 	  driver include crash and makedumpfile.
 
+source "drivers/char/lrng/Kconfig"
+
 endmenu
 
 config RANDOM_TRUST_CPU

index ffce287ef415..2110d3e28cf2 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..1d2a0211973d
@@ -0,0 +1,9 @@
+# SPDX-License-Identifier: GPL-2.0
+#
+# Makefile for the Linux Random Number Generator.
+#
+
+obj-y				+= lrng_pool.o lrng_aux.o \
+				   lrng_sw_noise.o lrng_archrandom.o \
+				   lrng_drng.o lrng_chacha20.o \
+				   lrng_interfaces.o \

new file mode 100644
index 000000000000..1533b2490964
@@ -0,0 +1,29 @@
+/* SPDX-License-Identifier: GPL-2.0 OR BSD-2-Clause */
+/*
+ * LRNG ChaCha20 definitions
+ *
+ * Copyright (C) 2016 - 2020, 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 __latent_entropy;
+	u32 counter;
+	u32 nonce[3] __latent_entropy;
+};
+
+static inline void lrng_cc20_init_rfc7539(struct chacha20_block *chacha20)
+{
+	/* String "expand 32-byte k" */
+	chacha20->constants[0] = 0x61707865;
+	chacha20->constants[1] = 0x3320646e;
+	chacha20->constants[2] = 0x79622d32;
+	chacha20->constants[3] = 0x6b206574;
+}

2.26.2

Part of the diff is not shown here. View the raw message.

Am Donnerstag, 20. August 2020, 13:46:49 CEST schrieb kernel test robot:

Hi,

Thank you, added <linux/hw_random.h>

Thanks, added prototype to header file.

Ciao
Stephan

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        |   2 +
 drivers/char/lrng/lrng_internal.h |   5 ++
 drivers/char/lrng/lrng_numa.c     | 101 ++++++++++++++++++++++++++++++
 3 files changed, 108 insertions(+)
 create mode 100644 drivers/char/lrng/lrng_numa.c

index 1d2a0211973d..0a32f22c2c1a 100644
@@ -7,3 +7,5 @@ obj-y				+= lrng_pool.o lrng_aux.o \
 				   lrng_sw_noise.o lrng_archrandom.o \
 				   lrng_drng.o lrng_chacha20.o \
 				   lrng_interfaces.o \
+
+obj-$(CONFIG_NUMA)		+= lrng_numa.o

index f6a5f0d960c1..495e00ae5ee1 100644
@@ -247,8 +247,13 @@ int lrng_drng_get_sleep(u8 *outbuf, u32 outbuflen);
 void lrng_drng_force_reseed(void);
 void lrng_drng_seed_work(struct work_struct *dummy);
 
+#ifdef CONFIG_NUMA
+struct lrng_drng **lrng_drng_instances(void);
+void lrng_drngs_numa_alloc(void);
+#else	/* CONFIG_NUMA */
 static inline struct lrng_drng **lrng_drng_instances(void) { return NULL; }
 static inline void lrng_drngs_numa_alloc(void) { return; }
+#endif /* CONFIG_NUMA */
 
 /************************** Health Test linking code **************************/
 

2.26.2

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 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 |   1 -
 drivers/char/lrng/lrng_internal.h   |   4 +
 drivers/char/lrng/lrng_proc.c       | 163 ++++++++++++++++++++++++++++
 4 files changed, 168 insertions(+), 1 deletion(-)
 create mode 100644 drivers/char/lrng/lrng_proc.c

index 0a32f22c2c1a..e69c176f0161 100644
@@ -9,3 +9,4 @@ obj-y				+= lrng_pool.o lrng_aux.o \
 				   lrng_interfaces.o \
 
 obj-$(CONFIG_NUMA)		+= lrng_numa.o
+obj-$(CONFIG_SYSCTL)		+= lrng_proc.o

index 7fc04e54d834..184108b6e1cb 100644
@@ -34,7 +34,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? */

index 495e00ae5ee1..a52c4cf367e2 100644
@@ -117,7 +117,11 @@ void lrng_cc20_init_state_boot(struct chacha20_state *state);
 
 /********************************** /proc *************************************/
 
+#ifdef CONFIG_SYSCTL
+void lrng_pool_inc_numa_node(void);
+#else
 static inline void lrng_pool_inc_numa_node(void) { }
+#endif
 
 /****************************** LRNG interfaces *******************************/
 

2.26.2

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.

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

index 059b21d9728c..d3138458fd8b 100644
@@ -65,4 +65,11 @@ config LRNG_POOL_SIZE
 	default 7 if LRNG_POOL_SIZE_65536
 	default 8 if LRNG_POOL_SIZE_131072
 
+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 e69c176f0161..31cfe87c999e 100644
@@ -10,3 +10,4 @@ obj-y				+= lrng_pool.o lrng_aux.o \
 
 obj-$(CONFIG_NUMA)		+= lrng_numa.o
 obj-$(CONFIG_SYSCTL)		+= lrng_proc.o
+obj-$(CONFIG_LRNG_DRNG_SWITCH)	+= lrng_switch.o

2.26.2

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 e99fe34cfa00..3644e954785a 100644
@@ -113,7 +113,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,

@@ -190,6 +190,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);
 

@@ -205,7 +206,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:

@@ -218,6 +219,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

@@ -1214,7 +1216,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;

@@ -1235,12 +1237,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;

@@ -1321,6 +1324,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

@@ -1890,8 +1894,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;

@@ -1918,6 +1921,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.26.2

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     |  12 ++
 drivers/char/lrng/Makefile    |   1 +
 drivers/char/lrng/lrng_drbg.c | 259 ++++++++++++++++++++++++++++++++++
 3 files changed, 272 insertions(+)
 create mode 100644 drivers/char/lrng/lrng_drbg.c

index d3138458fd8b..4ad26fdfbe7e 100644
@@ -72,4 +72,16 @@ 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_DRBG
+	tristate "SP800-90A support for the LRNG"
+	depends on CRYPTO
+	select CRYPTO_DRBG_MENU
+	select CRYPTO_SHA512
+	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 is provided by a DRBG.
+endif # LRNG_DRNG_SWITCH
+
 endif # LRNG

index 31cfe87c999e..0d320fcb7b9e 100644
@@ -11,3 +11,4 @@ obj-y				+= lrng_pool.o lrng_aux.o \
 obj-$(CONFIG_NUMA)		+= lrng_numa.o
 obj-$(CONFIG_SYSCTL)		+= lrng_proc.o
 obj-$(CONFIG_LRNG_DRNG_SWITCH)	+= lrng_switch.o
+obj-$(CONFIG_LRNG_DRBG)		+= lrng_drbg.o

2.26.2

Am Donnerstag, 20. August 2020, 14:07:40 CEST schrieb kernel test robot:

Hi,

Thanks, I will provide a new patch set with the two keywords switched.

Ciao
Stephan

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      |  11 ++
 drivers/char/lrng/Makefile     |   1 +
 drivers/char/lrng/lrng_kcapi.c | 321 +++++++++++++++++++++++++++++++++
 3 files changed, 333 insertions(+)
 create mode 100644 drivers/char/lrng/lrng_kcapi.c

index 4ad26fdfbe7e..ba3d84cd0676 100644
@@ -82,6 +82,17 @@ 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 is provided by a DRBG.
+
+config LRNG_KCAPI
+	tristate "Kernel Crypto API support for the LRNG"
+	depends on CRYPTO
+	select CRYPTO_RNG
+	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 0d320fcb7b9e..94b2dfb2dfdb 100644
@@ -12,3 +12,4 @@ obj-$(CONFIG_NUMA)		+= lrng_numa.o
 obj-$(CONFIG_SYSCTL)		+= lrng_proc.o
 obj-$(CONFIG_LRNG_DRNG_SWITCH)	+= lrng_switch.o
 obj-$(CONFIG_LRNG_DRBG)		+= lrng_drbg.o
+obj-$(CONFIG_LRNG_KCAPI)	+= lrng_kcapi.o

2.26.2

To support the LRNG operation which uses the Jitter RNG separately from the kernel crypto API, at a time where potentially the regular memory management is not yet initialized, the Jitter RNG needs to provide a state whose memory is defined at compile time. As only once instance will ever be needed by the LRNG, define once static memory block which is solely to be used by the LRNG.

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

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

index 6e147c43fc18..fa1459f09b01 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

@@ -854,3 +854,32 @@ int jent_entropy_init(void)
 
 	return 0;
 }
+
+struct rand_data *jent_lrng_entropy_collector(void)
+{
+	static unsigned char lrng_jent_mem[JENT_MEMORY_SIZE];
+	static struct rand_data lrng_jent_state = {
+		.data		= 0,
+		.old_data	= 0,
+		.prev_time	= 0,
+		.last_delta	= 0,
+		.last_delta2	= 0,
+		.osr		= 1,
+		.mem		= lrng_jent_mem,
+		.memlocation	= 0,
+		.memblocks	= JENT_MEMORY_BLOCKSIZE,
+		.memblocksize	= JENT_MEMORY_BLOCKS,
+		.memaccessloops	= JENT_MEMORY_ACCESSLOOPS,
+		.rct_count	= 0,
+		.apt_observations = 0,
+		.apt_count	= 0,
+		.apt_base	= 0,
+		.apt_base_set	= 0,
+		.health_failure = 0
+	};
+
+	if (jent_entropy_init())
+		return NULL;
+
+	return &lrng_jent_state;
+}

similarity index 84%
rename from crypto/jitterentropy.h
rename to include/crypto/internal/jitterentropy.h
index c83fff32d130..6e07d86eac82 100644
@@ -15,3 +15,6 @@ extern int jent_read_entropy(struct rand_data *ec, unsigned char *data,
 extern struct rand_data *jent_entropy_collector_alloc(unsigned int osr,
 						      unsigned int flags);
 extern void jent_entropy_collector_free(struct rand_data *entropy_collector);
+
+/* Access to statically allocated Jitter RNG instance */
+extern struct rand_data *jent_lrng_entropy_collector(void);

2.26.2

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     | 12 +++++
 drivers/char/lrng/Makefile    |  1 +
 drivers/char/lrng/lrng_jent.c | 88 +++++++++++++++++++++++++++++++++++
 3 files changed, 101 insertions(+)
 create mode 100644 drivers/char/lrng/lrng_jent.c

index ba3d84cd0676..66a775a8f912 100644
@@ -95,4 +95,16 @@ config LRNG_KCAPI
 	  provided by the selected kernel crypto API RNG.
 endif # LRNG_DRNG_SWITCH
 
+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.
+
 endif # LRNG

index 94b2dfb2dfdb..4f5b6f38f0c4 100644
@@ -13,3 +13,4 @@ obj-$(CONFIG_SYSCTL)		+= lrng_proc.o
 obj-$(CONFIG_LRNG_DRNG_SWITCH)	+= lrng_switch.o
 obj-$(CONFIG_LRNG_DRBG)		+= lrng_drbg.o
 obj-$(CONFIG_LRNG_KCAPI)	+= lrng_kcapi.o
+obj-$(CONFIG_LRNG_JENT)		+= lrng_jent.o

2.26.2

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 LFSR. 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       |  56 +++++
 drivers/char/lrng/Makefile      |   1 +
 drivers/char/lrng/lrng_health.c | 407 ++++++++++++++++++++++++++++++++
 3 files changed, 464 insertions(+)
 create mode 100644 drivers/char/lrng/lrng_health.c

index 66a775a8f912..70eee0f43d8c 100644
@@ -107,4 +107,60 @@ config LRNG_JENT
 	  time or at runtime with the lrng_base.jitterrng configuration
 	  variable.
 
+config LRNG_HEALTH_TESTS
+	bool "Enable noise source online health tests"
+	help
+	  The online health tests 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 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 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 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
+
 endif # LRNG

index 4f5b6f38f0c4..c3008763dd14 100644
@@ -14,3 +14,4 @@ obj-$(CONFIG_LRNG_DRNG_SWITCH)	+= lrng_switch.o
 obj-$(CONFIG_LRNG_DRBG)		+= lrng_drbg.o
 obj-$(CONFIG_LRNG_KCAPI)	+= lrng_kcapi.o
 obj-$(CONFIG_LRNG_JENT)		+= lrng_jent.o
+obj-$(CONFIG_LRNG_HEALTH_TESTS)	+= lrng_health.o

2.26.2

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 conatenated 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

* array logic batching the high-resolution time stamp

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        | 124 +++++++
 drivers/char/lrng/Makefile       |   1 +
 drivers/char/lrng/lrng_testing.c | 575 +++++++++++++++++++++++++++++++
 3 files changed, 700 insertions(+)
 create mode 100644 drivers/char/lrng/lrng_testing.c

index 70eee0f43d8c..5d2f44d07581 100644
@@ -163,4 +163,128 @@ config LRNG_APT_CUTOFF
 	default 325 if !LRNG_APT_BROKEN
 	default 32 if LRNG_APT_BROKEN
 
+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_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_TESTING
+	bool
+	default y if (LRNG_RAW_ENTROPY || LRNG_RAW_ARRAY || LRNG_IRQ_PERF)
+
+endif #LRNG_TESTING_MENU
+
 endif # LRNG

index c3008763dd14..b2ce1979dc4b 100644
@@ -15,3 +15,4 @@ obj-$(CONFIG_LRNG_DRBG)		+= lrng_drbg.o
 obj-$(CONFIG_LRNG_KCAPI)	+= lrng_kcapi.o
 obj-$(CONFIG_LRNG_JENT)		+= lrng_jent.o
 obj-$(CONFIG_LRNG_HEALTH_TESTS)	+= lrng_health.o
+obj-$(CONFIG_LRNG_TESTING)	+= lrng_testing.o

2.26.2

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 LFSR operation. This test injects a monotonic increasing counter into the LFSR. After completion of the injection of the counter, 3 pool words are compared with known good values. The known good values are calculated with the newly-developed tool lfsr_testvector_generation provided as part of the LRNG test tool set at [1].

* Self-test of the Hash_DF operation ensures that this function operates compliant to the specification. The self-test performs a Hash_DF operation of a zeroized entropy pool state. The test vectors are generated using the newly-developed tool hash_df_testvector_generation provided as part of the LRNG test tool set at [1].

* 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 [2]. 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/lrng.html
[2] https://www.chronox.de/chacha20.html

---
 drivers/char/lrng/Kconfig         |  25 ++
 drivers/char/lrng/Makefile        |   1 +
 drivers/char/lrng/lrng_selftest.c | 504 ++++++++++++++++++++++++++++++
 3 files changed, 530 insertions(+)
 create mode 100644 drivers/char/lrng/lrng_selftest.c

index 5d2f44d07581..6930dddb5347 100644
@@ -287,4 +287,29 @@ config LRNG_TESTING
 
 endif #LRNG_TESTING_MENU
 
+config LRNG_SELFTEST
+	bool "Enable power-on and on-demand self-tests"
+	help
+	  The power-on self-tests are executed during boot time
+	  covering the ChaCha20 DRNG, the LFSR processing and the
+	  time stamp management of the LRNG.
+
+	  The on-demand self-tests are triggered by writing any
+	  value into the SysFS file selftest_status. At the same
+	  time, when reading this file, the test status is
+	  returned. A zero indicates that all tests were executed
+	  successfully.
+
+	  If unsure, say Y.
+
+if LRNG_SELFTEST
+
+config LRNG_SELFTEST_PANIC
+	bool "Panic the kernel upon self-test failure"
+	help
+	  If the option is enabled, the kernel is terminated if an
+	  LRNG power-on self-test failure is detected.
+
+endif # LRNG_SELFTEST
+
 endif # LRNG

index b2ce1979dc4b..92219c565f66 100644
@@ -16,3 +16,4 @@ obj-$(CONFIG_LRNG_KCAPI)	+= lrng_kcapi.o
 obj-$(CONFIG_LRNG_JENT)		+= lrng_jent.o
 obj-$(CONFIG_LRNG_HEALTH_TESTS)	+= lrng_health.o
 obj-$(CONFIG_LRNG_TESTING)	+= lrng_testing.o
+obj-$(CONFIG_LRNG_SELFTEST)	+= lrng_selftest.o

2.26.2

Hi,

The following patch set provides a different approach to /dev/random which is called Linux Random Number Generator (LRNG) to collect entropy within the Linux kernel. The main improvements compared to the existing /dev/random is to provide sufficient entropy during boot time as well as in virtual environments and when using SSDs. A secondary design goal is to limit the impact of the entropy collection on massive parallel systems and also allow the use accelerated cryptographic primitives. Also, all steps of the entropic data processing are testable.

The LRNG patch set allows a user to select use of the existing /dev/random or the LRNG during compile time. As the LRNG provides API and ABI compatible interfaces to the existing /dev/random implementation, the user can freely chose the RNG implementation without affecting kernel or user space operations.

This patch set provides early boot-time entropy which implies that no additional flags to the getrandom(2) system call discussed recently on the LKML is considered to be necessary. Yet, if additional flags are introduced to cover special hardware, the LRNG implementation will also provide them to be fully ABI and API compliant as already discussed on LKML.

The LRNG is fully compliant to SP800-90B requirements and is shipped with a full SP800-90B assessment and all required test tools. The existing /dev/random implementation on the other hand has architectural limitations which does not easily allow to bring the implementation in compliance with SP800-90B. The key statement that causes concern is SP800-90B section 3.1.6. This section denies crediting entropy to multiple similar noise sources. This section explicitly references different noise sources resting on the timing of events and their derivatives (i.e. it is a direct complaint to the existing existing /dev/random implementation). Therefore, SP800-90B now denies the very issue mentioned in [1] with the existing /dev/random implementation for a long time: crediting entropy to interrupts as well as crediting entropy to derivatives of interrupts (HID and disk events). This is not permissible with SP800-90B.

SP800-90B specifies various requirements for the noise source(s) that seed any DRNG including SP800-90A DRBGs. In about a year from now, SP800-90B will be mandated for all noise sources that provide entropy to DRBGs as part of a FIPS 140-[2|3] validation or other evaluation types. That means, if we there are no solutions to comply with the requirements of SP800-90B found till one year from now, any random number generation and ciphers based on random numbers on Linux will be considered and treated as not applicable and delivering no entropy! As /dev/urandom, getrandom(2) and /dev/random are the most common and prevalent noise sources for DRNGs, all these DRNGs are affected. This applies across the board for all validations of cryptography executing on Linux (kernel and user space modules).

For users that are not interested in SP800-90B, the entire code for the compliance as well as test interfaces can be deselected at compile time.

The design and implementation is driven by a set of goals described in [1] that the LRNG completely implements. Furthermore, [1] includes the full assessment of the SP800-90B compliance as well as a comparison with RNG design suggestions of SP800-90C, and AIS20/31.

The LRNG provides a complete separation of the noise source maintenance and the collection of entropy into an entropy pool from the post-processing using a pseudo-random number generator. Different DRNGs are supported, including:

* The LRNG can be compile-time enabled to replace the existing /dev/random implementation. When not selecting the LRNG at compile time (default), the existing /dev/random implementation is built.

* Built-in ChaCha20 DRNG which has no dependency to other kernel frameworks.

* SP800-90A DRBG using the kernel crypto API including its accelerated raw cipher implementations. This implies that the output of /dev/random, getrandom(2), /dev/urandom or get_random_bytes is fully compliant to SP800-90A.

* Arbitrary DRNGs registered with the kernel crypto API

* Full compliance with SP800-90B which covers the startup and runtime health tests mandated by SP800-90B as well as providing the test tools and test interfaces to obtain raw noise data securely. The test tools are provided at [1].

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

The LRNG has a flexible design by allowing an easy replacement of the deterministic random number generator component.

Compared to the existing /dev/random implementation, the compiled binary is smaller when the LRNG is compiled with all options equal to the existing /dev/random (i.e. only CONFIG_LRNG is set): random.o is 52.5 kBytes whereas all LRNG object files are in 49 kBytes in size. The fully SP800-90A/SP800-90B compliant binary code (CONFIG_LRNG, CONFIG_LRNG_DRNG_SWITCH, CONFIG_LRNG_DRBG, CONFIG_LRNG_HEALTH_TESTS) uses some 61 kBytes. In addition, the LRNG is about 50% faster in the performance critical interrupt handler code path compared to the existing /dev/random implementation.

Full SP800-90B testing 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

[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

Changes (compared to the previous patch set):

* fix const static -> static const as indicated by kernel test robot

* fix double initialization as indicated by kernel test robot

* add hw_random.h header file and add get_random_bytes_full prototypes as indicated by kernel test robot

* if -> ifdef for CONFIG_CRYPTO_LIB_SHA256 in lrng_selftest.c

* Note, the warning on random_table is expected as it is there to ensure patch 0001 can be compiled. This symbol is "fixed" with patch 0003.

As a side node: With the switchable DRNG support offered in this patch set, the following areas could be removed. As the existing /dev/random has no support for switchable DRNGs, however, this is not yet feasible though.

* remove lrng_ready_list and all code around it in lrng_interfaces.c

* remove the kernel crypto API RNG API to avoid having two random number providing APIs - this would imply that all RNGs developed for this API would be converted to the LRNG interface

Stephan Mueller (12):
Linux Random Number Generator
LRNG - allocate one DRNG instance per NUMA node LRNG - sysctls and /proc interface
LRNG - add switchable DRNG support
crypto: DRBG - externalize DRBG functions for LRNG LRNG - add SP800-90A DRBG extension
LRNG - add kernel crypto API PRNG extension
crypto: provide access to a static Jitter RNG state 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                        |  31 +-
 drivers/char/Kconfig                          |   2 +
 drivers/char/Makefile                         |   9 +-
 drivers/char/lrng/Kconfig                     | 315 +++++++++
 drivers/char/lrng/Makefile                    |  19 +
 drivers/char/lrng/lrng_archrandom.c           |  93 +++
 drivers/char/lrng/lrng_aux.c                  | 136 ++++
 drivers/char/lrng/lrng_chacha20.c             | 320 +++++++++
 drivers/char/lrng/lrng_chacha20.h             |  29 +
 drivers/char/lrng/lrng_drbg.c                 | 259 +++++++
 drivers/char/lrng/lrng_drng.c                 | 409 +++++++++++
 drivers/char/lrng/lrng_health.c               | 407 +++++++++++
 drivers/char/lrng/lrng_interfaces.c           | 648 ++++++++++++++++++
 drivers/char/lrng/lrng_internal.h             | 345 ++++++++++
 drivers/char/lrng/lrng_jent.c                 |  88 +++
 drivers/char/lrng/lrng_kcapi.c                | 321 +++++++++
 drivers/char/lrng/lrng_lfsr.h                 | 152 ++++
 drivers/char/lrng/lrng_numa.c                 | 101 +++
 drivers/char/lrng/lrng_pool.c                 | 589 ++++++++++++++++
 drivers/char/lrng/lrng_proc.c                 | 163 +++++
 drivers/char/lrng/lrng_selftest.c             | 504 ++++++++++++++
 drivers/char/lrng/lrng_sw_noise.c             | 155 +++++
 drivers/char/lrng/lrng_sw_noise.h             |  57 ++
 drivers/char/lrng/lrng_switch.c               | 189 +++++
 drivers/char/lrng/lrng_testing.c              | 575 ++++++++++++++++
 include/crypto/drbg.h                         |   7 +
 .../crypto/internal}/jitterentropy.h          |   3 +
 include/linux/lrng.h                          |  63 ++
 31 files changed, 6005 insertions(+), 10 deletions(-)
 create mode 100644 drivers/char/lrng/Kconfig
 create mode 100644 drivers/char/lrng/Makefile
 create mode 100644 drivers/char/lrng/lrng_archrandom.c
 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_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_jent.c
 create mode 100644 drivers/char/lrng/lrng_kcapi.c
 create mode 100644 drivers/char/lrng/lrng_lfsr.h
 create mode 100644 drivers/char/lrng/lrng_numa.c
 create mode 100644 drivers/char/lrng/lrng_pool.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_sw_noise.c
 create mode 100644 drivers/char/lrng/lrng_sw_noise.h
 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 (84%)
 create mode 100644 include/linux/lrng.h

2.26.2

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

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

1. The LRNG implements a DRNG. The DRNG always generates the requested amount of output. When using the SP800-90A terminology it operates without prediction resistance. The secondary DRNG maintains a counter of how many bytes were generated since last re-seed and a timer of the elapsed time since last re-seed. If either the counter or the timer reaches a threshold, the secondary DRNG is seeded from the entropy pool.

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

2. The DRNG is seeded by concatenating the data from the following sources:

(a) the output of the entropy pool,

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

(c) the CPU-based noise source such as Intel RDRAND if available and enabled.

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

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

(a) During boot time, the amount of received interrupts are the trigger points to (re)seed the DRNG.

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

3. The entropy pool accumulates entropy obtained from certain events, which will henceforth be collectively called "slow noise sources". The entropy pool collects noise data from slow noise sources. Any data received by the LRNG from the slow noise sources is inserted into the entropy pool using an LFSR with a primitive and irreducible polynomial. The following sources of entropy are used:

(a) When an interrupt occurs, the high-resolution time stamp is mixed
into the LFSR. 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 LFSR. This data is not credited with entropy by the LRNG.

(c) Device drivers may provide data that is mixed into the LFSR. This
data is not credited with entropy by the LRNG.

(d) After the entropy pool is ``read'' by the DRNG, the data
used to seed the DRNG is mixed back into the entropy pool to stir the pool. This data is not credited with entropy by the LRNG.

Any data provided from user space by either writing to /dev/random, /dev/urandom or the IOCTL of RNDADDENTROPY on both device files are always injected into the entropy pool.

In addition, when a hardware random number generator covered by the Linux kernel HW generator framework wants to deliver random numbers, it is injected into the entropy 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 the DRNG requires data from the entropy pool, the entire entropy pool is processed with an SP800-90A section 10.3.1 compliant hash_df function to generate random numbers.

To speed up the interrupt handling code of the LRNG, the time stamp collected for an interrupt event is truncated to the 8 least significant bits. 64 truncated time stamps are concatenated and then jointly inserted into the LFSR. During boot time, until the fully seeded stage is reached, each time stamp with its 32 least significant bits is inserted into the LFSR at the time of arrival.

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. LFSR: The 8 least significant bits of the time stamp data received from the interrupts are processed with an LFSR. That LFSR is implemented identically to the LSFR used in the existing /dev/random implementation except that it is capable of processing an entire word and that a different polynomial is used. The reason for the different polynomial is performance in a performance sensitive code section, the interrupt handler. The chosen polynomials have 4 taps. Also, this LFSR-approach is used in the OpenBSD /dev/random equivalent.

2. Concatenation: The temporary seed buffer used to seed the DRNG is a concatenation of parts of the entropy pool data, and the CPU noise source output.

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 pool and potentially the fast noise sources if the entropy pool has collected at least 32 bits of entropy from the interrupt noise source. The goal of this step is to ensure that the DRNG receives some initial entropy as early as possible. In addition it receives the entropy available from the fast noise sources.

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

3. The DRNG is reseeded from the entropy pool and potentially the fast noise sources if all noise sources collectivel 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.

In all listed steps, the DRNG is (re)seeded with a number of random bytes from the entropy pool that is at most the amount of entropy present in the entropy pool. This means that when the entropy pool contains 128 or 256 bits of entropy, the DRNG is seeded with that amount of entropy as well.

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

The hash_df operation providing random data from the entropy pool will always require that all entropy sources collectively can deliver at least 129 entropy bits as configured with (128 bits of entropy for seeding plus one bit of entropy that is lost with the post processing as defined in SP800-90B).

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 secondary DRNG is reseeded with whatever entropy is available – in the worst case where no additional entropy can be provided by the noise 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 secondary DRNG is more than 600 seconds ago, or

- 2^20 DRNG generate operations are performed, whatever comes first, or

- the secondary DRNG is forced to reseed before the next generation of random numbers if data has been injected into the LRNG by writing data into /dev/random or /dev/urandom.

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

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.

The LRNG uses the following runtime memory using the currently smallest configuration:

* 576 bytes (512 bytes for the entropy pool and 64 for the entropy pool meta data) for the entropy pool management

* 64 bytes per CPU for the time stamp array

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

The entropy pool has support for sizes of 256, 128 and 64 bytes supported by primitive and irreducible polynomials.

The time stamp array is reduced to one atomic_t variable per CPU, i.e. 4 bytes when CONFIG_BASE_SMALL is selected during kernel configuration. This implies that after the receipt of 4 interrupts on one CPU, the data is injected into the LFSR. Depending on the behavior of the CPU caches, this may imply that the average interrupt handler execution time increases a bit, since instead of injecting 8 atomic_t values at one given time into the LFSR, only one is processed which may incur cache misses.

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 executes within an average of 65 cycles whereas the existing /dev/random on the same device takes about 97 cycles when measuring the execution time of add_interrupt_randomness().

* lockless LFSR to collect raw entropy supporing concurrency-free use of massive parallel systems

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

* "atomic" seeding of secondary DRBG to ensure full entropy transport

* instantiate one DRNG per NUMA node

* support for runtime switchable output DRNGs

* use of only well-defined entropy-preserving operations to collect, compress and forward entropy: concatenation, LFSR, SP800-90A hash_df function

* compile-time selectable entropy pool size: the choice also uses the applicable LFSR polynomial to maintain the entropy pool 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.

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

CC: "Eric W. Biederman" <[email protected]>
CC: "Alexander E. Patrakov" <[email protected]>
CC: "Ahmed S. Darwish" <[email protected]>
CC: "Theodore Y. Ts'o" <[email protected]>
CC: Willy Tarreau <[email protected]>
CC: Matthew Garrett <[email protected]>
CC: Vito Caputo <[email protected]>
CC: Andreas Dilger <[email protected]>
CC: Jan Kara <[email protected]>
CC: Ray Strode <[email protected]>
CC: William Jon McCann <[email protected]>
CC: zhangjs <[email protected]>
CC: Andy Lutomirski <[email protected]>
CC: Florian Weimer <[email protected]>
CC: Lennart Poettering <[email protected]>
CC: Nicolai Stange <[email protected]>
Mathematical aspects Reviewed-by: "Peter, Matthias" <[email protected]>

---
 MAINTAINERS                         |   7 +
 drivers/char/Kconfig                |   2 +
 drivers/char/Makefile               |   9 +-
 drivers/char/lrng/Kconfig           |  68 +++
 drivers/char/lrng/Makefile          |   9 +
 drivers/char/lrng/lrng_archrandom.c |  93 ++++
 drivers/char/lrng/lrng_aux.c        | 136 ++++++
 drivers/char/lrng/lrng_chacha20.c   | 320 ++++++++++++++
 drivers/char/lrng/lrng_chacha20.h   |  29 ++
 drivers/char/lrng/lrng_drng.c       | 409 ++++++++++++++++++
 drivers/char/lrng/lrng_interfaces.c | 649 ++++++++++++++++++++++++++++
 drivers/char/lrng/lrng_internal.h   | 336 ++++++++++++++
 drivers/char/lrng/lrng_lfsr.h       | 152 +++++++
 drivers/char/lrng/lrng_pool.c       | 589 +++++++++++++++++++++++++
 drivers/char/lrng/lrng_sw_noise.c   | 155 +++++++
 drivers/char/lrng/lrng_sw_noise.h   |  57 +++
 include/linux/lrng.h                |  63 +++
 17 files changed, 3082 insertions(+), 1 deletion(-)
 create mode 100644 drivers/char/lrng/Kconfig
 create mode 100644 drivers/char/lrng/Makefile
 create mode 100644 drivers/char/lrng/lrng_archrandom.c
 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_interfaces.c
 create mode 100644 drivers/char/lrng/lrng_internal.h
 create mode 100644 drivers/char/lrng/lrng_lfsr.h
 create mode 100644 drivers/char/lrng/lrng_pool.c
 create mode 100644 drivers/char/lrng/lrng_sw_noise.c
 create mode 100644 drivers/char/lrng/lrng_sw_noise.h
 create mode 100644 include/linux/lrng.h

index deaafb617361..74f6fd1ba1ec 100644
@@ -10084,6 +10084,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 b1bd336761b1..8a5b8a2db2c7 100644
@@ -470,6 +470,8 @@ config ADI
 	  and SSM (Silicon Secured Memory).  Intended consumers of this
 	  driver include crash and makedumpfile.
 
+source "drivers/char/lrng/Kconfig"
+
 endmenu
 
 config RANDOM_TRUST_CPU

index ffce287ef415..2110d3e28cf2 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..1d2a0211973d
@@ -0,0 +1,9 @@
+# SPDX-License-Identifier: GPL-2.0
+#
+# Makefile for the Linux Random Number Generator.
+#
+
+obj-y				+= lrng_pool.o lrng_aux.o \
+				   lrng_sw_noise.o lrng_archrandom.o \
+				   lrng_drng.o lrng_chacha20.o \
+				   lrng_interfaces.o \

new file mode 100644
index 000000000000..1533b2490964
@@ -0,0 +1,29 @@
+/* SPDX-License-Identifier: GPL-2.0 OR BSD-2-Clause */
+/*
+ * LRNG ChaCha20 definitions
+ *
+ * Copyright (C) 2016 - 2020, 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 __latent_entropy;
+	u32 counter;
+	u32 nonce[3] __latent_entropy;
+};
+
+static inline void lrng_cc20_init_rfc7539(struct chacha20_block *chacha20)
+{
+	/* String "expand 32-byte k" */
+	chacha20->constants[0] = 0x61707865;
+	chacha20->constants[1] = 0x3320646e;
+	chacha20->constants[2] = 0x79622d32;
+	chacha20->constants[3] = 0x6b206574;
+}

2.26.2

Part of the diff is not shown here. View the raw message.

Am Freitag, 21. August 2020, 21:42:17 CEST schrieb kernel test robot:

Hi,

This is caused by the fact that the LRNG code does not include trace/events/ random.h. However, a patch to lib/random32.c now requires this file to be included and creating a tracepoint. I.e. lib/random32.c code now relies on some other code to create the necessary hook.

I have added the include and will provide it with the next release although I am not sure lib/random32.c should rely on some other code to create its dependencies.

Ciao
Stephan

Am Mittwoch, 26. August 2020, 16:27:42 CEST schrieb kernel test robot:

Hi,

Thanks for the reports. Both, the __poll_t and the __le32 issues are fixed in v34.

Ciao
Stephan

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        |   2 +
 drivers/char/lrng/lrng_internal.h |   5 ++
 drivers/char/lrng/lrng_numa.c     | 101 ++++++++++++++++++++++++++++++
 3 files changed, 108 insertions(+)
 create mode 100644 drivers/char/lrng/lrng_numa.c

index 1d2a0211973d..0a32f22c2c1a 100644
@@ -7,3 +7,5 @@ obj-y				+= lrng_pool.o lrng_aux.o \
 				   lrng_sw_noise.o lrng_archrandom.o \
 				   lrng_drng.o lrng_chacha20.o \
 				   lrng_interfaces.o \
+
+obj-$(CONFIG_NUMA)		+= lrng_numa.o

index 53c267115721..5587be09f495 100644
@@ -250,8 +250,13 @@ int lrng_drng_get_sleep(u8 *outbuf, u32 outbuflen);
 void lrng_drng_force_reseed(void);
 void lrng_drng_seed_work(struct work_struct *dummy);
 
+#ifdef CONFIG_NUMA
+struct lrng_drng **lrng_drng_instances(void);
+void lrng_drngs_numa_alloc(void);
+#else	/* CONFIG_NUMA */
 static inline struct lrng_drng **lrng_drng_instances(void) { return NULL; }
 static inline void lrng_drngs_numa_alloc(void) { return; }
+#endif /* CONFIG_NUMA */
 
 /************************** Health Test linking code **************************/
 

2.26.2

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 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 |   1 -
 drivers/char/lrng/lrng_internal.h   |   4 +
 drivers/char/lrng/lrng_proc.c       | 163 ++++++++++++++++++++++++++++
 4 files changed, 168 insertions(+), 1 deletion(-)
 create mode 100644 drivers/char/lrng/lrng_proc.c

index 0a32f22c2c1a..e69c176f0161 100644
@@ -9,3 +9,4 @@ obj-y				+= lrng_pool.o lrng_aux.o \
 				   lrng_interfaces.o \
 
 obj-$(CONFIG_NUMA)		+= lrng_numa.o
+obj-$(CONFIG_SYSCTL)		+= lrng_proc.o

index d9c68679136d..95ee99c82592 100644
@@ -35,7 +35,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? */

index 5587be09f495..8aea41a2f43f 100644
@@ -117,7 +117,11 @@ void lrng_cc20_init_state_boot(struct chacha20_state *state);
 
 /********************************** /proc *************************************/
 
+#ifdef CONFIG_SYSCTL
+void lrng_pool_inc_numa_node(void);
+#else
 static inline void lrng_pool_inc_numa_node(void) { }
+#endif
 
 /****************************** LRNG interfaces *******************************/
 

2.26.2

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.

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

index 059b21d9728c..d3138458fd8b 100644
@@ -65,4 +65,11 @@ config LRNG_POOL_SIZE
 	default 7 if LRNG_POOL_SIZE_65536
 	default 8 if LRNG_POOL_SIZE_131072
 
+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 e69c176f0161..31cfe87c999e 100644
@@ -10,3 +10,4 @@ obj-y				+= lrng_pool.o lrng_aux.o \
 
 obj-$(CONFIG_NUMA)		+= lrng_numa.o
 obj-$(CONFIG_SYSCTL)		+= lrng_proc.o
+obj-$(CONFIG_LRNG_DRNG_SWITCH)	+= lrng_switch.o

2.26.2

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 e99fe34cfa00..3644e954785a 100644
@@ -113,7 +113,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,

@@ -190,6 +190,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);
 

@@ -205,7 +206,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:

@@ -218,6 +219,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

@@ -1214,7 +1216,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;

@@ -1235,12 +1237,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;

@@ -1321,6 +1324,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

@@ -1890,8 +1894,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;

@@ -1918,6 +1921,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.26.2

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     |  12 ++
 drivers/char/lrng/Makefile    |   1 +
 drivers/char/lrng/lrng_drbg.c | 259 ++++++++++++++++++++++++++++++++++
 3 files changed, 272 insertions(+)
 create mode 100644 drivers/char/lrng/lrng_drbg.c

index d3138458fd8b..4ad26fdfbe7e 100644
@@ -72,4 +72,16 @@ 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_DRBG
+	tristate "SP800-90A support for the LRNG"
+	depends on CRYPTO
+	select CRYPTO_DRBG_MENU
+	select CRYPTO_SHA512
+	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 is provided by a DRBG.
+endif # LRNG_DRNG_SWITCH
+
 endif # LRNG

index 31cfe87c999e..0d320fcb7b9e 100644
@@ -11,3 +11,4 @@ obj-y				+= lrng_pool.o lrng_aux.o \
 obj-$(CONFIG_NUMA)		+= lrng_numa.o
 obj-$(CONFIG_SYSCTL)		+= lrng_proc.o
 obj-$(CONFIG_LRNG_DRNG_SWITCH)	+= lrng_switch.o
+obj-$(CONFIG_LRNG_DRBG)		+= lrng_drbg.o

2.26.2

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      |  11 ++
 drivers/char/lrng/Makefile     |   1 +
 drivers/char/lrng/lrng_kcapi.c | 321 +++++++++++++++++++++++++++++++++
 3 files changed, 333 insertions(+)
 create mode 100644 drivers/char/lrng/lrng_kcapi.c

index 4ad26fdfbe7e..ba3d84cd0676 100644
@@ -82,6 +82,17 @@ 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 is provided by a DRBG.
+
+config LRNG_KCAPI
+	tristate "Kernel Crypto API support for the LRNG"
+	depends on CRYPTO
+	select CRYPTO_RNG
+	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 0d320fcb7b9e..94b2dfb2dfdb 100644
@@ -12,3 +12,4 @@ obj-$(CONFIG_NUMA)		+= lrng_numa.o
 obj-$(CONFIG_SYSCTL)		+= lrng_proc.o
 obj-$(CONFIG_LRNG_DRNG_SWITCH)	+= lrng_switch.o
 obj-$(CONFIG_LRNG_DRBG)		+= lrng_drbg.o
+obj-$(CONFIG_LRNG_KCAPI)	+= lrng_kcapi.o

2.26.2

To support the LRNG operation which uses the Jitter RNG separately from the kernel crypto API, at a time where potentially the regular memory management is not yet initialized, the Jitter RNG needs to provide a state whose memory is defined at compile time. As only once instance will ever be needed by the LRNG, define once static memory block which is solely to be used by the LRNG.

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

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

index 6e147c43fc18..fa1459f09b01 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

@@ -854,3 +854,32 @@ int jent_entropy_init(void)
 
 	return 0;
 }
+
+struct rand_data *jent_lrng_entropy_collector(void)
+{
+	static unsigned char lrng_jent_mem[JENT_MEMORY_SIZE];
+	static struct rand_data lrng_jent_state = {
+		.data		= 0,
+		.old_data	= 0,
+		.prev_time	= 0,
+		.last_delta	= 0,
+		.last_delta2	= 0,
+		.osr		= 1,
+		.mem		= lrng_jent_mem,
+		.memlocation	= 0,
+		.memblocks	= JENT_MEMORY_BLOCKSIZE,
+		.memblocksize	= JENT_MEMORY_BLOCKS,
+		.memaccessloops	= JENT_MEMORY_ACCESSLOOPS,
+		.rct_count	= 0,
+		.apt_observations = 0,
+		.apt_count	= 0,
+		.apt_base	= 0,
+		.apt_base_set	= 0,
+		.health_failure = 0
+	};
+
+	if (jent_entropy_init())
+		return NULL;
+
+	return &lrng_jent_state;
+}

similarity index 84%
rename from crypto/jitterentropy.h
rename to include/crypto/internal/jitterentropy.h
index c83fff32d130..6e07d86eac82 100644
@@ -15,3 +15,6 @@ extern int jent_read_entropy(struct rand_data *ec, unsigned char *data,
 extern struct rand_data *jent_entropy_collector_alloc(unsigned int osr,
 						      unsigned int flags);
 extern void jent_entropy_collector_free(struct rand_data *entropy_collector);
+
+/* Access to statically allocated Jitter RNG instance */
+extern struct rand_data *jent_lrng_entropy_collector(void);

2.26.2

From 4a94cf2db12d5d1f8fd3354ea0da2c5726f96ac7 Mon Sep 17 00:00:00 2001
From: Stephan Mueller <[email protected]>
Date: Sun, 19 Jan 2020 21:23:17 +0100
Subject:
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

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     | 12 +++++
 drivers/char/lrng/Makefile    |  1 +
 drivers/char/lrng/lrng_jent.c | 88 +++++++++++++++++++++++++++++++++++
 3 files changed, 101 insertions(+)
 create mode 100644 drivers/char/lrng/lrng_jent.c

index ba3d84cd0676..66a775a8f912 100644
@@ -95,4 +95,16 @@ config LRNG_KCAPI
 	  provided by the selected kernel crypto API RNG.
 endif # LRNG_DRNG_SWITCH
 
+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.
+
 endif # LRNG

index 94b2dfb2dfdb..4f5b6f38f0c4 100644
@@ -13,3 +13,4 @@ obj-$(CONFIG_SYSCTL)		+= lrng_proc.o
 obj-$(CONFIG_LRNG_DRNG_SWITCH)	+= lrng_switch.o
 obj-$(CONFIG_LRNG_DRBG)		+= lrng_drbg.o
 obj-$(CONFIG_LRNG_KCAPI)	+= lrng_kcapi.o
+obj-$(CONFIG_LRNG_JENT)		+= lrng_jent.o

2.26.2

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 LFSR. 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       |  56 +++++
 drivers/char/lrng/Makefile      |   1 +
 drivers/char/lrng/lrng_health.c | 407 ++++++++++++++++++++++++++++++++
 3 files changed, 464 insertions(+)
 create mode 100644 drivers/char/lrng/lrng_health.c

index 66a775a8f912..70eee0f43d8c 100644
@@ -107,4 +107,60 @@ config LRNG_JENT
 	  time or at runtime with the lrng_base.jitterrng configuration
 	  variable.
 
+config LRNG_HEALTH_TESTS
+	bool "Enable noise source online health tests"
+	help
+	  The online health tests 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 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 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 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
+
 endif # LRNG

index 4f5b6f38f0c4..c3008763dd14 100644
@@ -14,3 +14,4 @@ obj-$(CONFIG_LRNG_DRNG_SWITCH)	+= lrng_switch.o
 obj-$(CONFIG_LRNG_DRBG)		+= lrng_drbg.o
 obj-$(CONFIG_LRNG_KCAPI)	+= lrng_kcapi.o
 obj-$(CONFIG_LRNG_JENT)		+= lrng_jent.o
+obj-$(CONFIG_LRNG_HEALTH_TESTS)	+= lrng_health.o

2.26.2

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 conatenated 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

* array logic batching the high-resolution time stamp

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        | 124 +++++++
 drivers/char/lrng/Makefile       |   1 +
 drivers/char/lrng/lrng_testing.c | 575 +++++++++++++++++++++++++++++++
 3 files changed, 700 insertions(+)
 create mode 100644 drivers/char/lrng/lrng_testing.c

index 70eee0f43d8c..4feabb0a20c2 100644
@@ -163,4 +163,128 @@ config LRNG_APT_CUTOFF
 	default 325 if !LRNG_APT_BROKEN
 	default 32 if LRNG_APT_BROKEN
 
+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_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_TESTING
+	bool
+	default y if (LRNG_RAW_ENTROPY || LRNG_RAW_ARRAY || LRNG_IRQ_PERF)
+
+endif #LRNG_TESTING_MENU
+
 endif # LRNG

index c3008763dd14..b2ce1979dc4b 100644
@@ -15,3 +15,4 @@ obj-$(CONFIG_LRNG_DRBG)		+= lrng_drbg.o
 obj-$(CONFIG_LRNG_KCAPI)	+= lrng_kcapi.o
 obj-$(CONFIG_LRNG_JENT)		+= lrng_jent.o
 obj-$(CONFIG_LRNG_HEALTH_TESTS)	+= lrng_health.o
+obj-$(CONFIG_LRNG_TESTING)	+= lrng_testing.o

2.26.2

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 LFSR operation. This test injects a monotonic increasing counter into the LFSR. After completion of the injection of the counter, 3 pool words are compared with known good values. The known good values are calculated with the newly-developed tool lfsr_testvector_generation provided as part of the LRNG test tool set at [1].

* Self-test of the Hash_DF operation ensures that this function operates compliant to the specification. The self-test performs a Hash_DF operation of a zeroized entropy pool state. The test vectors are generated using the newly-developed tool hash_df_testvector_generation provided as part of the LRNG test tool set at [1].

* 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 [2]. 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/lrng.html
[2] https://www.chronox.de/chacha20.html

---
 drivers/char/lrng/Kconfig         |  25 ++
 drivers/char/lrng/Makefile        |   1 +
 drivers/char/lrng/lrng_selftest.c | 504 ++++++++++++++++++++++++++++++
 3 files changed, 530 insertions(+)
 create mode 100644 drivers/char/lrng/lrng_selftest.c

index 4feabb0a20c2..e8b7e9620123 100644
@@ -287,4 +287,29 @@ config LRNG_TESTING
 
 endif #LRNG_TESTING_MENU
 
+config LRNG_SELFTEST
+	bool "Enable power-on and on-demand self-tests"
+	help
+	  The power-on self-tests are executed during boot time
+	  covering the ChaCha20 DRNG, the LFSR processing and the
+	  time stamp management of the LRNG.
+
+	  The on-demand self-tests are triggered by writing any
+	  value into the SysFS file selftest_status. At the same
+	  time, when reading this file, the test status is
+	  returned. A zero indicates that all tests were executed
+	  successfully.
+
+	  If unsure, say Y.
+
+if LRNG_SELFTEST
+
+config LRNG_SELFTEST_PANIC
+	bool "Panic the kernel upon self-test failure"
+	help
+	  If the option is enabled, the kernel is terminated if an
+	  LRNG power-on self-test failure is detected.
+
+endif # LRNG_SELFTEST
+
 endif # LRNG

index b2ce1979dc4b..92219c565f66 100644
@@ -16,3 +16,4 @@ obj-$(CONFIG_LRNG_KCAPI)	+= lrng_kcapi.o
 obj-$(CONFIG_LRNG_JENT)		+= lrng_jent.o
 obj-$(CONFIG_LRNG_HEALTH_TESTS)	+= lrng_health.o
 obj-$(CONFIG_LRNG_TESTING)	+= lrng_testing.o
+obj-$(CONFIG_LRNG_SELFTEST)	+= lrng_selftest.o

2.26.2

Hi,

The following patch set provides a different approach to /dev/random which is called Linux Random Number Generator (LRNG) to collect entropy within the Linux kernel. The main improvements compared to the existing /dev/random is to provide sufficient entropy during boot time as well as in virtual environments and when using SSDs. A secondary design goal is to limit the impact of the entropy collection on massive parallel systems and also allow the use accelerated cryptographic primitives. Also, all steps of the entropic data processing are testable.

The LRNG patch set allows a user to select use of the existing /dev/random or the LRNG during compile time. As the LRNG provides API and ABI compatible interfaces to the existing /dev/random implementation, the user can freely chose the RNG implementation without affecting kernel or user space operations.

This patch set provides early boot-time entropy which implies that no additional flags to the getrandom(2) system call discussed recently on the LKML is considered to be necessary. Yet, if additional flags are introduced to cover special hardware, the LRNG implementation will also provide them to be fully ABI and API compliant as already discussed on LKML.

The LRNG is fully compliant to SP800-90B requirements and is shipped with a full SP800-90B assessment and all required test tools. The existing /dev/random implementation on the other hand has architectural limitations which does not easily allow to bring the implementation in compliance with SP800-90B. The key statement that causes concern is SP800-90B section 3.1.6. This section denies crediting entropy to multiple similar noise sources. This section explicitly references different noise sources resting on the timing of events and their derivatives (i.e. it is a direct complaint to the existing existing /dev/random implementation). Therefore, SP800-90B now denies the very issue mentioned in [1] with the existing /dev/random implementation for a long time: crediting entropy to interrupts as well as crediting entropy to derivatives of interrupts (HID and disk events). This is not permissible with SP800-90B.

SP800-90B specifies various requirements for the noise source(s) that seed any DRNG including SP800-90A DRBGs. In about a year from now, SP800-90B will be mandated for all noise sources that provide entropy to DRBGs as part of a FIPS 140-[2|3] validation or other evaluation types. That means, if we there are no solutions to comply with the requirements of SP800-90B found till one year from now, any random number generation and ciphers based on random numbers on Linux will be considered and treated as not applicable and delivering no entropy! As /dev/urandom, getrandom(2) and /dev/random are the most common and prevalent noise sources for DRNGs, all these DRNGs are affected. This applies across the board for all validations of cryptography executing on Linux (kernel and user space modules).

For users that are not interested in SP800-90B, the entire code for the compliance as well as test interfaces can be deselected at compile time.

The design and implementation is driven by a set of goals described in [1] that the LRNG completely implements. Furthermore, [1] includes the full assessment of the SP800-90B compliance as well as a comparison with RNG design suggestions of SP800-90C, and AIS20/31.

The LRNG provides a complete separation of the noise source maintenance and the collection of entropy into an entropy pool from the post-processing using a pseudo-random number generator. Different DRNGs are supported, including:

* The LRNG can be compile-time enabled to replace the existing /dev/random implementation. When not selecting the LRNG at compile time (default), the existing /dev/random implementation is built.

* Built-in ChaCha20 DRNG which has no dependency to other kernel frameworks.

* SP800-90A DRBG using the kernel crypto API including its accelerated raw cipher implementations. This implies that the output of /dev/random, getrandom(2), /dev/urandom or get_random_bytes is fully compliant to SP800-90A.

* Arbitrary DRNGs registered with the kernel crypto API

* Full compliance with SP800-90B which covers the startup and runtime health tests mandated by SP800-90B as well as providing the test tools and test interfaces to obtain raw noise data securely. The test tools are provided at [1].

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

The LRNG has a flexible design by allowing an easy replacement of the deterministic random number generator component.

Compared to the existing /dev/random implementation, the compiled binary is smaller when the LRNG is compiled with all options equal to the existing /dev/random (i.e. only CONFIG_LRNG is set): random.o is 52.5 kBytes whereas all LRNG object files are in 49 kBytes in size. The fully SP800-90A/SP800-90B compliant binary code (CONFIG_LRNG, CONFIG_LRNG_DRNG_SWITCH, CONFIG_LRNG_DRBG, CONFIG_LRNG_HEALTH_TESTS) uses some 61 kBytes. In addition, the LRNG is about 50% faster in the performance critical interrupt handler code path compared to the existing /dev/random implementation.

Full SP800-90B testing 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

[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

Changes (compared to the previous patch set):

* fix all sparse warnings, partially reported by kernel test robot <[email protected]>

* ensure that DRBG or KCAPI backend can only be exclusively compiled if it is selected for static compilation - suggested by
Andy Lavr <[email protected]>

* fix Kconfig to enable compilation of lrng_testing.c in all possible configurations reported by kernel test robot <[email protected]>

* include trace/events/random.h to make lib/random32.c happy (even though the LRNG does not need this header file) reported by kernel test robot <[email protected]>

As a side node: With the switchable DRNG support offered in this patch set, the following areas could be removed. As the existing /dev/random has no support for switchable DRNGs, however, this is not yet feasible though.

* remove lrng_ready_list and all code around it in lrng_interfaces.c

* remove the kernel crypto API RNG API to avoid having two random number providing APIs - this would imply that all RNGs developed for this API would be converted to the LRNG interface

Stephan Mueller (12):
Linux Random Number Generator
LRNG - allocate one DRNG instance per NUMA node LRNG - sysctls and /proc interface
LRNG - add switchable DRNG support
crypto: DRBG - externalize DRBG functions for LRNG LRNG - add SP800-90A DRBG extension
LRNG - add kernel crypto API PRNG extension
crypto: provide access to a static Jitter RNG state 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                        |  31 +-
 drivers/char/Kconfig                          |   2 +
 drivers/char/Makefile                         |   9 +-
 drivers/char/lrng/Kconfig                     | 316 +++++++++
 drivers/char/lrng/Makefile                    |  19 +
 drivers/char/lrng/lrng_archrandom.c           |  93 +++
 drivers/char/lrng/lrng_aux.c                  | 136 ++++
 drivers/char/lrng/lrng_chacha20.c             | 321 +++++++++
 drivers/char/lrng/lrng_chacha20.h             |  29 +
 drivers/char/lrng/lrng_drbg.c                 | 259 +++++++
 drivers/char/lrng/lrng_drng.c                 | 409 +++++++++++
 drivers/char/lrng/lrng_health.c               | 407 +++++++++++
 drivers/char/lrng/lrng_interfaces.c           | 651 ++++++++++++++++++
 drivers/char/lrng/lrng_internal.h             | 351 ++++++++++
 drivers/char/lrng/lrng_jent.c                 |  88 +++
 drivers/char/lrng/lrng_kcapi.c                | 321 +++++++++
 drivers/char/lrng/lrng_lfsr.h                 | 152 ++++
 drivers/char/lrng/lrng_numa.c                 | 101 +++
 drivers/char/lrng/lrng_pool.c                 | 589 ++++++++++++++++
 drivers/char/lrng/lrng_proc.c                 | 163 +++++
 drivers/char/lrng/lrng_selftest.c             | 506 ++++++++++++++
 drivers/char/lrng/lrng_sw_noise.c             | 155 +++++
 drivers/char/lrng/lrng_sw_noise.h             |  57 ++
 drivers/char/lrng/lrng_switch.c               | 193 ++++++
 drivers/char/lrng/lrng_testing.c              | 575 ++++++++++++++++
 include/crypto/drbg.h                         |   7 +
 .../crypto/internal}/jitterentropy.h          |   3 +
 include/linux/lrng.h                          |  63 ++
 31 files changed, 6022 insertions(+), 10 deletions(-)
 create mode 100644 drivers/char/lrng/Kconfig
 create mode 100644 drivers/char/lrng/Makefile
 create mode 100644 drivers/char/lrng/lrng_archrandom.c
 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_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_jent.c
 create mode 100644 drivers/char/lrng/lrng_kcapi.c
 create mode 100644 drivers/char/lrng/lrng_lfsr.h
 create mode 100644 drivers/char/lrng/lrng_numa.c
 create mode 100644 drivers/char/lrng/lrng_pool.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_sw_noise.c
 create mode 100644 drivers/char/lrng/lrng_sw_noise.h
 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 (84%)
 create mode 100644 include/linux/lrng.h

2.26.2

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

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

1. The LRNG implements a DRNG. The DRNG always generates the requested amount of output. When using the SP800-90A terminology it operates without prediction resistance. The secondary DRNG maintains a counter of how many bytes were generated since last re-seed and a timer of the elapsed time since last re-seed. If either the counter or the timer reaches a threshold, the secondary DRNG is seeded from the entropy pool.

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

2. The DRNG is seeded by concatenating the data from the following sources:

(a) the output of the entropy pool,

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

(c) the CPU-based noise source such as Intel RDRAND if available and enabled.

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

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

(a) During boot time, the amount of received interrupts are the trigger points to (re)seed the DRNG.

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

3. The entropy pool accumulates entropy obtained from certain events, which will henceforth be collectively called "slow noise sources". The entropy pool collects noise data from slow noise sources. Any data received by the LRNG from the slow noise sources is inserted into the entropy pool using an LFSR with a primitive and irreducible polynomial. The following sources of entropy are used:

(a) When an interrupt occurs, the high-resolution time stamp is mixed
into the LFSR. 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 LFSR. This data is not credited with entropy by the LRNG.

(c) Device drivers may provide data that is mixed into the LFSR. This
data is not credited with entropy by the LRNG.

(d) After the entropy pool is ``read'' by the DRNG, the data
used to seed the DRNG is mixed back into the entropy pool to stir the pool. This data is not credited with entropy by the LRNG.

Any data provided from user space by either writing to /dev/random, /dev/urandom or the IOCTL of RNDADDENTROPY on both device files are always injected into the entropy pool.

In addition, when a hardware random number generator covered by the Linux kernel HW generator framework wants to deliver random numbers, it is injected into the entropy 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 the DRNG requires data from the entropy pool, the entire entropy pool is processed with an SP800-90A section 10.3.1 compliant hash_df function to generate random numbers.

To speed up the interrupt handling code of the LRNG, the time stamp collected for an interrupt event is truncated to the 8 least significant bits. 64 truncated time stamps are concatenated and then jointly inserted into the LFSR. During boot time, until the fully seeded stage is reached, each time stamp with its 32 least significant bits is inserted into the LFSR at the time of arrival.

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. LFSR: The 8 least significant bits of the time stamp data received from the interrupts are processed with an LFSR. That LFSR is implemented identically to the LSFR used in the existing /dev/random implementation except that it is capable of processing an entire word and that a different polynomial is used. The reason for the different polynomial is performance in a performance sensitive code section, the interrupt handler. The chosen polynomials have 4 taps. Also, this LFSR-approach is used in the OpenBSD /dev/random equivalent.

2. Concatenation: The temporary seed buffer used to seed the DRNG is a concatenation of parts of the entropy pool data, and the CPU noise source output.

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 pool and potentially the fast noise sources if the entropy pool has collected at least 32 bits of entropy from the interrupt noise source. The goal of this step is to ensure that the DRNG receives some initial entropy as early as possible. In addition it receives the entropy available from the fast noise sources.

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

3. The DRNG is reseeded from the entropy pool and potentially the fast noise sources if all noise sources collectivel 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.

In all listed steps, the DRNG is (re)seeded with a number of random bytes from the entropy pool that is at most the amount of entropy present in the entropy pool. This means that when the entropy pool contains 128 or 256 bits of entropy, the DRNG is seeded with that amount of entropy as well.

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

The hash_df operation providing random data from the entropy pool will always require that all entropy sources collectively can deliver at least 129 entropy bits as configured with (128 bits of entropy for seeding plus one bit of entropy that is lost with the post processing as defined in SP800-90B).

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 secondary DRNG is reseeded with whatever entropy is available – in the worst case where no additional entropy can be provided by the noise 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 secondary DRNG is more than 600 seconds ago, or

- 2^20 DRNG generate operations are performed, whatever comes first, or

- the secondary DRNG is forced to reseed before the next generation of random numbers if data has been injected into the LRNG by writing data into /dev/random or /dev/urandom.

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

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.

The LRNG uses the following runtime memory using the currently smallest configuration:

* 576 bytes (512 bytes for the entropy pool and 64 for the entropy pool meta data) for the entropy pool management

* 64 bytes per CPU for the time stamp array

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

The entropy pool has support for sizes of 256, 128 and 64 bytes supported by primitive and irreducible polynomials.

The time stamp array is reduced to one atomic_t variable per CPU, i.e. 4 bytes when CONFIG_BASE_SMALL is selected during kernel configuration. This implies that after the receipt of 4 interrupts on one CPU, the data is injected into the LFSR. Depending on the behavior of the CPU caches, this may imply that the average interrupt handler execution time increases a bit, since instead of injecting 8 atomic_t values at one given time into the LFSR, only one is processed which may incur cache misses.

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 executes within an average of 65 cycles whereas the existing /dev/random on the same device takes about 97 cycles when measuring the execution time of add_interrupt_randomness().

* lockless LFSR to collect raw entropy supporing concurrency-free use of massive parallel systems

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

* "atomic" seeding of secondary DRBG to ensure full entropy transport

* instantiate one DRNG per NUMA node

* support for runtime switchable output DRNGs

* use of only well-defined entropy-preserving operations to collect, compress and forward entropy: concatenation, LFSR, SP800-90A hash_df function

* compile-time selectable entropy pool size: the choice also uses the applicable LFSR polynomial to maintain the entropy pool 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.

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

CC: "Eric W. Biederman" <[email protected]>
CC: "Alexander E. Patrakov" <[email protected]>
CC: "Ahmed S. Darwish" <[email protected]>
CC: "Theodore Y. Ts'o" <[email protected]>
CC: Willy Tarreau <[email protected]>
CC: Matthew Garrett <[email protected]>
CC: Vito Caputo <[email protected]>
CC: Andreas Dilger <[email protected]>
CC: Jan Kara <[email protected]>
CC: Ray Strode <[email protected]>
CC: William Jon McCann <[email protected]>
CC: zhangjs <[email protected]>
CC: Andy Lutomirski <[email protected]>
CC: Florian Weimer <[email protected]>
CC: Lennart Poettering <[email protected]>
CC: Nicolai Stange <[email protected]>
Mathematical aspects Reviewed-by: "Peter, Matthias" <[email protected]>

---
 MAINTAINERS                         |   7 +
 drivers/char/Kconfig                |   2 +
 drivers/char/Makefile               |   9 +-
 drivers/char/lrng/Kconfig           |  68 +++
 drivers/char/lrng/Makefile          |   9 +
 drivers/char/lrng/lrng_archrandom.c |  93 ++++
 drivers/char/lrng/lrng_aux.c        | 136 ++++++
 drivers/char/lrng/lrng_chacha20.c   | 321 ++++++++++++++
 drivers/char/lrng/lrng_chacha20.h   |  29 ++
 drivers/char/lrng/lrng_drng.c       | 409 +++++++++++++++++
 drivers/char/lrng/lrng_interfaces.c | 652 ++++++++++++++++++++++++++++
 drivers/char/lrng/lrng_internal.h   | 342 +++++++++++++++
 drivers/char/lrng/lrng_lfsr.h       | 152 +++++++
 drivers/char/lrng/lrng_pool.c       | 589 +++++++++++++++++++++++++
 drivers/char/lrng/lrng_sw_noise.c   | 155 +++++++
 drivers/char/lrng/lrng_sw_noise.h   |  57 +++
 include/linux/lrng.h                |  63 +++
 17 files changed, 3092 insertions(+), 1 deletion(-)
 create mode 100644 drivers/char/lrng/Kconfig
 create mode 100644 drivers/char/lrng/Makefile
 create mode 100644 drivers/char/lrng/lrng_archrandom.c
 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_interfaces.c
 create mode 100644 drivers/char/lrng/lrng_internal.h
 create mode 100644 drivers/char/lrng/lrng_lfsr.h
 create mode 100644 drivers/char/lrng/lrng_pool.c
 create mode 100644 drivers/char/lrng/lrng_sw_noise.c
 create mode 100644 drivers/char/lrng/lrng_sw_noise.h
 create mode 100644 include/linux/lrng.h

index deaafb617361..74f6fd1ba1ec 100644
@@ -10084,6 +10084,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 b1bd336761b1..8a5b8a2db2c7 100644
@@ -470,6 +470,8 @@ config ADI
 	  and SSM (Silicon Secured Memory).  Intended consumers of this
 	  driver include crash and makedumpfile.
 
+source "drivers/char/lrng/Kconfig"
+
 endmenu
 
 config RANDOM_TRUST_CPU

index ffce287ef415..2110d3e28cf2 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..1d2a0211973d
@@ -0,0 +1,9 @@
+# SPDX-License-Identifier: GPL-2.0
+#
+# Makefile for the Linux Random Number Generator.
+#
+
+obj-y				+= lrng_pool.o lrng_aux.o \
+				   lrng_sw_noise.o lrng_archrandom.o \
+				   lrng_drng.o lrng_chacha20.o \
+				   lrng_interfaces.o \

new file mode 100644
index 000000000000..1533b2490964
@@ -0,0 +1,29 @@
+/* SPDX-License-Identifier: GPL-2.0 OR BSD-2-Clause */
+/*
+ * LRNG ChaCha20 definitions
+ *
+ * Copyright (C) 2016 - 2020, 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 __latent_entropy;
+	u32 counter;
+	u32 nonce[3] __latent_entropy;
+};
+
+static inline void lrng_cc20_init_rfc7539(struct chacha20_block *chacha20)
+{
+	/* String "expand 32-byte k" */
+	chacha20->constants[0] = 0x61707865;
+	chacha20->constants[1] = 0x3320646e;
+	chacha20->constants[2] = 0x79622d32;
+	chacha20->constants[3] = 0x6b206574;
+}

2.26.2

Part of the diff is not shown here. View the raw message.

Am Dienstag, 25. August 2020, 13:28:53 CEST schrieb kernel test robot:

Hi,

The prototype is covered in an ifdef in lrng_internal.h as it is only needed for a specific configuration. I have moved the prototype out of that configuration conditional now.

Thanks.

Ciao
Stephan

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        |   2 +
 drivers/char/lrng/lrng_internal.h |   5 ++
 drivers/char/lrng/lrng_numa.c     | 101 ++++++++++++++++++++++++++++++
 3 files changed, 108 insertions(+)
 create mode 100644 drivers/char/lrng/lrng_numa.c

index 1d2a0211973d..0a32f22c2c1a 100644
@@ -7,3 +7,5 @@ obj-y				+= lrng_pool.o lrng_aux.o \
 				   lrng_sw_noise.o lrng_archrandom.o \
 				   lrng_drng.o lrng_chacha20.o \
 				   lrng_interfaces.o \
+
+obj-$(CONFIG_NUMA)		+= lrng_numa.o

index f86afe8d2612..de034260c323 100644
@@ -256,8 +256,13 @@ int lrng_drng_get_sleep(u8 *outbuf, u32 outbuflen);
 void lrng_drng_force_reseed(void);
 void lrng_drng_seed_work(struct work_struct *dummy);
 
+#ifdef CONFIG_NUMA
+struct lrng_drng **lrng_drng_instances(void);
+void lrng_drngs_numa_alloc(void);
+#else	/* CONFIG_NUMA */
 static inline struct lrng_drng **lrng_drng_instances(void) { return NULL; }
 static inline void lrng_drngs_numa_alloc(void) { return; }
+#endif /* CONFIG_NUMA */
 
 /************************** Health Test linking code **************************/
 

2.26.2

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