[PATCH] Kernel entropy rework

The attached patch set reworks the kernel entropy subsystem.

Why?  Goals:

1. Use cryptography primitives designed and vetted by cryptographers.
2. Be honest about entropy estimation.
3. Propagate full entropy as soon as possible.
4. Simplify the APIs.
5. Reduce overhead of rnd_add_data and cprng_strong.
6. Reduce side channels of HWRNG data and human input sources.
7. Improve visibility of operation with sysctl and event counters.

How?  General overview:

- Replace SHA-1/LFSR entropy pool by Keccak sponge.
- Replace global sample queue -- and global locks on cprng_strong --
  by per-CPU state.
- Eliminate counterproductive entropy `depletion' (though it is still
  available for testing, in very small code paths).

It's mostly ready but has a couple loose ends I'd like to tie up
before commit (marked with XXX below).  I tried a few times to split
it up into smaller incremental changes -- perhaps could have done the
core entropy subsystem first, and /dev/random and cprng_strong next
separately -- but after spending a while on this, I'm not sure it's
worthwhile to split up much more.

Comments and testing welcome!


What?  Details:

1. Use cryptography primitives designed and vetted by cryptographers.

   => WHAT WE DO NOW: A kind of wacky composition of LFSR with SHA-1
      feedback that was cooked up in the '90s, without clear analysis
      by cryptographers.

   => WHAT THE PATCH DOES: Keccak sponge in duplex mode.  The Keccak
      sponge is the basis for the SHA-3 standard; the duplex mode is a
      simple and well-understood way to feed input in and extract
      output that is also used for authenticated encryption and other
      purposes.  See, e.g.,

         Guido Bertoni, Joan Daemen, Michael Peeters, and Gilles van
         Assche, `Duplexing the Sponge: Single-Pass Authenticated
         Encryption and Other Applications', in Ali Miri and Serge
         Vaudenay, eds., Selected Areas in Cryptography---SAC 2011,
         Springer LNCS 7118, pp. 320--337.
         https://link.springer.com/chapter/10.1007/978-3-642-28496-0_19
         https://keccak.team/files/SpongeDuplex.pdf

      Everything works with 256-bit intermediate quantities in order
      to guarantee a standard 128-bit security level even against
      multi-target quantum adversaries and modest cryptanalytic
      advances.

2. Be honest about entropy estimation.

   => WHAT WE DO NOW: Feed samples from entropy sources into an
      extremely simple-minded algorithm to fit parameters for an
      extremely simple-minded model of the sampling process in the
      underlying device in order to derive a heuristic estimate of the
      sampling process's entropy as we feed samples into the pool.

      This model bears no resemblance to the sampling process of the
      actual device, and so is essentially designed to guarantee
      overestimating the entropy of the system.  And by feeding the
      same samples into the entropy estimation algorithm and into the
      entropy pool, we are almost certainly leaking information
      through timing side channels too.

   => WHAT THE PATCH DOES: Leaves it entirely to the driver to specify
      the entropy of the sampling process based on knowledge of how
      the device works.

      - For (e.g.) keyboard interrupt and network packet timings, this
        is zero, because an adversary can cause events to happen with
        timing that leads to predictable samples entering the pool.

      - For alleged hardware RNGs, it's up to the author of the driver
        to do science on the device (and identify reasonable health
        checks for the device based on its physics and engineering).

      Of course, this means that the kernel will now believe it has
      much lower entropy than it did before.  This is more honest, but
      may lead to usability issues particularly on platforms that do
      not have hardware RNGs.  To mitigate this:

      - I recently fixed two long-standing bugs in rndctl(8) whereby

        (a) it would erase, rather than update, the seed file at boot;
        and
        (b) it would always store an entropy estimate of zero in the
            seed file.

        Now it updates the file at boot (I also taught /etc/security
        to update the seed), and records the system's entropy in the
        file, so you don't lose all entropy if the system crashes
        after boot.

        This means it should be enough to, e.g., save a seed file with
        rndctl -S on your laptop and copy it onto an appliance that
        has an otherwise pristine OS image flashed onto it -- even if
        the appliance has no hardware RNG of its own.

      - I implemented a driver for the alleged TRNG in the Allwinner
        Crypto Engine found on sun8i platforms like the Pinebook, and
        would be happy to help anyone else do similarly for other
        hardware RNGs.

      - Entropy `depletion' -- which is widely understood to make no
        sense if you're using /dev/random output for keys in modern
        cryptography -- no longer happens by default, so you only need
        to wait early at boot.  (But `depletion' is supported by a
        handful of very small code paths which can be re-enabled by
        setting sysctl kern.entropy.depletion=1 in order to facilitate
        testing.)

