Re: [PATCH v41 00/13] /dev/random - a new approach

From: Alexander Lobakin
Date: Wed Jul 14 2021 - 07:54:47 EST


Hi,

From: Stephan Müller <smueller@xxxxxxxxxx>
Date: Wed, 14 Jul 2021 07:43:20 +0200

> 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. It provides the same API and ABI and can be used as a
> drop-in replacement. A general overview is given with [6].
>
> The LRNG implements at least all features of the existing /dev/random such as
> NUMA-node-local DRNGs. Patches 1 through 3 provide the code that is feature-
> identical. The following advantages compared to the existing /dev/random
> implementation are present:
>
> * Sole use of crypto for data processing:
>
> - Exclusive use of a hash operation for conditioning entropy data with
> a clear mathematical description as given in [2] section 2.2 -
> non-cryptographic operations like LFSR are not used.
>
> - The LRNG uses only properly defined and implemented cryptographic
> algorithms unlike the use of the SHA-1 transformation in the existing
> /dev/random implementation.
>
> - Hash operations use NUMA-node-local hash instances to benefit large
> parallel systems.
>
> - LRNG uses limited number of data post-processing steps as documented in
> [2] section 2.2 compared to the large variation of different
> post-processing steps in the existing /dev/random implementation that
> have no apparent mathematical description (see [2] section 4.5).
>
> * Performance
>
> - Faster by up to 130% in the critical code path of the interrupt handler
> depending on data collection size configurable at kernel compile time -
> the default is now set such that the highest performance is achieved as
> outlined in [2] section 4.2.
>
> - Configurable data collection sizes to accommodate small environments
> and big environments via CONFIG_LRNG_COLLECTION_SIZE.
>
> - Entropy collection using an almost never contended lock to benefit
> large parallel systems – worst case rate of contention is the number
> of DRNG reseeds, usually the number of potential contentions per 10
> minutes is equal to number of NUMA nodes.
>
> - ChaCha20 DRNG is significantly faster as implemented in the existing
> /dev/random as demonstrated with [2] table 2.
>
> - Faster entropy collection during boot time to reach fully seeded
> level, including on virtual systems or systems with SSDs as outlined
> in [2] section 4.1.
>
> - Faster processing of external data added to LRNG via /dev/random
> or add_hwgenerator_randomness.
>
> * Testing
>
> - Availability of run-time health tests of the raw unconditioned
> noise source to identify degradation of the available entropy as
> documented in [2] section 2.5.4. Such health tests are important
> today due to virtual machine monitors reducing the resolution of
> or disabling the high-resolution timer.
>
> - Heuristic entropy estimation is based on quantitative measurements
> and analysis following SP800-90B and not on coincidental
> underestimation of entropy applied by the existing /dev/random as
> outlined in [4] section 4.4.
>
> - Power-on self tests for critical deterministic components (ChaCha20
> DRNG, software hash implementation, and entropy collection logic)
> not already covered by power-up tests of the kernel crypto API as
> documented in [2] section 2.14.
>
> - Availability of test interfaces for all operational stages of the
> LRNG including boot-time raw entropy event data sampling as outlined
> in [2] section 2.15.
>
> - Fully testable ChaCha20 DRNG via a userspace ChaCha20 DRNG
> implementation [3].
>
> - In case of using the kernel crypto API SHASH hash implementation, it
> is fully testable and tested via the NIST ACVP test framework, for
> example certificates A734, A737, and A738.
>
> - The LRNG offers a test interface to validate the used software hash
> implementation and in particular that the LRNG invokes the hash
> correctly, allowing a NIST ACVP-compliant test cycle - see [2]
> section 2.15.
>
> - Availability of stress testing covering the different code paths for
> data and mechanism (de)allocations and code paths covered with locks.
>
> - Availability of regression tests verifying the different options provided
> with the LRNG.
>
> * Entropy collection
>
> - The LRNG is shipped with test tools allowing the collection of
> raw unconditioned entropy during runtime and boot time available at
> [1].
>
> - Full entropy assessment and description is provided with [2] chapter 3,
> specifically section 3.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).
>
> * Configurable
>
> - LRNG kernel configuration allows configuration that is functionally
> equivalent to the existing /dev/random. Non-compiled additional code
> is folded into no-ops.
>
> - The following additional functions are compile-time selectable
> independent of each other:
>
> + Enabling of switchable cryptographic implementation support. This
> allows enabling an SP800-90A DRBG.
>
> + Enabling of using Jitter RNG noise source.
>
> + Enabling of noise source health tests.
>
> + Enabling of test interface allowing to enable each test interface
> individually.
>
> + Enabling of the power-up self test.
>
> - At boot-time, the SP800-90B health tests can be enabled as outlined
> in [2] section 2.5.4.
>
> - At boot-time, the entropy rate used to credit the external CPU-based
> noise source and Jitter RNG noise source can be configured including
> setting an entropy rate of zero or full entropy - see [2] sections
> 2.5.2 and 2.5.3.
>
> * Run-time pluggable cryptographic implementations used for all data
> processing steps specified in [2] section 2.2
>
> - The DRNG can be replaced with a different implementation allowing
> any type of DRNG to provide data via the output interfaces. The LRNG
> provides the following types of DRNG implementations:
>
> + ChaCha20-based software implementation that is used per default.
>
> + SP800-90A DRBG using accelerated cryptographic implementations that
> may sleep.
>
> + Any DRNG that is accessible via the kernel crypto API RNG subsystem.
>
> - The hash component can be replaced with any other hash implementation
> provided the implementation does not sleep. The LRNG provides the
> access to the following types of non-sleeping hash implementations:
>
> + SHA-256 software implementation that is used per default. Due to
> kernel build system inconsistencies, the software SHA-1 implementation
> is used if the kernel crypto API is not compiled.
>
> + SHA-512 hash using the fastest hash implementation available via the
> kernel crypto API SHASH subsystem.
>
> * Code structure
>
> - The LRNG source code is available for current upstream Linux kernel
> separate to the existing /dev/random which means that users who are
> conservative can use the unchanged existing /dev/random implementation.
>
> - Back-port patches are available at [5] to apply the LRNG to Linux
> kernel versions of 5.10, 5.8, 5.4, 4.19, 4.14, 4.12, 4.10, and 4.4. Patches
> for other kernel versions are easily derived from the existing ones.
>
> Booting the patch with the kernel command line option
> "dyndbg=file drivers/char/lrng/* +p" generates logs indicating the
> operation of the LRNG. Each log is pre-pended with "lrng".
>
> An entropy analysis is performed on the following systems - details
> are given in [2] appendix C:
>
> * x86 KVM virtualized guest 32 and 64 bit systems
>
> * x86 bare metal
>
> * older and newer ARMv7 system
>
> * ARM64
>
> * POWER7 LE and POWER 8 BE
>
> * IBM Z System mainframe
>
> * old MIPS embedded device
>
> * testing with GCC and Clang
>
> [1] https://www.chronox.de/lrng.html - If the patch is accepted, I would
> be volunteering to convert the documentation into RST format and
> contribute it to the Linux kernel documentation directory.
>
> [2] https://www.chronox.de/lrng/doc/lrng.pdf
>
> [3] https://www.chronox.de/chacha20_drng.html
>
> [4] https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publications/Studies/LinuxRNG/LinuxRNG_EN_V4_1.pdf
>
> [5] https://github.com/smuellerDD/lrng/tree/master/backports
>
> [6] https://www.chronox.de/lrng/doc/lrng_presentation_v41.pdf
>
> Changes (compared to the previous patch set) - individual patches
> are visible at https://github.com/smuellerDD/lrng/commits/master:
>
> - update seeding threshold when loading DRNG only if min seeded
>
> - insert bootloader entropy directly into the aux pool
>
> - RNDADDTOENTCNT - entropy estmate update of aux pool
>
> - cleanup of initial seeding
>
> - use work queue after initialization only
>
> - add_random_ready_callback ping after full initialization
>
> - zeroize seed buffer
>
> - invoke processing of ready_list only if fully seeded
>
> - invoke invalidate_batched_entropy after initialization
>
> - always fill in the time stamp into seed buffer
>
> - initialize entropy value if insufficient entropy available
>
> - signal end of boot cycle in non-NUMA configuration
>
> - set NUMA node online flag in proper condition
>
> - harden entropy source configuration
>
> - significantly enhance performance of aux pool
>
> - fix LRNG reseed locking
>
> - set LRNG to non-operational for 90C compliance
>
> - fix increment of ChaCha20 nonce
>
> - make switch functions a noop if switching is disabled
>
> CC: Torsten Duwe <duwe@xxxxxx>
> 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>
> CC: Alexander Lobakin <alobakin@xxxxx>

