CVS log for src/sys/kern/Attic/kern_rndpool.c

Up to [cvs.NetBSD.org] / src / sys / kern

Request diff between arbitrary revisions

Keyword substitution: kv
Default branch: MAIN

Rewrite entropy subsystem.

Primary 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.

Caveat: rngtest is no longer used generically for RND_TYPE_RNG
rndsources.  Hardware RNG devices should have hardware-specific
health tests.  For example, checking for two repeated 256-bit outputs
works to detect AMD's 2019 RDRAND bug.  Not all hardware RNGs are
necessarily designed to produce exactly uniform output.

ENTROPY POOL

- A Keccak sponge, with test vectors, replaces the old LFSR/SHA-1
  kludge as the cryptographic primitive.

- `Entropy depletion' is available for testing purposes with a sysctl
  knob kern.entropy.depletion; otherwise it is disabled, and once the
  system reaches full entropy it is assumed to stay there as far as
  modern cryptography is concerned.

- No `entropy estimation' based on sample values.  Such `entropy
  estimation' is a contradiction in terms, dishonest to users, and a
  potential source of side channels.  It is the responsibility of the
  driver author to study the entropy of the process that generates
  the samples.

- Per-CPU gathering pools avoid contention on a global queue.

- Entropy is occasionally consolidated into global pool -- as soon as
  it's ready, if we've never reached full entropy, and with a rate
  limit afterward.  Operators can force consolidation now by running
  sysctl -w kern.entropy.consolidate=1.

- rndsink(9) API has been replaced by an epoch counter which changes
  whenever entropy is consolidated into the global pool.
  . Usage: Cache entropy_epoch() when you seed.  If entropy_epoch()
    has changed when you're about to use whatever you seeded, reseed.
  . Epoch is never zero, so initialize cache to 0 if you want to reseed
    on first use.
  . Epoch is -1 iff we have never reached full entropy -- in other
    words, the old rnd_initial_entropy is (entropy_epoch() != -1) --
    but it is better if you check for changes rather than for -1, so
    that if the system estimated its own entropy incorrectly, entropy
    consolidation has the opportunity to prevent future compromise.

- Sysctls and event counters provide operator visibility into what's
  happening:
  . kern.entropy.needed - bits of entropy short of full entropy
  . kern.entropy.pending - bits known to be pending in per-CPU pools,
    can be consolidated with sysctl -w kern.entropy.consolidate=1
  . kern.entropy.epoch - number of times consolidation has happened,
    never 0, and -1 iff we have never reached full entropy

CPRNG_STRONG

- A cprng_strong instance is now a collection of per-CPU NIST
  Hash_DRBGs.  There are only two in the system: user_cprng for
  /dev/urandom and sysctl kern.?random, and kern_cprng for kernel
  users which may need to operate in interrupt context up to IPL_VM.

  (Calling cprng_strong in interrupt context does not strike me as a
  particularly good idea, so I added an event counter to see whether
  anything actually does.)

- Event counters provide operator visibility into when reseeding
  happens.

INTEL RDRAND/RDSEED, VIA C3 RNG (CPU_RNG)

- Unwired for now; will be rewired in a subsequent commit.

Sync with HEAD

- add or adjust /* FALLTHROUGH */ where appropriate
- add __unreachable() after functions that can return but won't in
  this case, and thus can't be marked __dead easily

Sync with HEAD

Resolve a couple of conflicts (result of the uimin/uimax changes)

Rename min/max -> uimin/uimax for better honesty.

These functions are defined on unsigned int.  The generic name
min/max should not silently truncate to 32 bits on 64-bit systems.
This is purely a name change -- no functional change intended.

HOWEVER!  Some subsystems have

	#define min(a, b)	((a) < (b) ? (a) : (b))
	#define max(a, b)	((a) > (b) ? (a) : (b))

even though our standard name for that is MIN/MAX.  Although these
may invite multiple evaluation bugs, these do _not_ cause integer
truncation.

