Hi all,
first of all, my apologies for the patch bomb following up in reply to this
mail here -- it's not meant to receive any serious review at all, but only
to support the discussion I'm hoping to get going.
As some of you might already be aware of, all new submissions for FIPS
certification will be required to comply with NIST SP800-90B from Nov 7th
on ([1], sec. 7.18 "Entropy Estimation and Compliance with SP 800-90B").
For reference: broadly speaking, NIST SP800-90B is about noise sources,
SP800-90A about the DRBG algorithms stacked on top and SP800-90C about how
everything is supposed to be glued together. The main requirements from
SP800-90B are
- no correlations between different noise sources,
- to continuously run certain health tests on a noise source's output and
- to provide an interface enabling access to the raw noise samples for
validation purposes.
To my knowledge, all SP800-90B compliant noise sources available on Linux
today are either based on the Jitter RNG one way or another or on
architectural RNGs like e.g. x86's RDSEED or arm64's RNDRRS. Currently,
there's an in-kernel Jitter RNG implementation getting registered (c.f.
crypto/drbg.c, (*)) with the Crypto RNG API, which is also accessible from
userspace via AF_ALG. The userspace haveged ([2]) or jitterentropy
integrations ([3]) are worth mentioning in this context, too. So in
summary, I think that for the in-kernel entropy consumers falling under the
scope of FIPS, the currently only way to stay compliant would be to draw it
from said Crypto API RNG. For userspace applications there's the additional
option to invoke haveged and alike.
OTOH, CPU jitter based techniques are not uncontroversial ([4]). In any
case, it would certainly be a good idea to mix (xor or whatever) any jitter
output with entropy obtained from /dev/random (**). If I'm not mistaken,
the mentioned Crypto API RNG implementation (crypto/drbg.c) follows exactly
this approach, but doesn't enforce it yet: there's no
wait_for_random_bytes() and early DRBG invocations could in principle run
on seeds dominated entirely by jitterentropy. However, this can probably
get sorted quite easily and thus, one reasonable way towards maintaining
FIPS resp. SP800-90 compliance would be to
- make crypto/drbg.c invoke wait_for_random_bytes(),
- make all relevant in-kernel consumers to draw their random numbers from
the Crypto RNG API, if not already the case and
- convert all relevant userspace to use a SP800-90B conforming Jitter RNG
style noise source for compliance reasons, either by invoking the
kernel's Crypto RNG API or by diffent means, and mix that with
/dev/random.
Even though this would probably be feasible, I'm not sure that giving up on
/dev/random being the primary, well established source of randomness in
favor of each and every userspace crypto library rolling its own entropy
collection scheme is necessarily the best solution (it might very well be
though).
An obvious alternative would be to make /dev/random conform to SP800-90B.
Stephan Müller posted his "LRNG" patchset ([5]), in which he proposed to
introduce a second, independent implementation aiming at SP800-90[A-C]
conformance. However, it's in the 35th iteration now and my impression is
that there's hardly any discussion happening around this for quite a while
now. I haven't followed the earlier development, but I can imagine several
reasons for that:
- people are not really interested in FIPS or even questioning the whole
concept in the first place (c.f. Theodore Ts'o remarks on this topic
at [6]),
- potential reviewers got merely discouraged by the diffstat or
- people dislike the approach of having two competing implementations for
what is basically the same functionality in the kernel.
In either case, I figured it might perhaps help further discussion to
provide at least a rough idea of how bad the existing /dev/random
implementation would get cluttered when worked towards SP800-90B
compliance. So I implemented the required health tests for the interrupt
noise source -- the resulting patches can be found in reply to this mail.
I'd like to stress(!) that this should really only be considered a first
step and that there would still be a long way towards a complete solution;
known open items are listed below. Also, I'm fully aware that making those
continuous health tests block the best effort primary_crng reseeds upon
failure is a ridiculous thing to do -- that's again meant for demonstration
purposes only, c.f. the commit log from the next to last patch. Anyway,
those of you who are interested in some more details beyond the mere
diffstat can find them after the list of references below.
In summary, I can imagine three feasible ways towards SP800-90 compliance:
1.) Put the burden on consumers. For in-kernel users this would mean
conversion to the Jitter backed Crypto RNG API, in case that hasn't
happened yet. Userspace is free to use any approved Jitter based
mechanism for compliance reasons, but is encouraged to mix that with
/dev/random.
2.) Merge Stephan's LRNG. Users/distros would have to decide between either
of the two competing implementations at kernel config time.
3.) Develop the existing /dev/random towards compliance, ideally w/o
affecting !fips_enabled users too much. This would likely require some
redundancies as well as some atrocities imposed by the specs.
I'm looking forward to hearing your opinions and suggestions! In case you
happen to know of anybody who's not on CC but might potentially be
interested in FIPS, I'd highly appreciate it if you could point him/her to
this thread. The usual suspects are probably (enterprise?) distro folks,
but there might be others I haven't thought of.
Many thanks for your time!
Nicolai
(*) That's an oversimplification for the sake of brevity: actually
SP800-90A DRBGs stacked on top of the SP800-90B conforming
jitterentropy source get registered with the Crypto API.
(**) "/dev/random" is used as a synonym for everything related to
drivers/char/random.c throughout this mail.
[1] https://csrc.nist.gov/csrc/media/projects/cryptographic-module-validation-program/documents/fips140-2/fips1402ig.pdf
[2] http://www.issihosts.com/haveged/
[3] http://www.chronox.de/jent/doc/CPU-Jitter-NPTRNG.html
c.f. appendices C-E
[4] https://lwn.net/Articles/642166/
[5] https://lkml.kernel.org/r/[email protected]
[6] https://lkml.kernel.org/r/[email protected]
https://lkml.kernel.org/r/[email protected]
[7] https://lkml.kernel.org/r/[email protected]
As promised above, some more details on the RFC series sent alongside
follow. The primary goal was to implement that health test functionality as
required by SP800-90B for the existing drivers/char/random.c without
affecting !fips_enabled users in any way. As outlined below, I failed quite
miserably as far as performance is concerned, but that shouldn't be
something which cannot get rectified. Kernel version v5.9-rc4 had been used
as a basis. The series can be logically subdivided into the following
parts:
- [1-5]: Preparatory cleanup.
- [6-17]: Implement support for deferring entropy credit dispatch to the
global balance to long after the corresponding pool mixing operation has
taken place. Needed for "holding back" entropy until the health tests
have finished on the latest pending batch of samples.
- [18-21]: Move arch_get_random_{seed_,}long() out of the interrupt path.
Needed to adhere to how SP800-90C expects multiple noise source to get
combined, but is also worthwhile on its own from a performance POV.
- [22-23]: Don't award entropy to non-SP800-90B conforming architectural
RNGs if fips_enabled is set.
- [24]: Move rand_initialize() to after time_init(). A "fix" for what is
currently a non-issue, but it's a prerequisite for the subsequent patch.
- [25]: Detect cycle counter resolution, subsequently needed for making a
per-IRQ entropy assessment.
- [26-28]: Follow Stephan's LRNG approach in how much entropy gets
awarded to what: a lot more than before to add_interrupt_randomness(),
none to add_{disk,input}_randomness() anymore.
- [29-33]: Introduce empty health test stubs and wire them up to
add_interrupt_randomness().
- [34-36]: Implement the Adaptive Proportion Test (APT) as specified by
SP800-90B and squeeze some more statistical power out of it.
- [37]: Implement SP800-90B's Repetition Count Test (RCT).
- [38-40]: Implement the startup tests, which are nothing but the
continuous tests (APT + RCT) run on a specified amount of samples at
boot time.
- [41]: Attempt to keep the system going in case the entropy estimate
had been too optimistic and the health tests keep failing.
As the health tests are run from interrupt context on each sample, a
performance measurement is due. To this end, I configured a Raspberry Pi 2B
(ARMv7 Cortex A7) to disable all peripherals, gated a
19.2 MHz / 2048 ~= 9.3 kHz clock signal to some edge triggered GPIO and
function_graph traced add_interrupt_randomness() for 10 min from a busybox
initramfs. Unfortunately, the results had been a bit disappointing: with
fips_enabled being unset there had been a runtime degradation of ~12.5% w/o
SMP and ~5% w/ SMP resp. on average merely due to the application of the
patches onto the v5.9-rc4 base. However, as the amount of work should not
have changed much and given that struct fast_pool still fits into a single
cacheline, I'm optimistic that this can get rectified by e.g. introducing
a static_key for fips_enabled and perhaps shuffling branches a bit such
that the !fips_enabled code becomes more linear. OTOH, the impact of
enabling the health tests by means of setting fips_enabled had not been so
dramatic: the observed increase in average add_interrupt_randomness()
runtimes had been 6% w/o SMP and 5% w/ SMP respectively.
Apart from those well controlled experiments on a RPi, I also did some
lax benchmarking on my x86 desktop (which has some Intel i9, IIRC).
More specifically, I simply didn't touch the system and ftraced
add_interrupt_randomness() for 15 mins. The number of captured events had
been about 2000 in each configuration. Here the add_interrupt_randomness()
performance improved greatly: from 4.3 us on average w/o the patches down
to 2.0 us with the patches applied and fips_enabled. However, I suppose
this gain was due to the removal of RDSEED from add_interrupt_randomness().
Indeed, when inspecting the distribution of add_interrupt_randomness()
runtimes on plain v5.9-rc4 more closely, it can be seen that there's a
good portion of events (about 1/4th) where add_interrupt_randomness() took
about 10us. So I think that this comparison isn't really a fair one...
To the best of my knowledge, these are the remaining open questions/items
towards full SP800-90[A-C] compliance:
- There's no (debugfs?) interface for accessing raw samples for validation
purposes yet. That would be doable though.
- try_to_generate_entropy() should probably get wired up to the health
tests as well. More or less straightfoward to implement, too.
- Diverting fast_pool contents into net_rand_state is not allowed (for a
related discussion on this topic see [7]).
- I've been told that SP800-90A is not a hard requirement yet, but I
suppose it will eventually become one. This would mean that the chacha20
RNG would have to get replaced by something approved for fips_enabled.
- The sequence of fast_pool -> input_pool -> extract_buf() operations
is to be considered a "non-vetted conditioning component" in SP800-90B
speak. It would follow that the output can't be estimated as having full
entropy, but only 0.999 of its length at max. (c.f. sec. 3.1.5.2). This
could be resolved by running a SP800-90A derivation function at CRNG
reseeding for fips_enabled. extract_buf(), which is already SHA1 based,
could perhaps be transformed into such one as well.
- The only mention of combining different noise sources I was able to find
had been in SP800-90C, sec. 5.3.4 ("Using Multiple Entropy Sources"):
it clearly states that the outputs have to be combined by concatenation.
add_hwgenerator_randomness() mixes into the same input_pool as
add_interrupt_randomness() though and I would expect that this isn't
allowed, independent of whether the noise source backing the former
is SP800-90B compliant or not. IIUC, Stephan solved this for his LRNG
by maintaing a separate pool for the hw generator.
- SP800-90A sets an upper bound on how many bits may be drawn from a
DRBG/crng before a reseed *must* take place ("reseed_interval"). In
principle that shouldn't matter much in practice, at least not with
CONFIG_NUMA: with reseed_interval == 2^32 bits, a single CRNG instance
would be allowed to hand out only 500MB worth of randomness before
reseeding, but a (single) numa crng chained to the primary_crng may
produce as much as 8PB before the latter must eventually get reseeded
from the input_pool. But AFAICT, a SP800-90A conforming implementation
would still have to provide provisions for a blocking extract_crng().
- It's entirely unclear to me whether support for "prediction resistance
requests" is optional. It would be a pity if it weren't, because IIUC
that would effectively imply a return to the former blocking_pool
behaviour, which is obviously a no-no.
Nicolai Stange (41):
random: remove dead code in credit_entropy_bits()
random: remove dead code for nbits < 0 in credit_entropy_bits()
random: prune dead assignment to entropy_bits in credit_entropy_bits()
random: drop 'reserved' parameter from extract_entropy()
random: don't reset entropy to zero on overflow
random: factor the exponential approximation in credit_entropy_bits()
out
random: let pool_entropy_delta() take nbits in units of
2^-ENTROPY_SHIFT
random: introduce __credit_entropy_bits_fast() for hot paths
random: protect ->entropy_count with the pool spinlock
random: implement support for delayed entropy dispatching
random: convert add_timer_randomness() to queued_entropy API
random: convert add_interrupt_randomness() to queued_entropy API
random: convert try_to_generate_entropy() to queued_entropy API
random: drop __credit_entropy_bits_fast()
random: convert add_hwgenerator_randomness() to queued_entropy API
random: convert random_ioctl() to queued_entropy API
random: drop credit_entropy_bits() and credit_entropy_bits_safe()
random: move arch_get_random_seed() calls in crng_reseed() into own
loop
random: reintroduce arch_has_random() + arch_has_random_seed()
random: provide min_crng_reseed_pool_entropy()
random: don't invoke arch_get_random_long() from
add_interrupt_randomness()
random: introduce arch_has_sp800_90b_random_seed()
random: don't award entropy to non-SP800-90B arch RNGs in FIPS mode
init: call time_init() before rand_initialize()
random: probe cycle counter resolution at initialization
random: implement support for evaluating larger fast_pool entropies
random: increase per-IRQ event entropy estimate if in FIPS mode
random: don't award entropy to disk + input events if in FIPS mode
random: move definition of struct queued_entropy and related API
upwards
random: add a queued_entropy instance to struct fast_pool
random: introduce struct health_test + health_test_reset()
placeholders
random: introduce health test stub and wire it up
random: make health_test_process() maintain the get_cycles() delta
random: implement the "Adaptive Proportion" NIST SP800-90B health test
random: improve the APT's statistical power
random: optimize the APT's presearch
random: implement the "Repetition Count" NIST SP800-90B health test
random: enable NIST SP800-90B startup tests
random: make the startup tests include muliple APT invocations
random: trigger startup health test on any failure of the health tests
random: lower per-IRQ entropy estimate upon health test failure
arch/arm64/include/asm/archrandom.h | 33 +-
arch/powerpc/include/asm/archrandom.h | 17 +-
arch/s390/include/asm/archrandom.h | 19 +-
arch/x86/include/asm/archrandom.h | 26 +-
drivers/char/random.c | 1141 ++++++++++++++++++++++---
include/linux/random.h | 17 +
init/main.c | 2 +-
7 files changed, 1101 insertions(+), 154 deletions(-)
--
SUSE Software Solutions Germany GmbH, Maxfeldstr. 5, 90409 Nürnberg, Germany
(HRB 36809, AG Nürnberg), GF: Felix Imendörffer
--
2.26.2
In an effort to drop credit_entropy_bits_safe() in favor of the new
queue_entropy()/dispatch_queued_entropy() API, convert random_ioctl() from
the former to the latter.
Implement two helpers:
- queue_entropy_bits_safe(), which checks the entropy passed from userspace
for extreme values in analogy to what credit_entropy_bits_safe() did
- discard_queue_entropy(), which is invoked from random_ioctly() to discard
the entropy queued prior to the write_pool() call in case the latter
fails.
Use them to convert the two call sites of credit_entropy_bits_safe()
in random_ioctl() to the new API.
As a side effect, the pool entropy watermark as tracked over the duration
of the write_pool() operation is now taken correctly taken into account
when calulating the amount of new entropy to dispatch to the pool based on
the latter's fill level.
Signed-off-by: Nicolai Stange <[email protected]>
---
drivers/char/random.c | 57 ++++++++++++++++++++++++++++++++++++++++---
1 file changed, 53 insertions(+), 4 deletions(-)
diff --git a/drivers/char/random.c b/drivers/char/random.c
index 78e65367ea86..03eadefabbca 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -737,7 +737,9 @@ struct queued_entropy {
* dispatch. However, any such sequence of invocations must eventually
* be followed by exactly one call to either of __dequeue_entropy(),
* __dispatch_queued_entropy_fast() or dispatch_queued_entropy()
- * when the actual pool mixing has completed.
+ * when the actual pool mixing has completed. Alternatively,
+ * discard_queued_entropy() may be called in case the mixing has
+ * failed.
* __queue_entropy() must be called with r->lock held.
*
* Entropy extraction is a two-step process:
@@ -813,6 +815,26 @@ static void queue_entropy(struct entropy_store *r, struct queued_entropy *q,
spin_unlock_irqrestore(&r->lock, flags);
}
+/*
+ * Queue entropy which comes from userspace and might take extreme
+ * values.
+ */
+static int queue_entropy_bits_safe(struct entropy_store *r,
+ struct queued_entropy *q,
+ int nbits)
+{
+ const int nbits_max = r->poolinfo->poolwords * 32;
+
+ if (nbits < 0)
+ return -EINVAL;
+
+ /* Cap the value to avoid overflows */
+ nbits = min(nbits, nbits_max);
+
+ queue_entropy(r, q, nbits << ENTROPY_SHIFT);
+ return 0;
+}
+
/*
* Dequeue previously queued entropy and return the pool entropy
* watermark to be used in pool_entropy_delta().
@@ -950,6 +972,22 @@ static void dispatch_queued_entropy(struct entropy_store *r,
}
}
+/*
+ * Discard queued entropy. May be called when e.g. a write_pool()
+ * operation failed and the corresponding previously queued entropy
+ * should not get dispatched to the pool.
+ */
+static void discard_queued_entropy(struct entropy_store *r,
+ struct queued_entropy *q)
+{
+ unsigned long flags;
+ int pool_watermark;
+
+ spin_lock_irqsave(&r->lock, flags);
+ __dequeue_entropy(r, q, &pool_watermark);
+ spin_unlock_irqrestore(&r->lock, flags);
+}
+
/*
* Credit the entropy store with n bits of entropy.
* Use credit_entropy_bits_safe() if the value comes from userspace
@@ -2272,6 +2310,7 @@ static long random_ioctl(struct file *f, unsigned int cmd, unsigned long arg)
int size, ent_count;
int __user *p = (int __user *)arg;
int retval;
+ struct queued_entropy q = { 0 };
switch (cmd) {
case RNDGETENTCNT:
@@ -2285,7 +2324,11 @@ static long random_ioctl(struct file *f, unsigned int cmd, unsigned long arg)
return -EPERM;
if (get_user(ent_count, p))
return -EFAULT;
- return credit_entropy_bits_safe(&input_pool, ent_count);
+ retval = queue_entropy_bits_safe(&input_pool, &q, ent_count);
+ if (retval < 0)
+ return retval;
+ dispatch_queued_entropy(&input_pool, &q);
+ return 0;
case RNDADDENTROPY:
if (!capable(CAP_SYS_ADMIN))
return -EPERM;
@@ -2295,11 +2338,17 @@ static long random_ioctl(struct file *f, unsigned int cmd, unsigned long arg)
return -EINVAL;
if (get_user(size, p++))
return -EFAULT;
+ retval = queue_entropy_bits_safe(&input_pool, &q, ent_count);
+ if (retval < 0)
+ return retval;
retval = write_pool(&input_pool, (const char __user *)p,
size);
- if (retval < 0)
+ if (retval < 0) {
+ discard_queued_entropy(&input_pool, &q);
return retval;
- return credit_entropy_bits_safe(&input_pool, ent_count);
+ }
+ discard_queued_entropy(&input_pool, &q);
+ return 0;
case RNDZAPENTCNT:
case RNDCLEARPOOL:
/*
--
2.26.2
Consider the following scenario:
Producer Consumer
-------- --------
mix_pool_bytes()
account()
->entropy_count -= n
extract_buf()
credit_entropy_bits()
->entropy_count += pool_entropy_delta()
The amount of entropy to credit as calculated by pool_entropy_delta()
depends on the current pool fill level: the higher the current
->entropy_count, the less the amount of new entropy credited. In the
situation above, a too small value of ->entropy_count would have been
observed and thus, too much entropy attributed to the new batch.
I do recognize the fact that this is currently more of a theoretical
concern. However, future patches will implement some statistical "health
tests" to be run on raw samples like e.g. cycle counts obtained and mixed
into the fast_pools in add_interrupt_randomness(). These tests must have
processed more events than can fit into the fast_pools (~64) before the
outcome is known. Thus, add_interrupt_randomness() will have to dump its
fast_pool into the global input_pool a couple of times before the tests
have completed and hence before the (accumulated) entropy credit may be
released to input_pool's ->entropy_count. It follows that the final entropy
credit attribution can be delayed for arbitrarily long to after the
corresponding mix_pool_bytes() operation.
The simplest solution would be to maintain a sequence counter which gets
incremented from account(). The producer side would take a snapshot before
mix_pool_bytes() and only eventually credit any entropy if it hasn't
changed in the meanwhile. However, that would mean that a lot of precious
entropy would be discarded, especially at boot time: as soon as the first
CPU seeds the primary_crng(), a large part of the entropy accumulated
through add_interrupt_randomness() on all other CPUs would be lost.
So follow a watermark based approach instead. That is, provide the producer
side with an ->entropy_count watermark which is guaranteed to not be less
than the value of ->entropy_count at any point in time from before to after
the mix_pool_bytes() operation(s). Note that the order in which concurrent
producers credit entropy doesn't matter, because
e1 = e0 + pool_entropy_delta(e0, n1)
e2 = e1 + pool_entropy_delta(e1, n2)
is equivalent (modulo approximation artifacts) to
e2 = e0 + pool_entropy_delta(e0, n1 + n2).
Thus, taking the larger of said watermark and the latest ->entropy_count
value for the pool fill level when calculating pool_entropy_delta() will
guarantee that the result won't exceed the true value.
Introduce the new __queue_entropy() and __dequeue_entropy() functions
intended to be used for delimiting one or more successive mix_pool_bytes()
invocations for which the pool watermark tracking is needed. Both take a
pointer to the target pool as well as to an instance of the new
struct queued_entropy. For reasons explained below, __queue_entropy() also
receives the amount of entropy transferred in the subsequent
mix_pool_bytes() operation as an argument and accumulates that at the given
struct queued_entropy instance. __queue_entropy() may be called any number
of times on the same struct queued_entropy instance until a matching
__dequeue_entropy() gets eventually invoked. The latter will return the
total number of (fractional) entropy bits accumulated at queued_entropy as
well as an appropriate pool watermark. Both are intended to be used for
that pool_entropy_delta() calculation when subsequently dispatching the
accumulated entropy to the pool.
Producers are not actually expected to call __dequeue_entropy() directly.
Instead, provide the new dispatch_queued_entropy() and
__dispatch_queued_entropy_fast() helpers. These will eventually supersede
credit_entropy_bits() respectively __credit_entropy_bits_fast(). Both take
a queued_entropy instance, run __dequeue_entropy() on it, carry out the
required pool_entropy_delta() calculations and add the result to the
target pool's ->entropy_count. Conversion of the individual entropy
producers to the new API will be the subject of future patches for the sake
of better reviewability. For now, merely reimplement credit_entropy_bits()
and __credit_entropy_bits_fast() on top of it in order to avoid excessive
code duplication.
Obviously, it's the consumer side's job to maintain the pool watermark:
whenever ->entropy_count decreases, the watermark needs updating. Maintain
the pool entropy watermark in the form of a delta to be added to the
current ->entropy_count to obtain the actual value. To this end, introduce
a new field ->entropy_watermark_delta to struct entropy_store.
Rename the existing account(), which gets called right before the
corresponding extract_buf()s in extract_entropy(), to account_begin(). Make
it add the allocated entropy count, i.e. the amount by which the pool's
->entropy_count has been reduced, to ->entropy_watermark_delta.
If possible, this watermark increment should be undone after the subsequent
extract_buf()s have completed, because otherwise the watermark would grow
unboundedly beyond the pool size over time. Note that this would render
producers unable to dispatch any new non-zero entropy to ->entropy_count.
Introduce the new account_complete() for handling the
->entropy_watermark_delta decrements and call it from extract_entropy()
right after the extract_buf()s following the preceding account_begin()
have finished.
Obviously it's safe to decrement the watermark again in case nobody cares
at all -- that is, if there currently isn't any entropy queued at the
producer side. Introduce a new field ->queued_entropy_batches to struct
entropy_store for keeping track of that. Make __queue_entropy() increment
it upon the first request to queue a non-zero amount of entropy at a given
struct queued_entropy instance. Likewise, make __dequeue_entropy()
decrement it again iff a non-zero amount of entropy has been queued.
Finally, make account_complete() undo the ->entropy_watermark_delta
increment from the preceding account_begin() in case
->queued_entropy_batches is zero.
Note that if ->queued_entropy_batches is found to be non-zero in
account_complete(), ->entropy_watermark_delta is left untouched, i.e. the
increment from the preceding account_begin() is "leaked". It follows
that the watermark can still grow beyond any bound over time. However, if
at the time account_complete() runs there is no entropy queued at the
producer side *and* there is no other, concurrent extraction pending an
upcoming __queue_entropy() could possibly interfere with, the watermark may
even get reset to zero and thus, any leakages left from former invocations
cleaned up. Introduce a new field ->pending_extractions to
struct entropy_store for keeping track of the number of pending entropy
extractions. Make account_begin() increment it and make account_complete()
decrement it again. Make account_complete() reset ->entropy_watermark_delta
in case ->queued_entropy_batches and ->entropy_watermark_delta are both
zero.
Once the initially mentioned health tests have been implemented and
enabled, it will not be unlikely that there's always at least one CPU
having some entropy queued at any point in time and thus, that
->queued_entropy_batches will never be found to equal zero in
account_complete(). As a last resort, enforce upper bounds on the magnitude
as well as on the lifetime of the pool watermark and reset it if any has
been exceeded. All entropy currently queued up on the producer side needs
to be invalidated in this case. Introduce a new field
->entropy_watermark_seq to struct entropy_store for maintaing a sequence
count needed to implement entropy invalidations. Make __queue_entropy()
take a snapshot at the first invocation and make it revalidate the
snapshot when accumulating additional entropy in subsequent invocations.
Make the final __dequeue_entropy() validate the snapshot and return zero
for the amount of dequeued entropy on failure. Make account_complete()
increment the sequence count when resetting the pool watermark even though
->queued_entropy_batches is non-zero.
Note that this sequence count based invalidation scheme does not allow
for watermark resets when there are multiple concurrent extractions
pending: a future __queue_entropy() could potentially interfere with any
of the other extractions and there is no way to invalidate it "in advance".
However, this doesn't matter because there are hardly any concurrent
entropy extractions after boot and even if there were: some
account_complete() would always come last.
What remains to be clarified is under which exact circumstances
account_complete() would resort to resetting the pool watermark and
invalidating all currently queued entropy. The limit on the watermark
magnitude, ->entropy_watermark_delta to be more specific, has been set to
one eighth of the pool size == 1/8 * 4096 bits == 512 bits. This has been
chosen as a compromise between allowing for up to two 256 bit
extractions/reseeds without invalidating queued entropy and not reducing
the efficiency of new entropy contributions too much. Assuming a watermark
value of 512 bits over the current ->entropy_count, the entropy credits as
calculated by pool_entropy_delta() for new contributions are 87.5%, 75%
and 50% respectively for pool fill levels of 0%, 50% and 75% of what they
would have been with a ->entropy_watermark_delta of zero. In order to avoid
a situation where a smallish ->entropy_watermark_delta which accumulated
during boot time, but never manages to increase beyond the reset threshold,
is kept forever, also impose a lifetime limit. The choice of
2 * CRNG_RESEED_INTERVAL for the maximum watermark lifetime follows the
same line of reasoning as for the chosen magnitude limit.
In order to enable this watermark lifetime management, add yet another new
field ->entropy_watermark_leak_time to struct entropy_store. Make
account_begin() set it to the current jiffies upon the first increment of
->entropy_watermark_delta from zero. Make account_complete() reset
->entropy_watermark_delta and invalidate all queued entropy as
described above whenever ->pending_extractions is zero and either
->entropy_watermark_leak_time is older than two times CRNG_RESEED_INTERVAL
or if ->entropy_watermark_delta exceeds one fourth of the pool size.
As entropy producers haven't been converted to the new __queue_entropy() +
dispatch_queued_entropy()/__dispatch_queued_entropy_fast() API yet, the net
effect of this patch is to "fix" a scenario similar to the one initially
described for those producers that call __mix_pool_bytes() and
__credit_entropy_bits_fast() without dropping the pool's ->lock inbetween,
i.e. for add_interrupt_randomness() and add_timer_randomness(). Namely, if
said sequence happens to get serialized inbetween the account_begin()
(formerly account()) and the last extract_buf() from a concurrent
extraction, the pool's entropy watermark will now be taken into account
when calculating the amount of new entropy to credit in
__credit_entropy_bits_fast(), because the latter has been reimplemented on
top of the new API.
Other than that, it's noteworthy that the pool entropy watermark might
exceed unexpectedly high levels at boot time, namely if multiple producers
happen to trigger the initial seeding of the primary_crng and the
subsequent entropy extractions complete when entropy has been queued up
somewhere else, e.g. in try_to_generate_entropy(). As detailed above, high
values of the pool watermark will reduce the efficiency when dispatching
new entropy attributions, but note that
- There are mechanisms in place to limit the effect in magnitude and
time.
- The watermark can never exceed the total amount of entropy collected
so far. So entropy collection at boot time would have to be terribly
efficient in order for this to matter.
- As seeding the primary_crng is a prerequisite for the described scenario,
a temporarily reduced entropy collection efficiency isn't really
concerning: getting towards a seeded primary_crng is all that matters at
this point.
Signed-off-by: Nicolai Stange <[email protected]>
---
drivers/char/random.c | 315 +++++++++++++++++++++++++++++++++++++++---
1 file changed, 292 insertions(+), 23 deletions(-)
diff --git a/drivers/char/random.c b/drivers/char/random.c
index 9f87332b158f..b91d1fc08ac5 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -499,7 +499,13 @@ struct entropy_store {
spinlock_t lock;
unsigned short add_ptr;
unsigned short input_rotate;
+
int entropy_count;
+ unsigned int entropy_watermark_delta;
+ unsigned int entropy_watermark_seq;
+ unsigned int queued_entropy_batches;
+ unsigned int pending_extractions;
+ unsigned long entropy_watermark_leak_time;
unsigned int initialized:1;
unsigned int last_data_init:1;
__u8 last_data[EXTRACT_SIZE];
@@ -671,6 +677,9 @@ static unsigned int pool_entropy_delta(struct entropy_store *r,
if (!nfrac)
return 0;
+ if (pool_size <= base_entropy_count)
+ return 0;
+
/*
* Credit: we have to account for the possibility of
* overwriting already present entropy. Even in the
@@ -714,26 +723,172 @@ static unsigned int pool_entropy_delta(struct entropy_store *r,
return entropy_count - base_entropy_count;
}
+struct queued_entropy {
+ unsigned int pool_watermark_seq;
+ unsigned int queued_entropy_fracbits;
+};
+
/*
- * Credit the entropy store with n bits of entropy.
- * To be used from hot paths when it is either known that nbits is
- * smaller than one half of the pool size or losing anything beyond that
- * doesn't matter. Must be called with r->lock being held.
+ * Queue a given amount of new entropy which is about to mixed into
+ * the entropy pool for later dispatch.
+ *
+ * __queue_entropy() may be called one or more time on the same struct
+ * queued_entropy instance in order to accumulate entropy for later
+ * dispatch. However, any such sequence of invocations must eventually
+ * be followed by exactly one call to either of __dequeue_entropy(),
+ * __dispatch_queued_entropy_fast() or dispatch_queued_entropy()
+ * when the actual pool mixing has completed.
+ * __queue_entropy() must be called with r->lock held.
+ *
+ * Entropy extraction is a two-step process:
+ * 1.) The allocated amount of entropy gets subtracted from ->entropy_count.
+ * 2.) The entropy is actually extracted from the pool by means of one or more
+ * extract_buf() invocations.
+ * Likewise for the mixing side:
+ * 1.) The new entropy data gets mixed into the pool via __mix_pool_bytes() and
+ * 2.) the pool's ->entropy_count incremented by a certain amount afterwards.
+ * However, that amount of new entropy credited in the last step depends
+ * on the current pool fill level: the higher the current ->entropy_count,
+ * the less the amount of new entropy credited, c.f. pool_entropy_delta().
+ *
+ * This must be accounted for in a scenario involving concurrent producers
+ * and consumers like the following:
+ * Producer Consumer
+ * -------- --------
+ * ->entropy_count -= n
+ * __mix_pool_bytes()
+ * ->entropy_count += pool_entropy_delta()
+ * extract_buf()
+ * Note how the pool_entropy_delta() would observe a too small pool
+ * fill level and thus, credits too much entropy to the new batch.
+ *
+ * The solution to work around this is to maintain a watermark, which
+ * is guaranteed to be >= than the pool's ->entropy_count value
+ * at any point in time from before __mix_pool_bytes() to after it.
+ *
+ * A call to __queue_entropy() enables watermark tracking from the
+ * producers side, the final __dequeue_entropy() disables it and
+ * returns the watermark. See also account_begin() and
+ * account_complete().
+ *
+ * Note there's no problem wuth multiple concurrent producers, because
+ * e1 = e0 + pool_entropy_delta(e0, n1);
+ * e2 = e1 + pool_entropy_delta(e1, n2);
+ * is equivalent (modulo approximation artifacts) to
+ * e2 = e0 + pool_entropy_delta(e0, n1 + n2);
*/
-static bool __credit_entropy_bits_fast(struct entropy_store *r, int nbits)
+static void __queue_entropy(struct entropy_store *r, struct queued_entropy *q,
+ unsigned int nfrac)
+{
+ if (!nfrac)
+ return;
+
+ if (!q->queued_entropy_fracbits) {
+ /*
+ * First call with non-zero nbits, enable watermark
+ * tracking.
+ */
+ q->pool_watermark_seq = r->entropy_watermark_seq;
+ r->queued_entropy_batches++;
+ } else if (q->pool_watermark_seq != r->entropy_watermark_seq) {
+ /*
+ * Previously queued entropy is doomed because
+ * the ->pool_watermark_delta had been reset.
+ * Don't add any more entropy on top of that.
+ */
+ q->pool_watermark_seq = r->entropy_watermark_seq;
+ q->queued_entropy_fracbits = 0;
+ }
+
+ q->queued_entropy_fracbits += nfrac;
+}
+
+static void queue_entropy(struct entropy_store *r, struct queued_entropy *q,
+ unsigned int nfrac)
{
- int entropy_count, orig;
+ unsigned long flags;
- if (!nbits)
+ spin_lock_irqsave(&r->lock, flags);
+ __queue_entropy(r, q, nfrac);
+ spin_unlock_irqrestore(&r->lock, flags);
+}
+
+/*
+ * Dequeue previously queued entropy and return the pool entropy
+ * watermark to be used in pool_entropy_delta().
+ *
+ * Must only be called after a sequence of one or more matching
+ * __queue_entropy() invocations. Must be called with r->lock
+ * held.
+ *
+ * __dequeue_entropy() returns the number of queued bits and resets
+ * q. *pool_watermark receives the pool entropy watermark as tracked
+ * from the beginning of the first preceding __queue_entropy() call
+ * up to the __dequeue_entropy() invocation.
+ *
+ * The number of returned fractional bits is intended to get
+ * subsequently passed together with the larger of *pool_watermark and
+ * r->entropy_count to pool_entropy_delta().
+ * If r->lock is not dropped inbetween *pool_watermark and the load
+ * of r->entropy_count, the former is guaranteed to equal the maximum.
+ */
+static unsigned int __dequeue_entropy(struct entropy_store *r,
+ struct queued_entropy *q,
+ int *pool_watermark)
+{
+ unsigned int nfrac;
+
+ nfrac = q->queued_entropy_fracbits;
+ if (!nfrac)
+ return 0;
+
+ /* Disable watermark tracking. */
+ q->queued_entropy_fracbits = 0;
+ r->queued_entropy_batches--;
+
+ /*
+ * The watermark has been invalidated in the meanwhile and
+ * the queued entropy is lost.
+ */
+ if (q->pool_watermark_seq != r->entropy_watermark_seq)
+ return 0;
+
+ *pool_watermark = r->entropy_count + r->entropy_watermark_delta;
+ if (*pool_watermark < 0)
+ return 0;
+
+ return nfrac;
+}
+
+/*
+ * Credit the pool with previously queued entropy.
+ *
+ * Must only be called after a sequence of one or more matching
+ * __queue_entropy() invocations. Must be called with r->lock
+ * held.
+ *
+ * To be used from hot paths when it is either known that the amount
+ * of queued entropy is smaller than one half of the pool size or
+ * losing anything beyond that doesn't matter.
+ *
+ * Returns true if the caller is supposed to seed the primary_crng.
+ */
+static bool __dispatch_queued_entropy_fast(struct entropy_store *r,
+ struct queued_entropy *q)
+{
+ unsigned int nfrac;
+ int entropy_count, orig, pool_watermark;
+
+ nfrac = __dequeue_entropy(r, q, &pool_watermark);
+ if (!nfrac)
return false;
orig = r->entropy_count;
- entropy_count = orig + pool_entropy_delta(r, orig,
- nbits << ENTROPY_SHIFT,
+ entropy_count = orig + pool_entropy_delta(r, pool_watermark, nfrac,
true);
WRITE_ONCE(r->entropy_count, entropy_count);
- trace_credit_entropy_bits(r->name, nbits,
+ trace_credit_entropy_bits(r->name, nfrac >> ENTROPY_SHIFT,
entropy_count >> ENTROPY_SHIFT, _RET_IP_);
if (unlikely(r == &input_pool && crng_init < 2)) {
@@ -747,15 +902,35 @@ static bool __credit_entropy_bits_fast(struct entropy_store *r, int nbits)
/*
* Credit the entropy store with n bits of entropy.
- * Use credit_entropy_bits_safe() if the value comes from userspace
- * or otherwise should be checked for extreme values.
+ * To be used from hot paths when it is either known that nbits is
+ * smaller than one half of the pool size or losing anything beyond that
+ * doesn't matter. Must be called with r->lock being held.
*/
-static void credit_entropy_bits(struct entropy_store *r, int nbits)
+static bool __credit_entropy_bits_fast(struct entropy_store *r, int nbits)
+{
+ struct queued_entropy q = { 0 };
+
+ __queue_entropy(r, &q, nbits << ENTROPY_SHIFT);
+ return __dispatch_queued_entropy_fast(r, &q);
+}
+
+/*
+ * Credit the pool with previously queued entropy.
+ *
+ * Must only be called after a sequence of one or more matching
+ * __queue_entropy() invocations.
+ */
+static void dispatch_queued_entropy(struct entropy_store *r,
+ struct queued_entropy *q)
{
- int entropy_count, orig;
+ unsigned int nfrac;
+ int entropy_count, orig, pool_watermark, base;
unsigned long flags;
- if (!nbits)
+ spin_lock_irqsave(&r->lock, flags);
+ nfrac = __dequeue_entropy(r, q, &pool_watermark);
+ spin_unlock_irqrestore(&r->lock, flags);
+ if (!nfrac)
return;
retry:
@@ -765,9 +940,8 @@ static void credit_entropy_bits(struct entropy_store *r, int nbits)
* ->entropy_count becomes stable.
*/
orig = READ_ONCE(r->entropy_count);
- entropy_count = orig + pool_entropy_delta(r, orig,
- nbits << ENTROPY_SHIFT,
- false);
+ base = max_t(int, pool_watermark, orig);
+ entropy_count = orig + pool_entropy_delta(r, base, nfrac, false);
spin_lock_irqsave(&r->lock, flags);
if (r->entropy_count != orig) {
spin_unlock_irqrestore(&r->lock, flags);
@@ -776,7 +950,7 @@ static void credit_entropy_bits(struct entropy_store *r, int nbits)
WRITE_ONCE(r->entropy_count, entropy_count);
spin_unlock_irqrestore(&r->lock, flags);
- trace_credit_entropy_bits(r->name, nbits,
+ trace_credit_entropy_bits(r->name, nfrac >> ENTROPY_SHIFT,
entropy_count >> ENTROPY_SHIFT, _RET_IP_);
if (r == &input_pool) {
@@ -790,6 +964,19 @@ static void credit_entropy_bits(struct entropy_store *r, int nbits)
}
}
+/*
+ * Credit the entropy store with n bits of entropy.
+ * Use credit_entropy_bits_safe() if the value comes from userspace
+ * or otherwise should be checked for extreme values.
+ */
+static void credit_entropy_bits(struct entropy_store *r, int nbits)
+{
+ struct queued_entropy q = { 0 };
+
+ queue_entropy(r, &q, nbits << ENTROPY_SHIFT);
+ dispatch_queued_entropy(r, &q);
+}
+
static int credit_entropy_bits_safe(struct entropy_store *r, int nbits)
{
const int nbits_max = r->poolinfo->poolwords * 32;
@@ -1402,8 +1589,12 @@ EXPORT_SYMBOL_GPL(add_disk_randomness);
/*
* This function decides how many bytes to actually take from the
* given pool, and also debits the entropy count accordingly.
+ *
+ * Increases the pool entropy watermark (c.f. __queue_entropy() and
+ * __dequeue_entropy()) and must be followed with a matching
+ * account_complete() in order to decrease it again, if possible.
*/
-static size_t account(struct entropy_store *r, size_t nbytes, int min)
+static size_t account_begin(struct entropy_store *r, size_t nbytes, int min)
{
int entropy_count, have_bytes;
size_t ibytes, nfrac;
@@ -1419,6 +1610,7 @@ static size_t account(struct entropy_store *r, size_t nbytes, int min)
have_bytes = entropy_count >> (ENTROPY_SHIFT + 3);
ibytes = min_t(size_t, ibytes, have_bytes);
+
if (ibytes < min)
ibytes = 0;
@@ -1434,6 +1626,18 @@ static size_t account(struct entropy_store *r, size_t nbytes, int min)
entropy_count = 0;
WRITE_ONCE(r->entropy_count, entropy_count);
+
+ if (!r->entropy_watermark_delta) {
+ /*
+ * This is not exact. In fact it is not known yet if
+ * the watermark entropy added below will be actually
+ * be leaked in account_complete(). But there can be
+ * concurrent consumers and someone has to set this.
+ */
+ r->entropy_watermark_leak_time = jiffies;
+ }
+ r->entropy_watermark_delta += nfrac;
+ r->pending_extractions++;
spin_unlock_irqrestore(&r->lock, flags);
trace_debit_entropy(r->name, 8 * ibytes);
@@ -1445,6 +1649,69 @@ static size_t account(struct entropy_store *r, size_t nbytes, int min)
return ibytes;
}
+/*
+ * Undo the pool watermark increment from a preceding
+ * account_begin(), if possible.
+ */
+static void account_complete(struct entropy_store *r, size_t ibytes)
+{
+ unsigned long flags;
+
+ spin_lock_irqsave(&r->lock, flags);
+ r->pending_extractions--;
+ if (!r->queued_entropy_batches) {
+ /*
+ * There's currently no entropy queued at the producer
+ * side and at the very least it is safe to undo the
+ * watermark increment from the matching
+ * account_begin().
+ */
+ if (!r->pending_extractions) {
+ /*
+ * No other extractions pending. It is even
+ * safe to dismiss all watermark increments
+ * which had to be leaked from previous,
+ * unrelated account_complete() invocations
+ * because there had been some entropy queued
+ * at their time.
+ */
+ r->entropy_watermark_delta = 0;
+ } else {
+ unsigned int nfrac;
+
+ nfrac = ibytes << (ENTROPY_SHIFT + 3);
+ r->entropy_watermark_delta -= nfrac;
+ }
+ } else if (!r->pending_extractions) {
+ /*
+ * There is currently some entropy queued at the
+ * producer side and there's no choice but to leave
+ * the pool watermark untouched and thus, to "leak"
+ * the increment from the matching account_begin().
+ *
+ * However, if it gets too wild, the watermark is
+ * reset and all currently queued entropy invalidated.
+ * We don't want to keep leaked watermark increments
+ * forever and also keep them bounded by 1/8 of the
+ * pool size in total in order to limit its damping
+ * effect on new entropy in pool_entropy_delta().
+ */
+ int leak_limit;
+ unsigned long leak_cleanup_time;
+
+ leak_limit = r->poolinfo->poolfracbits >> 3;
+ leak_cleanup_time = (r->entropy_watermark_leak_time +
+ 2 * CRNG_RESEED_INTERVAL);
+ if (r->entropy_watermark_delta > leak_limit ||
+ time_after(jiffies, leak_cleanup_time)) {
+ r->entropy_watermark_delta = 0;
+ /* Invalidate all queued entropy. */
+ r->entropy_watermark_seq++;
+ }
+ }
+ spin_unlock_irqrestore(&r->lock, flags);
+}
+
/*
* This function does the actual extraction for extract_entropy and
* extract_entropy_user.
@@ -1547,6 +1814,7 @@ static ssize_t extract_entropy(struct entropy_store *r, void *buf,
{
__u8 tmp[EXTRACT_SIZE];
unsigned long flags;
+ ssize_t ret;
/* if last_data isn't primed, we need EXTRACT_SIZE extra bytes */
if (fips_enabled) {
@@ -1564,9 +1832,10 @@ static ssize_t extract_entropy(struct entropy_store *r, void *buf,
}
trace_extract_entropy(r->name, nbytes, ENTROPY_BITS(r), _RET_IP_);
- nbytes = account(r, nbytes, min);
-
- return _extract_entropy(r, buf, nbytes, fips_enabled);
+ nbytes = account_begin(r, nbytes, min);
+ ret = _extract_entropy(r, buf, nbytes, fips_enabled);
+ account_complete(r, nbytes);
+ return ret;
}
#define warn_unseeded_randomness(previous) \
--
2.26.2
In an effort to drop __credit_entropy_bits_fast() in favor of the new
__queue_entropy()/__dispatch_queued_entropy_fast() API, convert
add_timer_randomness() from the former to the latter.
There is no change in functionality at this point, because
__credit_entropy_bits_fast() has already been reimplemented on top of the
new API before.
Signed-off-by: Nicolai Stange <[email protected]>
---
drivers/char/random.c | 6 ++++--
1 file changed, 4 insertions(+), 2 deletions(-)
diff --git a/drivers/char/random.c b/drivers/char/random.c
index b91d1fc08ac5..e8c86abde901 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -1400,6 +1400,7 @@ static void add_timer_randomness(struct timer_rand_state *state, unsigned num)
long delta, delta2, delta3;
bool reseed;
unsigned long flags;
+ struct queued_entropy q = { 0 };
sample.jiffies = jiffies;
sample.cycles = random_get_entropy();
@@ -1432,13 +1433,14 @@ static void add_timer_randomness(struct timer_rand_state *state, unsigned num)
r = &input_pool;
spin_lock_irqsave(&r->lock, flags);
- __mix_pool_bytes(r, &sample, sizeof(sample));
/*
* delta is now minimum absolute delta.
* Round down by 1 bit on general principles,
* and limit entropy estimate to 12 bits.
*/
- reseed = __credit_entropy_bits_fast(r, min_t(int, fls(delta>>1), 11));
+ __queue_entropy(r, &q, min_t(int, fls(delta>>1), 11) << ENTROPY_SHIFT);
+ __mix_pool_bytes(r, &sample, sizeof(sample));
+ reseed = __dispatch_queued_entropy_fast(r, &q);
spin_unlock_irqrestore(&r->lock, flags);
if (reseed)
crng_reseed(&primary_crng, r);
--
2.26.2
NIST SP800-90B requires certain statistical tests to be run continuously on
a noise source's output.
In preparation to implementing those, introduce an empty stub,
health_test_process() and wire it up to add_interrupt_randomness(). This
patch does not implement any actual testing functionality yet, it's mereley
meant to define the interactions between add_interrupt_randomness() and
the health tests.
health_test_process() is to be invoked on individual noise samples, i.e.
cycle counter values and returns, either of three possible status
codes indicating to the calling add_interrupt_randomness() that
- either some more samples are needed in order to complete the statistical
tests,
- that the tests have finished with positive result on the latest run
of noise samples or
- that the tests have failed.
Introduce an enum health_result defining constants corresponding to these
resp. cases: health_queue, health_dispatch and health_discard. Provide
another value, health_none, to indicate the case that the health tests
are disabled, because e.g. fips_enabled is unset. Make the stub
health_test_process() return this value for now.
As long as the statistical tests need more input noise samples before
reaching a conclusion, health_queue will get returned from
health_test_process(). FWIW, the number of successive input samples needed
by the tests will be at the order of 128 to 8192, depending on the per-IRQ
entropy estimate. add_interrupt_randomness() currently attempts to transfer
the noise kept within in the per-CPU fast_pool, which is of limited
capacity, to the global input_pool as soon as a threshold of 64 events is
reached and it will continue to do so. However, as long as some tests are
pending, i.e. keep returning health_queue, the associated amount of
estimated entropy must not get added to the global input_pool balance, but
queued up at the fast_pool's queued_entropy instance. Once the health test
have eventually succeeded, as indiciated by health_test_process(), the
entropy previously queued up may get dispatched to the global reserve.
OTOH, on test failure health_discard will get returned and all entropy
queued up from add_interrupt_randomness() since the last dispatch (or
discard resp.) must get discarded.
Note that add_interrupt_randomness() will continue to unconditionally mix
the samples into the fast_pools and eventually into the global input_pool
-- the health test results really only affect the entropy accounting.
So, make add_interrupt_randomness() invoke health_test_process() on
the current cycle counter value in case fips_enabled is set.
In case a fast_pool's fill level threshold of 64 events is reached at a
time when health tests are still pending and keep returning health_queue,
let add_interrupt_randomness() continue to mix the fast_pool's contents
into the input_pool as before, but enqueue the associated amount of entropy
at the fast_pool's associated queued_entropy instance for later dispatch.
Both, entropy dispatch as well as discard operations, require a call to
__dequeue_entropy(), which in turn must only get invoked with the
input_pool's ->lock being held. It follows that in case the spin_trylock()
in add_interrupt_randomness() failed, the latter would not be able to
perform entropy dispatch or discard operations immediately at the time
those have been requested by the health tests. Add two new boolean flags,
->dispatch_needed and ->discard_needed, to struct fast_pool. Set them from
add_interrupt_randomness() in case health_test_process() returned
health_dispatch or health_discard resp.. Make the current and subsequent
add_interrupt_randomness() invocations to check for ->dispatch_needed and
->discard_needed and to attempt to execute any pending dispatch/discard
request. Clear ->dispatch_needed and ->discard_needed again when the
prerequisite ->lock could eventually be obtained.
As actual health tests returning anything but health_none haven't been
implemented yet, there is no behavioural change at this point.
Signed-off-by: Nicolai Stange <[email protected]>
---
drivers/char/random.c | 78 +++++++++++++++++++++++++++++++++++++++++--
1 file changed, 75 insertions(+), 3 deletions(-)
diff --git a/drivers/char/random.c b/drivers/char/random.c
index 0f56c873a501..cb6441b96b8e 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -881,14 +881,30 @@ static void discard_queued_entropy(struct entropy_store *r,
struct health_test {};
+enum health_result {
+ health_none,
+ health_queue,
+ health_dispatch,
+ health_discard,
+};
+
static void health_test_reset(struct health_test *h)
{}
+static enum health_result
+health_test_process(struct health_test *h, unsigned int event_entropy_shift,
+ u8 sample)
+{
+ return health_none;
+}
+
struct fast_pool {
__u32 pool[4];
unsigned long last;
unsigned short reg_idx;
unsigned char count;
+ bool dispatch_needed : 1;
+ bool discard_needed : 1;
int event_entropy_shift;
struct queued_entropy q;
struct health_test health;
@@ -1662,9 +1678,10 @@ void add_interrupt_randomness(int irq, int irq_flags)
cycles_t cycles = random_get_entropy();
__u32 c_high, j_high;
__u64 ip;
- bool reseed;
+ bool reseed = false;
struct queued_entropy *q = &fast_pool->q;
unsigned int nfrac;
+ enum health_result health_result = health_none;
if (cycles == 0)
cycles = get_reg(fast_pool, regs);
@@ -1682,6 +1699,12 @@ void add_interrupt_randomness(int irq, int irq_flags)
this_cpu_add(net_rand_state.s1, fast_pool->pool[cycles & 3]);
fast_pool_init_accounting(fast_pool);
+ if (fips_enabled) {
+ health_result =
+ health_test_process(&fast_pool->health,
+ fast_pool->event_entropy_shift,
+ cycles);
+ }
if (unlikely(crng_init == 0)) {
if ((fast_pool->count >= 64) &&
@@ -1693,8 +1716,48 @@ void add_interrupt_randomness(int irq, int irq_flags)
return;
}
+ switch (health_result) {
+ case health_dispatch:
+ /*
+ * Still haven't made it around processing a previous
+ * entropy discard request?
+ */
+ fast_pool->dispatch_needed = !fast_pool->discard_needed;
+ break;
+
+ case health_discard:
+ /*
+ * Still haven't made it around processing a previous
+ * entropy dispatch request?
+ */
+ fast_pool->discard_needed = !fast_pool->dispatch_needed;
+ break;
+
+ case health_queue:
+ /*
+ * If a previous sample triggered a dispatch which is
+ * still pending, it's impossible to add new events on
+ * top as far as entropy accounting is
+ * concerned. Don't count any events until we get a
+ * hold of the input_pool ->lock and complete the
+ * dispatch below. Undo the increment from fast_mix()
+ * above.
+ */
+ if (fast_pool->dispatch_needed)
+ fast_pool->count--;
+ break;
+
+ case health_none:
+ /*
+ * fips_enabled is unset, suppress compiler warnings.
+ */
+ break;
+ };
+
if ((fast_pool->count < 64) &&
- !time_after(now, fast_pool->last + HZ))
+ !(health_result == health_none &&
+ time_after(now, fast_pool->last + HZ)) &&
+ !fast_pool->dispatch_needed && !fast_pool->discard_needed)
return;
r = &input_pool;
@@ -1710,7 +1773,16 @@ void add_interrupt_randomness(int irq, int irq_flags)
}
__queue_entropy(r, q, nfrac);
__mix_pool_bytes(r, &fast_pool->pool, sizeof(fast_pool->pool));
- reseed = __dispatch_queued_entropy_fast(r, q);
+
+ if (fast_pool->dispatch_needed || health_result == health_none) {
+ reseed = __dispatch_queued_entropy_fast(r, q);
+ fast_pool->dispatch_needed = false;
+ } else if (fast_pool->discard_needed) {
+ int dummy;
+
+ __dequeue_entropy(r, q, &dummy);
+ fast_pool->discard_needed = false;
+ }
spin_unlock(&r->lock);
fast_pool->last = now;
--
2.26.2
The to be implemented health tests will maintain some per-CPU state as they
successively process the IRQ samples fed into the resp. fast_pool from
add_interrupt_randomness().
In order to not to clutter future patches with trivialities, introduce
an empty struct health_test supposed to keep said state in the future.
Add a member of this new type to struct fast_pool.
Introduce a health_test_reset() stub, which is supposed to (re)initialize
instances of struct health_test.
Invoke it from the fast_pool_init_accounting() to make sure that a
fast_pool's contained health_test instance gets initialized once before
its first usage.
Make add_interrupt_randomness call fast_pool_init_accounting() earlier:
health test functionality will get invoked before the latter's old location
and it must have been initialized by that time.
Signed-off-by: Nicolai Stange <[email protected]>
---
drivers/char/random.c | 11 +++++++++--
1 file changed, 9 insertions(+), 2 deletions(-)
diff --git a/drivers/char/random.c b/drivers/char/random.c
index 37746df53acf..0f56c873a501 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -879,6 +879,11 @@ static void discard_queued_entropy(struct entropy_store *r,
spin_unlock_irqrestore(&r->lock, flags);
}
+struct health_test {};
+
+static void health_test_reset(struct health_test *h)
+{}
+
struct fast_pool {
__u32 pool[4];
unsigned long last;
@@ -886,6 +891,7 @@ struct fast_pool {
unsigned char count;
int event_entropy_shift;
struct queued_entropy q;
+ struct health_test health;
};
/*
@@ -1644,6 +1650,7 @@ static inline void fast_pool_init_accounting(struct fast_pool *f)
return;
f->event_entropy_shift = min_irq_event_entropy_shift();
+ health_test_reset(&f->health);
}
void add_interrupt_randomness(int irq, int irq_flags)
@@ -1674,6 +1681,8 @@ void add_interrupt_randomness(int irq, int irq_flags)
add_interrupt_bench(cycles);
this_cpu_add(net_rand_state.s1, fast_pool->pool[cycles & 3]);
+ fast_pool_init_accounting(fast_pool);
+
if (unlikely(crng_init == 0)) {
if ((fast_pool->count >= 64) &&
crng_fast_load((char *) fast_pool->pool,
@@ -1692,8 +1701,6 @@ void add_interrupt_randomness(int irq, int irq_flags)
if (!spin_trylock(&r->lock))
return;
- fast_pool_init_accounting(fast_pool);
-
if (!fips_enabled) {
/* award one bit for the contents of the fast pool */
nfrac = 1 << ENTROPY_SHIFT;
--
2.26.2
The startup health tests to be executed at boot as required by NIST 800-90B
consist of running the contiuous health tests, i.e. the Adaptive Proportion
Test (APT) and the Repetition Count Test (RCT), until a certain amount
of noise samples have been examined. In case of test failure during this
period, the startup tests would get restarted by means of reinitializing
the fast_pool's ->warmup member with the original number of total samples
to examine during startup.
A future patch will enable dynamically switching from the initial H=1 or
1/8 per-IRQ min-entropy estimates to lower values upon health test
failures in order to keep those systems going where these more or less
arbitrary per-IRQ entropy estimates turn out to simply be wrong. It is
certainly desirable to restart the startup health tests upon such a switch.
In order to keep the upcoming code comprehensible, move the startup test
restart logic from health_test_process() into add_interrupt_randomness().
For simplicity, make add_interrupt_randomness() trigger a startup test on
each health test failure. Note that there's a change in behaviour: up to
now, only the bootime startup tests would have restarted themselves upon
failure, whereas now even a failure of the continuous health tests can
potentially trigger a startup test long after boot.
Note that as it currently stands, rerunning the full startup tests after
the crng has received its initial seed has the only effect to inhibit
entropy dispatch for a while and thus, to potentially delay those best
effort crng reseeds during runtime. As reseeds never reduce a crng state's
entropy, this behaviour is admittedly questionable. However, further
patches introducing forced reseeds might perhaps become necessary in the
future, c.f. the specification of "reseed_interval" in NIST SP800-90A.
Thus, it's better to keep the startup health test restart logic consistent
for now.
Signed-off-by: Nicolai Stange <[email protected]>
---
drivers/char/random.c | 12 ++++++++----
1 file changed, 8 insertions(+), 4 deletions(-)
diff --git a/drivers/char/random.c b/drivers/char/random.c
index 86dd87588b1b..bb79dcb96882 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -1098,8 +1098,6 @@ health_test_process(struct health_test *h, unsigned int event_entropy_shift,
* Something is really off, get_cycles() has become
* (or always been) a constant.
*/
- if (h->warmup)
- health_test_reset(h, event_entropy_shift);
return health_discard;
}
@@ -1110,8 +1108,6 @@ health_test_process(struct health_test *h, unsigned int event_entropy_shift,
*/
apt = health_test_apt(h, event_entropy_shift, sample_delta);
if (unlikely(h->warmup) && --h->warmup) {
- if (apt == health_discard)
- health_test_reset(h, event_entropy_shift);
/*
* Don't allow the caller to dispatch until warmup
* has completed.
@@ -1928,6 +1924,14 @@ void add_interrupt_randomness(int irq, int irq_flags)
health_test_process(&fast_pool->health,
fast_pool->event_entropy_shift,
cycles);
+ if (unlikely(health_result == health_discard)) {
+ /*
+ * Oops, something's odd. Restart the startup
+ * tests.
+ */
+ health_test_reset(&fast_pool->health,
+ fast_pool->event_entropy_shift);
+ }
}
if (unlikely(crng_init == 0)) {
--
2.26.2
When health tests are introduced with upcoming patches, it will become
necessary to keep entropy queued across add_interrupt_randomness()
invocations for later dispatch to the global balance.
Prepare for this by adding a struct queued_entropy member to the per-CPU
fast_pool. Use it in place of that queue with automatic storage duration
in add_interrupt_randomness().
Signed-off-by: Nicolai Stange <[email protected]>
---
drivers/char/random.c | 7 ++++---
1 file changed, 4 insertions(+), 3 deletions(-)
diff --git a/drivers/char/random.c b/drivers/char/random.c
index 55e784a5a2ec..37746df53acf 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -885,6 +885,7 @@ struct fast_pool {
unsigned short reg_idx;
unsigned char count;
int event_entropy_shift;
+ struct queued_entropy q;
};
/*
@@ -1655,7 +1656,7 @@ void add_interrupt_randomness(int irq, int irq_flags)
__u32 c_high, j_high;
__u64 ip;
bool reseed;
- struct queued_entropy q = { 0 };
+ struct queued_entropy *q = &fast_pool->q;
unsigned int nfrac;
if (cycles == 0)
@@ -1700,9 +1701,9 @@ void add_interrupt_randomness(int irq, int irq_flags)
nfrac = fast_pool_entropy(fast_pool->count,
fast_pool->event_entropy_shift);
}
- __queue_entropy(r, &q, nfrac);
+ __queue_entropy(r, q, nfrac);
__mix_pool_bytes(r, &fast_pool->pool, sizeof(fast_pool->pool));
- reseed = __dispatch_queued_entropy_fast(r, &q);
+ reseed = __dispatch_queued_entropy_fast(r, q);
spin_unlock(&r->lock);
fast_pool->last = now;
--
2.26.2
Currently, all updates to ->entropy_count are synchronized by means of
cmpxchg-retry loops found in credit_entropy_bits(),
__credit_entropy_bits_fast() and account() respectively.
However, all but one __credit_entropy_bits_fast() call sites grap the pool
->lock already and it would be nice if the potentially costly cmpxchg could
be avoided in these performance critical paths. In addition to that, future
patches will introduce new fields to struct entropy_store which will
required some kinf of synchronization with ->entropy_count updates from
said producer paths as well.
Protect ->entropy_count with the pool ->lock.
- Make callers of __credit_entropy_bits_fast() invoke it with the
pool ->lock held. Extend existing critical sections where possible.
Drop the cmpxchg-reply loop in __credit_entropy_bits_fast() in favor of
a plain assignment.
- Retain the retry loop in credit_entropy_bits(): the potentially
expensive pool_entropy_delta() should not be called under the lock in
order to not unnecessarily block contenders. In order to continue to
synchronize with __credit_entropy_bits_fast() and account(), the
cmpxchg gets replaced by a plain comparison + store with the ->lock being
held.
- Make account() grab the ->lock and drop the cmpxchg-retry loop in favor
of a plain assignent.
Signed-off-by: Nicolai Stange <[email protected]>
---
drivers/char/random.c | 44 +++++++++++++++++++++++++++++--------------
1 file changed, 30 insertions(+), 14 deletions(-)
diff --git a/drivers/char/random.c b/drivers/char/random.c
index d9e4dd27d45d..9f87332b158f 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -718,7 +718,7 @@ static unsigned int pool_entropy_delta(struct entropy_store *r,
* Credit the entropy store with n bits of entropy.
* To be used from hot paths when it is either known that nbits is
* smaller than one half of the pool size or losing anything beyond that
- * doesn't matter.
+ * doesn't matter. Must be called with r->lock being held.
*/
static bool __credit_entropy_bits_fast(struct entropy_store *r, int nbits)
{
@@ -727,13 +727,11 @@ static bool __credit_entropy_bits_fast(struct entropy_store *r, int nbits)
if (!nbits)
return false;
-retry:
- orig = READ_ONCE(r->entropy_count);
+ orig = r->entropy_count;
entropy_count = orig + pool_entropy_delta(r, orig,
nbits << ENTROPY_SHIFT,
true);
- if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
- goto retry;
+ WRITE_ONCE(r->entropy_count, entropy_count);
trace_credit_entropy_bits(r->name, nbits,
entropy_count >> ENTROPY_SHIFT, _RET_IP_);
@@ -755,17 +753,28 @@ static bool __credit_entropy_bits_fast(struct entropy_store *r, int nbits)
static void credit_entropy_bits(struct entropy_store *r, int nbits)
{
int entropy_count, orig;
+ unsigned long flags;
if (!nbits)
return;
retry:
+ /*
+ * Don't run the potentially expensive pool_entropy_delta()
+ * calculations under the spinlock. Instead retry until
+ * ->entropy_count becomes stable.
+ */
orig = READ_ONCE(r->entropy_count);
entropy_count = orig + pool_entropy_delta(r, orig,
nbits << ENTROPY_SHIFT,
false);
- if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
+ spin_lock_irqsave(&r->lock, flags);
+ if (r->entropy_count != orig) {
+ spin_unlock_irqrestore(&r->lock, flags);
goto retry;
+ }
+ WRITE_ONCE(r->entropy_count, entropy_count);
+ spin_unlock_irqrestore(&r->lock, flags);
trace_credit_entropy_bits(r->name, nbits,
entropy_count >> ENTROPY_SHIFT, _RET_IP_);
@@ -1203,12 +1212,11 @@ static void add_timer_randomness(struct timer_rand_state *state, unsigned num)
} sample;
long delta, delta2, delta3;
bool reseed;
+ unsigned long flags;
sample.jiffies = jiffies;
sample.cycles = random_get_entropy();
sample.num = num;
- r = &input_pool;
- mix_pool_bytes(r, &sample, sizeof(sample));
/*
* Calculate number of bits of randomness we probably added.
@@ -1235,12 +1243,16 @@ static void add_timer_randomness(struct timer_rand_state *state, unsigned num)
if (delta > delta3)
delta = delta3;
+ r = &input_pool;
+ spin_lock_irqsave(&r->lock, flags);
+ __mix_pool_bytes(r, &sample, sizeof(sample));
/*
* delta is now minimum absolute delta.
* Round down by 1 bit on general principles,
* and limit entropy estimate to 12 bits.
*/
reseed = __credit_entropy_bits_fast(r, min_t(int, fls(delta>>1), 11));
+ spin_unlock_irqrestore(&r->lock, flags);
if (reseed)
crng_reseed(&primary_crng, r);
}
@@ -1358,12 +1370,12 @@ void add_interrupt_randomness(int irq, int irq_flags)
__mix_pool_bytes(r, &seed, sizeof(seed));
credit = 1;
}
- spin_unlock(&r->lock);
fast_pool->count = 0;
/* award one bit for the contents of the fast pool */
reseed = __credit_entropy_bits_fast(r, credit + 1);
+ spin_unlock(&r->lock);
if (reseed)
crng_reseed(&primary_crng, r);
}
@@ -1393,14 +1405,15 @@ EXPORT_SYMBOL_GPL(add_disk_randomness);
*/
static size_t account(struct entropy_store *r, size_t nbytes, int min)
{
- int entropy_count, orig, have_bytes;
+ int entropy_count, have_bytes;
size_t ibytes, nfrac;
+ unsigned long flags;
BUG_ON(r->entropy_count > r->poolinfo->poolfracbits);
+ spin_lock_irqsave(&r->lock, flags);
/* Can we pull enough? */
-retry:
- entropy_count = orig = READ_ONCE(r->entropy_count);
+ entropy_count = r->entropy_count;
ibytes = nbytes;
/* never pull more than available */
have_bytes = entropy_count >> (ENTROPY_SHIFT + 3);
@@ -1420,8 +1433,8 @@ static size_t account(struct entropy_store *r, size_t nbytes, int min)
else
entropy_count = 0;
- if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
- goto retry;
+ WRITE_ONCE(r->entropy_count, entropy_count);
+ spin_unlock_irqrestore(&r->lock, flags);
trace_debit_entropy(r->name, 8 * ibytes);
if (ibytes && ENTROPY_BITS(r) < random_write_wakeup_bits) {
@@ -1639,8 +1652,11 @@ EXPORT_SYMBOL(get_random_bytes);
static void entropy_timer(struct timer_list *t)
{
bool reseed;
+ unsigned long flags;
+ spin_lock_irqsave(&input_pool.lock, flags);
reseed = __credit_entropy_bits_fast(&input_pool, 1);
+ spin_unlock_irqrestore(&input_pool.lock, flags);
if (reseed)
crng_reseed(&primary_crng, &input_pool);
}
--
2.26.2
On Tue, Sep 22, 2020 at 03:23:44PM +0200, Torsten Duwe wrote:
> On Mon, Sep 21, 2020 at 10:40:37AM +0200, Stephan Mueller wrote:
> > Am Montag, 21. September 2020, 09:58:16 CEST schrieb Nicolai Stange:
> >
> > > - people dislike the approach of having two competing implementations for
> > > what is basically the same functionality in the kernel.
> >
> > Is this really so bad considering the security implications on this topic? We
> > also have multiple file systems, multiple memory allocators, etc...
>
> Exactly. I thought Linux was about the freedom of choice.
http://www.islinuxaboutchoice.com/
:)
On Fri, Oct 02, 2020 at 02:38:36PM +0200, Torsten Duwe wrote:
> Almost two weeks passed and these are the "relevant" replies:
>
> Jason personally does not like FIPS, and is afraid of
> "subpar crypto". Albeit this patch set strictly isn't about
> crypto at all; the crypto subsystem is in the unlucky position
> to just depend on a good entropy source.
>
> Greg claims that Linux (kernel) isn't about choice, which is clearly
> wrong.
I think there's a small misunderstanding here, my understanding is
that for quite a while, the possibilities offered by the various
random subsystems or their proposed derivative used to range from
"you have to choose between a fast system that may be vulnerable
to some attacks, a system that might not be vulnerable to certain
attacks but might not always boot, or a slow system not vulnerable
to certain attacks". Greg's point seems to be that if we add an
option, it means it's yet another tradeoff between these possibilities
and that someone will still not be happy at the end of the chain. If
the proposed solution covers everything at once (performance,
reliability, unpredictability), then there probably is no more reason
for keeping alternate solutions at all, hence there's no need to give
the user the choice between multiple options when only one is known
to always be valid. At least that's how I see it and it makes sense
to me.
> And this is all ???
Possibly a lot of people got used to seeing the numerous versions
and are less attentive to new series, it's possible that your message
will wake everyone up.
Regards,
Willy
> -----Original Message-----
> From: Greg Kroah-Hartman <[email protected]>
> Sent: Friday, October 2, 2020 5:13 PM
> To: Van Leeuwen, Pascal <[email protected]>
> Cc: Torsten Duwe <[email protected]>; Theodore Y. Ts'o <[email protected]>; [email protected]; Nicolai Stange
> <[email protected]>; LKML <[email protected]>; Arnd Bergmann <[email protected]>; Eric W. Biederman
> <[email protected]>; Alexander E. Patrakov <[email protected]>; Ahmed S. Darwish <[email protected]>; Willy
> Tarreau <[email protected]>; Matthew Garrett <[email protected]>; Vito Caputo <[email protected]>; Andreas Dilger
> <[email protected]>; Jan Kara <[email protected]>; Ray Strode <[email protected]>; William Jon McCann <[email protected]>;
> zhangjs <[email protected]>; Andy Lutomirski <[email protected]>; Florian Weimer <[email protected]>; Lennart
> Poettering <[email protected]>; Peter Matthias <[email protected]>; Marcelo Henrique Cerri
> <[email protected]>; Neil Horman <[email protected]>; Randy Dunlap <[email protected]>; Julia Lawall
> <[email protected]>; Dan Carpenter <[email protected]>; Andy Lavr <[email protected]>; Eric Biggers
> <[email protected]>; Jason A. Donenfeld <[email protected]>; Stephan Müller <[email protected]>; Petr Tesarik
> <[email protected]>
> Subject: Re: [DISCUSSION PATCH 00/41] random: possible ways towards NIST SP800-90B compliance
>
> <<< External Email >>>
> On Fri, Oct 02, 2020 at 02:34:44PM +0000, Van Leeuwen, Pascal wrote:
> >
> >
> >
> > > -----Original Message-----
> > > From: Greg Kroah-Hartman <[email protected]>
> > > Sent: Friday, October 2, 2020 4:04 PM
> > > To: Van Leeuwen, Pascal <[email protected]>
> > > Cc: Torsten Duwe <[email protected]>; Theodore Y. Ts'o <[email protected]>; [email protected]; Nicolai Stange
> > > <[email protected]>; LKML <[email protected]>; Arnd Bergmann <[email protected]>; Eric W. Biederman
> > > <[email protected]>; Alexander E. Patrakov <[email protected]>; Ahmed S. Darwish <[email protected]>; Willy
> > > Tarreau <[email protected]>; Matthew Garrett <[email protected]>; Vito Caputo <[email protected]>; Andreas Dilger
> > > <[email protected]>; Jan Kara <[email protected]>; Ray Strode <[email protected]>; William Jon McCann
> <[email protected]>;
> > > zhangjs <[email protected]>; Andy Lutomirski <[email protected]>; Florian Weimer <[email protected]>; Lennart
> > > Poettering <[email protected]>; Peter Matthias <[email protected]>; Marcelo Henrique Cerri
> > > <[email protected]>; Neil Horman <[email protected]>; Randy Dunlap <[email protected]>; Julia Lawall
> > > <[email protected]>; Dan Carpenter <[email protected]>; Andy Lavr <[email protected]>; Eric Biggers
> > > <[email protected]>; Jason A. Donenfeld <[email protected]>; Stephan Müller <[email protected]>; Petr Tesarik
> > > <[email protected]>
> > > Subject: Re: [DISCUSSION PATCH 00/41] random: possible ways towards NIST SP800-90B compliance
> > >
> > > <<< External Email >>>
> > > On Fri, Oct 02, 2020 at 01:35:18PM +0000, Van Leeuwen, Pascal wrote:
> > > > ** This message and any attachments are for the sole use of the intended recipient(s). It may contain information that is
> > > confidential and privileged. If you are not the intended recipient of this message, you are prohibited from printing, copying,
> > > forwarding or saving it. Please delete the message and attachments and notify the sender immediately. **
> > >
> > > As per my legal department requests, this is now ignored and deleted on
> > > my system...
> > >
> > > Hint, it's not a valid footer for public mailing lists...
> > >
> > > greg k-h
> > It's automatically added by our company mail server ... not something I can control at all :-(
>
> Then your company can not contribute in Linux kernel development, as
> this is obviously not allowed by such a footer.
>
Interesting, this has never been raised as a problem until today ...
Going back through my mail archive, it looks like they started automatically adding that some
3 months ago. Not that they informed anyone about that, it just silently happened.
> Please work with your IT and legal department to fix this.
>
Eh ... Greg ... that's not how that works in the real world. In the real world, legal and IT lay
down the law and you just comply with that (or hack your way around it, if you can ;-).
I'm already fighting the good fight trying to keep control of my development machines
because IT would just love to get rid of those (since not under IT control .... oh dear ...)
And obviously, you cannot do kernel development on a machine without root access.
It's annoying enough already to require IT support to provide explicit permission to open
the task manager on my own company laptop ... grmbl.
>
> thanks,
>
> greg k-h
Regards,
Pascal van Leeuwen
Silicon IP Architect Multi-Protocol Engines, Rambus Security
Rambus ROTW Holding BV
+31-73 6581953
Note: The Inside Secure/Verimatrix Silicon IP team was recently acquired by Rambus.
Please be so kind to update your e-mail address book with my new e-mail address.
** This message and any attachments are for the sole use of the intended recipient(s). It may contain information that is confidential and privileged. If you are not the intended recipient of this message, you are prohibited from printing, copying, forwarding or saving it. Please delete the message and attachments and notify the sender immediately. **
Rambus Inc.<http://www.rambus.com>
Eric Biggers <[email protected]> writes:
> On Fri, Oct 02, 2020 at 02:38:36PM +0200, Torsten Duwe wrote:
>>
>> Would some maintainer please comment on potential problems or
>> shortcomings?
>>
>
> Well, very people are experts in the Linux RNG *and* have time to review large
> patchsets, especially when three people are all proposing conflicting changes.
> And those that might be able to review these patches aren't necessarily
> interested in compliance with particular government standards.
To make it clear: I'm personally not really enthusiastic about some of
the restrictions imposed by SP800-90 either and Jason certainly has a
point with his concerns about "subpar crypto" ([1]). However, at the
same time I'm acknowledging that for some users FIPS compliance is
simply a necessity and I don't see a strong reason why that shouldn't be
supported, if doable without negatively affecting !fips_enabled users.
> Note that having multiple RNG implementations would cause fragmentation, more
> maintenance burden, etc. So IMO, that should be a last resort. Instead we
> should try to find an implementation that works for everyone. I.e., at least to
> me, Nicolai's patchset seems more on the right track than Stephan's patchset...
I suppose that this concern about fragmentation is among the main
reasons for reservations against Stephan's LRNG patchset and that's why
I posted this RFC series here for comparison purposes. But note that, as
said ([2]), it's incomplete and the only intent was to provide at least
a rough idea on what it would take to move the current /dev/random
implementation towards SP800-90 -- I was hoping for either a hard NACK
or something along the lines of "maybe, go ahead and let's see".
> However, not everyone cares about "compliance". So any changes for "compliance"
> either need to have a real technical argument for making the change, *or* need
> to be optional (e.g. controlled by fips_enabled).
Fully agreed.
> AFAICS, this patchset mostly just talks about NIST SP800-90B compliance, and
> doesn't make clear whether the changes make the RNG better, worse, or the same
> from an actual technical perspective.
>
> If that was properly explained, and if the answer was "better" or at least
> "not worse", I expect that people would be more interested.
The goal was not to negatively affect !fips_enabled users, but as
outlined in the cover letter ([2]), a performance impact had been
measured on ARMv7. This probably isn't something which couldn't get
sorted out, but I see no point in doing it at this stage, because
- there's still quite some stuff missing for full SP800-90 compliance
anyway, c.f. the overview at the end of [2] and
- such optimizations would have bloated this patchset even more,
e.g. for making fips_enabled a static_key, which should certainly go
into a separate series.
User visible effects set aside, an obvious downside of SP800-90
compliance would be the increase in code size and the associated
maintenance burden.
That being said, I can imagine that those boot health tests could also
get enabled for !fips_enabled users in the future, if wanted: rather
than inhibiting /dev/random output on failure, a warning would get
logged instead. Whether or not this would be seen as an improvement
is for others to judge though.
Thanks,
Nicolai
[1] https://lkml.kernel.org/r/CAHmME9rMXORFXtwDAc8yxj+h9gytJj6DpvCxA-JMAAgyOP+5Yw@mail.gmail.com
[2] https://lkml.kernel.org/r/[email protected]
--
SUSE Software Solutions Germany GmbH, Maxfeldstr. 5, 90409 Nürnberg, Germany
(HRB 36809, AG Nürnberg), GF: Felix Imendörffer