3. Propagate full entropy as soon as possible.

   => WHAT WE DO NOW: Stash samples into buffers that can sit in a
      queue for unbounded durations even if the samples happen early
      at boot when we need entropy ASAP.  (To compensate for this,
      systems like rump pile on as much data as they can to make sure
      it gets through the buffering, when 256 bits should always be
      enough.)

   => WHAT THE PATCH DOES: Notifies all waiters the moment full
      entropy is attained early at boot, while avoiding the overhead
      afterward and imposing rate limits when we've already attained
      full entropy afterward so that interrupt storms don't eat all
      the CPU entering data.

      The `overhead' here arises because samples are buffered only on
      the local CPU, not in a global queue; this requires a cross-call
      to consolidate the per-CPU entropy.  The patch also adds a
      sysctl node kern.entropy.consolidate that you can write to in
      order to trigger consolidation of entropy from all CPUs (at most
      once per second).

4. Simplify the APIs.

   => WHAT WE DO NOW:
      - Various bookkeeping, on which notification decisions are
        based, is mixed up with the cryptography in rndpool(9).
      - Bookkeeping and wakeup notification is split across
        kern_rndq.c and kern_rndpool.c, and hasn't always been
        consistent.
      - A system of threaded callbacks, rndsink(9), serves to notify
        other subsystems when reseeding is appropriate, except it's
        only used in subr_cprng.c.
      - An MI cpu_rng API that is and has only ever been implemented
        on x86, and is used internally for an x86-only cpu_earlyrng
        which works only on x86 machines with RDRAND/RDSEED or VIA C3
        RNG.

   => WHAT THE PATCH DOES:
      - Puts all the cryptography (along with deterministic
        known-answer test vectors) into libkern/entpool.c.  (This could
        also be used for other purposes as a simple reseedable PRNG,
        if we didn't already use NIST Hash_DRBG.)
      - Puts all the bookkeeping and wakeup notifications together
        into kern/kern_entropy.c.
      - Replaces the rndsink(9) API by a single entropy_epoch()
        function to return a generation number that changes whenever
        the system warrants reseeding, and is never 0 so you can
        safely use that to mean unseeded.
      - . Keeps the RDRAND/RDSEED and VIA C3 logic under x86.
          -> If we find more CPUs have anything that works similarly,
             and the logic factors out meaningfully, then we can make
             an MI API for it, but at the moment an MI API isn't
             really helpful.
        . Makes the entropy pool available sooner.
        . Uses the entropy pool instead of cpu_earlyrng.
          -> In principle, this could use the on-disk seed, although
             at the moment that is loaded too late.

5. Reduce overhead of rnd_add_data and cprng_strong.

   => WHAT WE DO NOW:

      - Every rnd_add_data takes a global lock to serialize access to
        the sample buffers.
        => If I recall correctly, this has been observed to be a
           bottleneck in high-volume network interfaces.

      - Every call to cprng_strong takes a global lock to draw from a
        global NIST Hash_DRBG.

   => WHAT THE PATCH DOES:

      - Samples are always entered into a per-CPU pool normally, and
        only affect the global pool immediately early at boot.
        Samples can be entered in one of two ways:

        (a) xor sample data into sponge and truncate if it's too long
        (b) xor sample data into sponge and permute sponge as needed

        Option (a) is done for samples entered from interrupt context,
        to avoid doing any cryptography in interrupt context; then a
        softint is scheduled to permute the sponge so there's room for
        more data.

        Option (b) is done for samples entered from thread context,
        and during option (b), new samples from interrupt context are
        simply ignored -- without blocking interrupts.

        I haven't measured under high network load, but I expect this
        should significantly reduce the cost of rnd_add_data so that
        it should no longer be a bottleneck for just about anything
        doing interrupts.

      - cprng_strong is a per-CPU NIST Hash_DRBG, using a simpler
        version of the logic we already had in dev/rndpseudo.c for a
        per-CPU /dev/urandom cprng_strong.

6. Reduce side channels of HWRNG data and human input sources.

   => WHAT WE DO NOW:

      - Run all RND_TYPE_RNG data through software implementing the
        FIPS 140-1 statistical tests -- monobit, poker, runs.  (These
        tests were all rescinded with strikethrough in FIPS 140-2 in
        2001 and completely eliminated in FIPS 140-3 in 2019.)  The
        software is full of secret-dependent branches and array
        indices and therefore likely has side channels.

      - Wake when any sample changes the entropy estimate.  This can
        happen immediately after a keystroke, for example; it is
        limited only by the sample buffering.

   => WHAT THE PATCH DOES:

      - Provide an API for a constant-time repetition count test, from
        NIST SP800-90B, to be used explicitly in a device driver if it
        is appropriate.  This has high statistical power to detect
        known failure modes of widespread hardware RNGs, such as the
        recent AMD bug which makes RDSEED return all bits 1, and much
        simpler to implement in constant time.

        (XXX I'm not set on the rngreptest API here.  It is plausible
        that there are hardware RNGs with failure modes that are
        detected with high statistical power by the FIPS 140-1
        monobit/poker/runs tests but not by the the NIST SP800-90B
        repetition count test.  It is sort of nice that in the status
        quo, the existing FIPS 140-1 tests report, e.g., that the
        sun8icrypto TRNG is not very uniform when you rnd_add_data --
        but to be meaningful, RNG health tests really have to depend
        on the physics and engineering of the underlying device and
        its realistic failure modes; sun8icrypto's TRNG can have
        entropy even if the distribution is not uniform.)

      - Rate-limits wakeups to happen at most once per second if
        explicitly requested by the operator, and once per minute
        otherwise, after the system has attained full entropy for the
        first time.

7. Improve visibility of operation with sysctl and event counters.

   => WHAT WE DO NOW: Print some warnings if statistical tests fail,
      and sometimes block on reads from /dev/random, unless you enable
      the RND_VERBOSE kernel option in which case the kernel output is
      much more verbose (but it can't be done dynamically).

   => WHAT THE PATCH DOES: Exposes several sysctl nodes and event
      counters:

         kern.entropy.needed - how much entropy is needed, in bits;
           256 at boot, 0 when we have reached full entropy.

         kern.entropy.pending - how much entropy is pending in CPUs,
           if the system is not at full entropy; updated at most once
           per minute when the system has full entropy, so that it
           doesn't serve as a side channel for events

         kern.entropy.epoch - generation number that increments
           whenever the system warrants reseeding, never set to 0
           (userland programs could consult this too to decide when to
           reseed from /dev/urandom)

      The sysctls -- and event counters -- that are affected by timing
      of samples are rate-limited to change once per minute, so they
      are not useful, e.g., to find typing rate.

      This should make it much easier for operators to diagnose why
      their system is not reaching full entropy if it seems to get
      stuck at boot in a predictable state.

      (XXX Exception: The softint counter is not rate-limited, so it
      could serve as a reasonably high-precision side channel for some
      types of keyboard event timings.  This warrants reconsideration,
      and the event counters should be more generally reviewed again
      for their role as potential side channels.)