For the series:

Reviewed-by: Alexander Lobakin <alobakin@xxxxx>
Tested-by: Alexander Lobakin <alobakin@xxxxx>

> 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
>
> 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 | 515 +++++++++++++
> drivers/char/lrng/Makefile | 20 +
> drivers/char/lrng/lrng_archrandom.c | 91 +++
> 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 | 198 +++++
> drivers/char/lrng/lrng_drng.c | 422 +++++++++++
> drivers/char/lrng/lrng_health.c | 410 ++++++++++
> drivers/char/lrng/lrng_interfaces.c | 648 ++++++++++++++++
> drivers/char/lrng/lrng_internal.h | 425 +++++++++++
> drivers/char/lrng/lrng_jent.c | 90 +++
> drivers/char/lrng/lrng_kcapi.c | 227 ++++++
> drivers/char/lrng/lrng_kcapi_hash.c | 103 +++
> drivers/char/lrng/lrng_kcapi_hash.h | 20 +
> drivers/char/lrng/lrng_numa.c | 122 +++
> drivers/char/lrng/lrng_pool.c | 622 ++++++++++++++++
> drivers/char/lrng/lrng_proc.c | 185 +++++
> drivers/char/lrng/lrng_selftest.c | 351 +++++++++
> drivers/char/lrng/lrng_sw_noise.c | 702 ++++++++++++++++++
> drivers/char/lrng/lrng_sw_noise.h | 71 ++
> drivers/char/lrng/lrng_switch.c | 231 ++++++
> drivers/char/lrng/lrng_testing.c | 689 +++++++++++++++++
> include/crypto/drbg.h | 7 +
> .../crypto/internal}/jitterentropy.h | 3 +
> include/linux/lrng.h | 81 ++
> 32 files changed, 6777 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
>
> --
> 2.31.1

Thanks,
Al