To avoid `fixing' these cases, I first changed the name in libkern,
and then compile-tested every file where min/max occurred in order to
confirm that it failed -- and thus confirm that nothing shadowed
min/max -- before changing it.

I have left a handful of bootloaders that are too annoying to
compile-test, and some dead code:

cobalt ews4800mips hp300 hppa ia64 luna68k vax
acorn32/if_ie.c (not included in any kernels)
macppc/if_gm.c (superseded by gem(4))

It should be easy to fix the fallout once identified -- this way of
doing things fails safe, and the goal here, after all, is to _avoid_
silent integer truncations, not introduce them.

Maybe one day we can reintroduce min/max as type-generic things that
never silently truncate.  But we should avoid doing that for a while,
so that existing code has a chance to be detected by the compiler for
conversion to uimin/uimax without changing the semantics until we can
properly audit it all.  (Who knows, maybe in some cases integer
truncation is actually intended!)

update from HEAD

Sync with HEAD

Turn a kassert into a more appropriately placed ctassert.

Sort includes.

Fix typo expliict -> explicit.

Use explicit_memset.

Omit needless declaration.

Cull another unused rndpool routine.

Cull some unused rndpool routines.

More rnd.h user cleanup.

Omit needless state.

Pull up following revision(s) (requested by riastradh in ticket #1118):
	sys/kern/kern_rndq.c: revision 1.27
	sys/kern/kern_rndpool.c: revision 1.7
buf is not guaranteed to be aligned; don't *(uint32_t *) it in kern_rndq.c.
done is not guaranteed to be aligned; don't *(uint32_t *) it in kern_rndpool.c.

Pull up following revision(s) (requested by riastradh in ticket #1118):
	sys/kern/kern_rndq.c: revision 1.27
	sys/kern/kern_rndpool.c: revision 1.7
buf is not guaranteed to be aligned; don't *(uint32_t *) it in kern_rndq.c.
done is not guaranteed to be aligned; don't *(uint32_t *) it in kern_rndpool.c.

Pull up following revision(s) (requested by riastradh in ticket #1118):
	sys/kern/kern_rndq.c: revision 1.27
	sys/kern/kern_rndpool.c: revision 1.7
buf is not guaranteed to be aligned; don't *(uint32_t *) it in kern_rndq.c.
done is not guaranteed to be aligned; don't *(uint32_t *) it in kern_rndpool.c.

Rebase to HEAD as of a few days ago.

Pull up following revision(s) (requested by riastradh in ticket #4):
	sys/kern/kern_rndq.c: revision 1.27
	sys/kern/kern_rndpool.c: revision 1.7
buf is not guaranteed to be aligned; don't *(uint32_t *) it.
done is not guaranteed to be aligned; don't *(uint32_t *) it.

buf is not guaranteed to be aligned; don't *(uint32_t *) it.

Merge tls-earlyentropy branch into HEAD.

Fix rndctl accounting.

sync with head.

for a reference, the tree before this commit was tagged
as yamt-pagecache-tag8.

this commit was splitted into small chunks to avoid
a limitation of cvs.  ("Protocol error: too many arguments")

sync with head

Entropy estimation changes:

1) Avoid wraparound problems with delta estimator by making estimation
   framework 64-bit.

2) Adjust rnd_counter to always return a 64-bit value, accordingly.

3) Make delta estimator generic and create two instances: delta-time and
   delta-value.

4) Add LZF estimator -- used mostly to protect us against injection of
   bulk data we think is random but is really constant.

5) Allow value and time estimation/collection to be controlled separately.

6) Expose estimator performance to userspace.

Fix rnd_add_* to conform to manual page: allow addition of entropy
with NULL source.

resync from head

Correct use of entropy estimate when data are extracted from the pool.

The "threshold" value was being inappropriately used to limit how many
bytes could be output even after the estimator said enough bytes had
been put in to meet our minimum security guarantee.

This fixes a panic observed with the automatic test harness and by
msaitoh, where it was not possible to extract the full estimate's worth
of bytes even holding the pool lock across the estimate and extract
calls.

Convert the entropy pool framework from pseudo-callout-driven to
soft interrupt driven operation.

Add a polling mode of operation -- now we can ask hardware random number
generators to top us up just when we need it (bcm2835_rng and amdpm
converted as examples).

Fix a stall noticed with repeated reads from /dev/random while testing.

sync with head.

sync to latest -current.

Pull up following revision(s) (requested by tls in ticket #190):
	sys/sys/rnd.h: revision 1.31
	sys/sys/rnd.h: revision 1.32
	sys/sys/cprng.h: revision 1.5
	sys/kern/subr_cprng.c: revision 1.8
	share/man/man4/rnd.4: revision 1.19
	sys/kern/kern_rndq.c: revision 1.3
	sys/dev/rndpseudo.c: revision 1.8
	sys/dev/rndpseudo.c: revision 1.9
	sys/kern/kern_rndpool.c: revision 1.2
Address multiple problems with rnd(4)/cprng(9):
1) Add a per-cpu CPRNG to handle short reads from /dev/urandom so that
   programs like perl don't drain the entropy pool dry by repeatedly
   opening, reading 4 bytes, closing.
2) Really fix the locking around reseeds and destroys.
3) Fix the opportunistic-reseed strategy so it actually works, reseeding
   existing RNGs once each (as they are used, so idle RNGs don't get
   reseeded) until the pool is half empty or newly full again.
Fix a bug and a compilation problem.  Bug: spin mutexes don't have owners,
so KASSERT(!mutex_owned()) shouldn't be used to assert that the current
LWP does not have the mutex.  Compilation problem: explicitly include
sys/mutex.h from rnd.h so evbarm builds again.

Address multiple problems with rnd(4)/cprng(9):

1) Add a per-cpu CPRNG to handle short reads from /dev/urandom so that
   programs like perl don't drain the entropy pool dry by repeatedly
   opening, reading 4 bytes, closing.

2) Really fix the locking around reseeds and destroys.

3) Fix the opportunistic-reseed strategy so it actually works, reseeding
   existing RNGs once each (as they are used, so idle RNGs don't get
   reseeded) until the pool is half empty or newly full again.

sync with head

merge to -current.

file kern_rndpool.c was added on branch yamt-pagecache on 2012-04-17 00:08:25 +0000

file kern_rndpool.c was added on branch jmcneill-usbmp on 2012-02-18 07:35:31 +0000

Entropy-pool implementation move and cleanup.

1) Move core entropy-pool code and source/sink/sample management code
   to sys/kern from sys/dev.

2) Remove use of NRND as test for presence of entropy-pool code throughout
   source tree.

3) Remove use of RND_ENABLED in device drivers as microoptimization to
   avoid expensive operations on disabled entropy sources; make the
   rnd_add calls do this directly so all callers benefit.

4) Fix bug in recent rnd_add_data()/rnd_add_uint32() changes that might
   have lead to slight entropy overestimation for some sources.

5) Add new source types for environmental sensors, power sensors, VM
   system events, and skew between clocks, with a sample implementation
   for each.

ok releng to go in before the branch due to the difficulty of later
pullup (widespread #ifdef removal and moved files).  Tested with release
builds on amd64 and evbarm and live testing on amd64.