[PATCH v35 00/13] /dev/random - a new approach

From: Stephan Müller
Date: Fri Sep 18 2020 - 06:13:04 EST


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 following advantages compared to the existing /dev/random
implementation are present:

* Sole use of crypto for data processing:

- exclusive use of a hash operation for conditioning entropy data with
a clear mathematical description as given in [2] section 2.2 -
non-cryptographic operations like LFSR are not used

- accelerated SHA-512 and software SHA-256 hash are available - LRNG works
even if the kernel crypto API is not compiled

- hash operations use NUMA-node-local hash instances to benefit large
parallel systems

- runtime-switchable DRNG and hash implementations which allows
the use of an SP800-90A DRBG or other types of DRNGs

* Performance

- faster by up to 75% in the critical code path of the interrupt handler
depending on data collection size configurable at kernel compile time -
the default is about equal in performance with existing /dev/random

- configurable data collection sizes to accommodate small environments and
big environments

- entropy collection using an almost never contended lock to benefit
large parallel systems - worst case rate of contention is the number
of DRNG reseeds, usually the number of potential contentions per 5
minutes is equal to number of NUMA nodes.

- ChaCha20 DRNG is significantly faster as implemented in random.c

- faster entropy collection during boot time to reach fully seeded level,
including on virtual systems or systems with SSDs

* Testing

- heuristic entropy estimation is based on analysis following SP800-90B
and not on coincidental underestimation of entropy

- power-on self tests for critical deterministic components
(ChaCha20 DRNG, hash, and entropy collection logic) not already
covered by power-up tests of the kernel crypto API

- availability of test interfaces for all operational stages of the LRNG
including boot-time raw entropy event data sampling

- fully testable ChaCha20 DRNG - see [3]

* Entropy collection

- The LRNG is fully compliant to SP800-90B requirements and is shipped with
a full SP800-90B assessment and all required test tools in [1]. 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 existing /dev/random is not easily made
compliant with SP800-90B as outlined in [2] section 4.5.

- full entropy assessment and description provided with [2], specifically
section 3.2.6

- guarantee that entropy events are not credited with entropy twice
(the existing /dev/random implementation credits HID/disk and interrupt
events with entropy which are a derivative of each other) and
guarantee that entropy data is not reused for two different use cases
(as done in the existing /dev/random implementation when injecting a
part of fast_pool into the net_rand_state)

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

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 [2]
that the LRNG completely implements. Furthermore, [2] 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 per-CPU entropy pools from the
post-processing using a pseudo-random number generator. Different
DRNGs are supported, including:

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

* 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

* Arbitrary DRNGs registered with the kernel crypto API

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 as well as hash

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


* IBM Z System mainframe

* old MIPS embedded device

* testing with GCC and Clang

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

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

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

Changes (compared to the previous patch set):

* replace hash_df operation with simple hash to make code leaner without
affecting entropy statements

* replace central LFSR with per-CPU entropy pools which implies that
LRNG only uses a hash for conditioning - this makes data processing
much cleaner (see [2] section 2.2) entropy assessment significantly
easier (see [2] section 3.2.6)

* add aux_pool to process data received from user space and
add_hwgenerator_randomness with a cryptographic hash compliant to
SP800-90B section 3.1.6 to allow data from those sources and stay
SP800-90B compliant

* remove duplicated code - add lrng_kcapi_hash.c to consolidate hash
handling code from lrng_drbg.c and lrng_kcapi.c

* ensure that the NUMA pool allocation also allocates the hash instance
as a precaution in case the DRNG switching code is executed before
the NUMA allocation

* Make invocation of SHA-1 compliant to FIPS 180-4

* Addition of test interface for interrupt registers noise data -
with that interface, all data potentially delivering entropy can be

