Re: [PATCH] Kernel entropy rework

[Taylor R Campbell <campbell+netbsd-tech-kern%mumble.net@localhost>]

> Date: Thu, 26 Dec 2019 20:16:20 +0000
> From: maya%NetBSD.org@localhost
> 
> On Sat, Dec 21, 2019 at 10:08:20PM +0000, Taylor R Campbell wrote:
> > - Replace SHA-1/LFSR entropy pool by Keccak sponge.
> 
> The peanut gallery would like to inquire if you have a secret BLAKE2
> version of this patch ready.

It's a good question, but I don't have a secret BLAKE2 version of this
patch ready.

The reason I chose Keccak is that there is a published well-understood
confidence-inspiring construction for alternately consuming inputs
(not necessarily uniformly distributed!) and generating outputs using
a permutation like Keccak -- namely a sponge duplex[1][2].  These are
exactly the operations we need for an entropy pool: enter samples,
extract key material.

(Our `enter' is `feed' from the paper; our `extract' is `fetch, then
forget', so that we provide key erasure (or `backtracking resistance'
or `forward secrecy') at every request.)

All of the logic is generic in terms of a permutation.  It currently
uses Keccak-p[1600,24], the same permutation as SHA-3 uses, but you
could drop in a different permutation if you wanted, like Gimli (which
I drafted for fun).  So what about BLAKE2?

Although BLAKE2 was derived from a permutation-based design, ChaCha,
the ChaCha permutation has various symmetries that have to be broken
by inputs beyond the adversary's control -- the constant words -- and
in BLAKE2 the fixed permutation was adapted into a keyed permutation,
i.e. a block cipher, also requiring a constant to break symmetries.
So neither one can just be dropped into the duplex construction
without analysis.

One could certainly cook up a scheme based on BLAKE2, and it might
provide better software performance -- in principle, anyway, if we
could do enough vectorization in the kernel! -- but:

(a) While BLAKE2 inspires confidence for what it does, there's no
    _existing_ published well-understood confidence-inspiring
    construction based on BLAKE2 -- or the BLAKE2 block cipher, or the
    ChaCha permutation -- like a sponge duplex with the two operations
    we need, entropy_enter and entropy_extract.  (Not that I know of,
    anyway!)

(b) The performance of entropy_enter/entropy_extract is not critical:

    - The input samples are usually low-volume -- even during high
      interrupt activity, the _cryptography_ operations are limited to
      when softints can get a word in edgewise; additional samples are
      just discarded until then, to prevent cryptography operations
      from adding to interrupt latency.

    - The output is used only to draw a key for a PRNG, namely NIST
      Hash_DRBG with SHA-256 (formerly NIST CTR_DRBG with AES-128),
      which is what generates the data you read from /dev/urandom, and
      I'm not changing that algorithm at the moment.

    So it'd be rather surprising if the cryptography in the entropy
    pool itself turned out to be a bottleneck.

Since the entropy pool is basically the single most security-critical
piece of infrastructure for any cryptography such as you need to
safely use the modern internet, and since it's not likely to be
performance-critical, I figured that it's less important that it be
potentially vectorizable to maximize throughput in software like
BLAKE2 -- and much more important that it be well-understood and
inspire confidence like the sponge duplex construction with Keccak
does.


1. Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche,
   `Sponge-Based Pseudo-Random Number Generators', in Stefan Mangard
   and François-Xavier Standaert, eds., Cryptographic Hardware and
   Embedded Systems CHES 2010, Springer LNCS 6225, pp. 33--47.
   https://link.springer.com/chapter/10.1007/978-3-642-15031-9_3
   https://keccak.team/files/SpongePRNG.pdf

2. Guido Bertoni, Joan Daemen, Michaël 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