Messages in this thread | | | From | Stephan Müller <> | Subject | [PATCH v35 00/13] /dev/random - a new approach | Date | Fri, 18 Sep 2020 11:47:36 +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.
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 operations.
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 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
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 component.
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
* 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 sampled.
* 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@gmail.com>
* move prototype of lrng_reset() to a spot in lrng_internal.h that is compiled unconditional as requested by kernel test robot <lkp@intel.com>
* correctly advance *ppos in DebugFS read function for testing interfaces preventing successive read operations
* fix __latent_entropy usage as reported by kernel test robot <lkp@intel.com>
* use compxch_release / smp_load_acquire to set NUMA pool as suggested by Eric Biggers
CC: "Eric W. Biederman" <ebiederm@xmission.com> CC: "Alexander E. Patrakov" <patrakov@gmail.com> CC: "Ahmed S. Darwish" <darwish.07@gmail.com> CC: "Theodore Y. Ts'o" <tytso@mit.edu> CC: Willy Tarreau <w@1wt.eu> CC: Matthew Garrett <mjg59@srcf.ucam.org> CC: Vito Caputo <vcaputo@pengaru.com> CC: Andreas Dilger <adilger.kernel@dilger.ca> CC: Jan Kara <jack@suse.cz> CC: Ray Strode <rstrode@redhat.com> CC: William Jon McCann <mccann@jhu.edu> CC: zhangjs <zachary@baishancloud.com> CC: Andy Lutomirski <luto@kernel.org> CC: Florian Weimer <fweimer@redhat.com> CC: Lennart Poettering <mzxreary@0pointer.de> CC: Nicolai Stange <nstange@suse.de> CC: Eric Biggers <ebiggers@kernel.org> Tested-by: Roman Drahtmüller <draht@schaltsekun.de> Tested-by: Marcelo Henrique Cerri <marcelo.cerri@canonical.com>
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 | 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
-- 2.26.2
| |