* Addition of ACVT interface to validate correct invocation of SHA by
LRNG (for test definition, see https://github.com/usnistgov/ACVP) -
interface was used for successful testing of the SHA-256 and SHA-1
handling of the LRNG.

* remove superfluous backslash from Makefile reported by
Andy Lavr <andy.lavr@xxxxxxxxx>

* move prototype of lrng_reset() to a spot in lrng_internal.h that is
compiled unconditional as requested by kernel test robot

* correctly advance *ppos in DebugFS read function for testing interfaces
preventing successive read operations

* fix __latent_entropy usage as reported by kernel test robot

* use compxch_release / smp_load_acquire to set NUMA pool as suggested
by Eric Biggers

CC: "Eric W. Biederman" <ebiederm@xxxxxxxxxxxx>
CC: "Alexander E. Patrakov" <patrakov@xxxxxxxxx>
CC: "Ahmed S. Darwish" <darwish.07@xxxxxxxxx>
CC: "Theodore Y. Ts'o" <tytso@xxxxxxx>
CC: Willy Tarreau <w@xxxxxx>
CC: Matthew Garrett <mjg59@xxxxxxxxxxxxx>
CC: Vito Caputo <vcaputo@xxxxxxxxxxx>
CC: Andreas Dilger <adilger.kernel@xxxxxxxxx>
CC: Jan Kara <jack@xxxxxxx>
CC: Ray Strode <rstrode@xxxxxxxxxx>
CC: William Jon McCann <mccann@xxxxxxx>
CC: zhangjs <zachary@xxxxxxxxxxxxxxxx>
CC: Andy Lutomirski <luto@xxxxxxxxxx>
CC: Florian Weimer <fweimer@xxxxxxxxxx>
CC: Lennart Poettering <mzxreary@xxxxxxxxxxx>
CC: Nicolai Stange <nstange@xxxxxxx>
CC: Eric Biggers <ebiggers@xxxxxxxxxx>
Tested-by: Roman Drahtmüller <draht@xxxxxxxxxxxxxx>
Tested-by: Marcelo Henrique Cerri <marcelo.cerri@xxxxxxxxxxxxx>

Stephan Mueller (13):
Linux Random Number Generator
LRNG - allocate one DRNG instance per NUMA node
LRNG - sysctls and /proc interface
LRNG - add switchable DRNG support
LRNG - add common generic hash support
crypto: DRBG - externalize DRBG functions for LRNG
LRNG - add SP800-90A DRBG extension
LRNG - add kernel crypto API PRNG extension
crypto: 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

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 | 353 +++++++++
drivers/char/lrng/Makefile | 20 +
drivers/char/lrng/lrng_archrandom.c | 93 +++
drivers/char/lrng/lrng_aux.c | 136 ++++
drivers/char/lrng/lrng_chacha20.c | 352 +++++++++
drivers/char/lrng/lrng_chacha20.h | 29 +
drivers/char/lrng/lrng_drbg.c | 197 +++++
drivers/char/lrng/lrng_drng.c | 406 +++++++++++
drivers/char/lrng/lrng_health.c | 407 +++++++++++
drivers/char/lrng/lrng_interfaces.c | 649 +++++++++++++++++
drivers/char/lrng/lrng_internal.h | 426 +++++++++++
drivers/char/lrng/lrng_jent.c | 88 +++
drivers/char/lrng/lrng_kcapi.c | 228 ++++++
drivers/char/lrng/lrng_kcapi_hash.c | 97 +++
drivers/char/lrng/lrng_kcapi_hash.h | 19 +
drivers/char/lrng/lrng_numa.c | 108 +++
drivers/char/lrng/lrng_pool.c | 478 ++++++++++++
drivers/char/lrng/lrng_proc.c | 181 +++++
drivers/char/lrng/lrng_selftest.c | 344 +++++++++
drivers/char/lrng/lrng_sw_noise.c | 461 ++++++++++++
drivers/char/lrng/lrng_sw_noise.h | 56 ++
drivers/char/lrng/lrng_switch.c | 203 ++++++
drivers/char/lrng/lrng_testing.c | 687 ++++++++++++++++++
include/crypto/drbg.h | 7 +
.../crypto/internal}/jitterentropy.h | 3 +
include/linux/lrng.h | 79 ++
32 files changed, 6165 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_kcapi_hash.c
create mode 100644 drivers/char/lrng/lrng_kcapi_hash.h
create mode 100644 drivers/char/lrng/lrng_numa.c
create mode 100644 drivers/char/lrng/lrng_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