mbox series

[v31,00/12] /dev/random - a new approach with full SP800-90B

Message ID 2050754.Mh6RI2rZIc@positron.chronox.de (mailing list archive)
Headers show
Series /dev/random - a new approach with full SP800-90B | expand

Message

Stephan Mueller July 13, 2020, 6:17 a.m. UTC
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):

* Port to v5.8-rc5 including updated initialization of static Jitter RNG
  instance

* Add latent_entropy GCC compiler plugin annotations

* Add test interfaces to validate performance of interrupt handler
  and time stamp concatenation

* Fix memleak during rmmod lrng_drbg.ko which was missing deallocation
  of cipher handles

* Remove seeding from CPU noise sources for get_random_u64/u32 compliant
  to random.c

* Use of arch_get_random_seed_long_early / arch_get_random_long_early for
  initialization of LFSR state and ChaCha20 DRNG state.

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

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>
Tested-by: Roman Drahtmüller <draht@schaltsekun.de>
Tested-by: Marcelo Henrique Cerri <marcelo.cerri@canonical.com>

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                     | 249 +++++++
 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             | 285 ++++++++
 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             | 318 +++++++++
 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             | 437 ++++++++++++
 drivers/char/lrng/lrng_sw_noise.c             | 125 ++++
 drivers/char/lrng/lrng_sw_noise.h             |  57 ++
 drivers/char/lrng/lrng_switch.c               | 189 +++++
 drivers/char/lrng/lrng_testing.c              | 393 +++++++++++
 include/crypto/drbg.h                         |   7 +
 .../crypto/internal}/jitterentropy.h          |   3 +
 include/linux/lrng.h                          |  63 ++
 31 files changed, 5597 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

Comments

Pavel Machek July 28, 2020, 8:40 p.m. UTC | #1
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.

That sounds good.. maybe too good. Where does LRNG get the entropy? That is the
part that should be carefully documented..

									Pavel
Stephan Mueller July 29, 2020, 7:15 a.m. UTC | #2
Am Dienstag, 28. Juli 2020, 22:40:44 CEST schrieb Pavel Machek:

Hi Pavel,

> 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.
> 
> That sounds good.. maybe too good. Where does LRNG get the entropy? That is
> the part that should be carefully documented..
> 
> 									Pavel

The entire description of the LRNG is given in [1].

[1] section 2.1 outlines the general architecture specifying that there are 
currently 3 noise sources. Per default, the interrupt-based noise source is 
the main source.

Section 2.4 outlines the details of the interrupt noise source handling. The 
key now is unlike the existing implementation that there is no separate block/
HID noise collection because they are "just" derivatives of the interrupt 
noise source which would imply that noise events are double credited with 
entropy. This allows for a massively higher valuation of the entropy rate that 
exists in interrupt events.

To support the design, a large scale noise source analysis is performed in 
chapter 3 [1]. Specifically sections 3.2.3 and 3.2.4 provide quantitative 
statements which are further analyzed in subsequent sections. This includes 
reboot tests as well as runtime tests.

[1] appendix C performs these measurements on other CPU architectures, 
including very small environments which could be expected to have too little 
entropy (specifically the first listed ARM system mentioned there and the MIPS 
system are older embedded devices that yet show sufficient entropy). Also, the 
entropy available in virtual environments is shown in appendix C.

The tools perform the aforementioned measurements are provided with the 
enabling of CONFIG_LRNG_RAW_ENTROPY supported by [2]. This allows everybody to 
re-perform the analysis on the system of his choice.

Also, the entire entropy assessment of the LRNG is supported by the entropy 
analysis of the existing implementation in [3]. Specifically section 6.1 shows 
that the existing implementation has much more entropy available in the 
interrupt events than it credits. Yet, due to the design of the existing 
implementation with the fast pool (for which we have no assessment how much 
entropy is lost by it) and the fact of double counting of entropy with HID/
block devices, the massive underestimation of existing entropy with the 
existing /dev/random implementation is warranted.

Lastly, [4] performs the entropy assessment of the existing /dev/random 
implementation in virtualized environments showing that still sufficient 
entropy is available in interrupt events supporting the approach taken in the 
LRNG. Writing the assessment of [4] was the initial trigger point for me to 
start the LRNG implementation.

The second noise source that, however, is credited much less entropy is 
documented in [5] including its entropy assessment.

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

[2] https://chronox.de/lrng/lrng-tests-20200415.tar.xz

[3] https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publications/Studies/
LinuxRNG/LinuxRNG_EN.pdf?__blob=publicationFile

[4] https://www.bsi.bund.de/SharedDocs/Downloads/DE/BSI/Publikationen/Studien/
ZufallinVMS/Randomness-in-VMs.pdf?__blob=publicationFile

[5] https://chronox.de/jent/doc/CPU-Jitter-NPTRNG.pdf

Ciao
Stephan