crypto: jitter - use permanent health test storage

The health test result in the current code is only given for the currently
processed raw time stamp. This implies to react on the health test error,
the result must be checked after each raw time stamp being processed. To
avoid this constant checking requirement, any health test error is recorded
and stored to be analyzed at a later time, if needed.

This change ensures that the power-up test catches any health test error.
Without that patch, the power-up health test result is not enforced.

The introduced changes are already in use with the user space version of
the Jitter RNG.

Fixes: 04597c8dd6c4 ("jitter - add RCT/APT support for different OSRs")
Reported-by: Joachim Vandersmissen <git@jvdsn.com>
Signed-off-by: Stephan Mueller <smueller@chronox.de>
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

crypto: jitter - reuse allocated entropy collector

In case a health test error occurs during runtime, the power-up health
tests are rerun to verify that the noise source is still good and
that the reported health test error was an outlier. For performing this
power-up health test, the already existing entropy collector instance
is used instead of allocating a new one. This change has the following
implications:

* The noise that is collected as part of the newly run health tests is
inserted into the entropy collector and thus stirs the existing
data present in there further. Thus, the entropy collected during
the health test is not wasted. This is also allowed by SP800-90B.

* The power-on health test is not affected by the state of the entropy
collector, because it resets the APT / RCT state. The remainder of
the state is unrelated to the health test as it is only applied to
newly obtained time stamps.

This change also fixes a bug report about an allocation while in an
atomic lock (the lock is taken in jent_kcapi_random, jent_read_entropy
is called and this can call jent_entropy_init).

Fixes: 04597c8dd6c4 ("jitter - add RCT/APT support for different OSRs")
Reported-by: Dan Carpenter <dan.carpenter@linaro.org>
Signed-off-by: Stephan Mueller <smueller@chronox.de>
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

crypto: jitter - Allow configuration of memory size

The memory size consumed by the Jitter RNG is one contributing factor in
the amount of entropy that is gathered. As the amount of entropy
directly correlates with the distance of the memory from the CPU, the
caches that are possibly present on a given system have an impact on the
collected entropy.

Thus, the kernel compile time should offer a means to configure the
amount of memory used by the Jitter RNG. Although this option could be
turned into a runtime option (e.g. a kernel command line option), it
should remain a compile time option as otherwise adminsitrators who may
not have performed an entropy assessment may select a value that is
inappropriate.

The default value selected by the configuration is identical to the
current Jitter RNG value. Thus, the patch should not lead to any change
in the Jitter RNG behavior.

To accommodate larger memory buffers, kvzalloc / kvfree is used.

Signed-off-by: Stephan Mueller <smueller@chronox.de>
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

crypto: jitter - add RCT/APT support for different OSRs

The oversampling rate (OSR) value specifies the heuristically implied
entropy in the recorded data - H_submitter = 1/osr. A different entropy
estimate implies a different APT/RCT cutoff value. This change adds
support for OSRs 1 through 15. This OSR can be selected by the caller
of the Jitter RNG.

For this patch, the caller still uses one hard-coded OSR. A subsequent
patch allows this value to be configured.

In addition, the power-up self test is adjusted as follows:

* It allows the caller to provide an oversampling rate that should be
tested with - commonly it should be the same as used for the actual
runtime operation. This makes the power-up testing therefore consistent
with the runtime operation.

* It calls now jent_measure_jitter (i.e. collects the full entropy
that can possibly be harvested by the Jitter RNG) instead of only
jent_condition_data (which only returns the entropy harvested from
the conditioning component). This should now alleviate reports where
the Jitter RNG initialization thinks there is too little entropy.

* The power-up test now solely relies on the (enhanced) APT and RCT
test that is used as a health test at runtime.

The code allowing the different OSRs as well as the power-up test
changes are present in the user space version of the Jitter RNG 3.4.1
and thus was already in production use for some time.

Reported-by "Ospan, Abylay" <aospan@amazon.com>
Signed-off-by: Stephan Mueller <smueller@chronox.de>
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

crypto: jitter - Add clarifying comments to Jitter Entropy RCT cutoff values

The RCT cutoff values are correct, but they don't exactly match the ones
one would expect when computing them using the formula in SP800-90B. This
discrepancy is due to the fact that the Jitter Entropy RCT starts at 1. To
avoid any confusion by future reviewers, add some comments and explicitly
subtract 1 from the "correct" cutoff values in the definitions.

Signed-off-by: Joachim Vandersmissen <git@jvdsn.com>
Reviewed-by: Stephan Mueller <smueller@chronox.de>
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

crypto: jitter - correct health test during initialization

With the update of the permanent and intermittent health errors, the
actual indicator for the health test indicates a potential error only
for the one offending time stamp gathered in the current iteration
round. The next iteration round will "overwrite" the health test result.

Thus, the entropy collection loop in jent_gen_entropy checks for
the health test failure upon each loop iteration. However, the
initialization operation checked for the APT health test once for
an APT window which implies it would not catch most errors.

Thus, the check for all health errors is now invoked unconditionally
during each loop iteration for the startup test.

With the change, the error JENT_ERCT becomes unused as all health
errors are only reported with the JENT_HEALTH return code. This
allows the removal of the error indicator.

Fixes: 3fde2fe99aa6 ("crypto: jitter - permanent and intermittent health errors"
)
Reported-by: Joachim Vandersmissen <git@jvdsn.com>
Signed-off-by: Stephan Mueller <smueller@chronox.de>
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

crypto: jitter - replace LFSR with SHA3-256

Using the kernel crypto API, the SHA3-256 algorithm is used as
conditioning element to replace the LFSR in the Jitter RNG. All other
parts of the Jitter RNG are unchanged.

The application and use of the SHA-3 conditioning operation is identical
to the user space Jitter RNG 3.4.0 by applying the following concept:

- the Jitter RNG initializes a SHA-3 state which acts as the "entropy
pool" when the Jitter RNG is allocated.

- When a new time delta is obtained, it is inserted into the "entropy
pool" with a SHA-3 update operation. Note, this operation in most of
the cases is a simple memcpy() onto the SHA-3 stack.

- To cause a true SHA-3 operation for each time delta operation, a
second SHA-3 operation is performed hashing Jitter RNG status
information. The final message digest is also inserted into the
"entropy pool" with a SHA-3 update operation. Yet, this data is not
considered to provide any entropy, but it shall stir the entropy pool.

- To generate a random number, a SHA-3 final operation is performed to
calculate a message digest followed by an immediate SHA-3 init to
re-initialize the "entropy pool". The obtained message digest is one
block of the Jitter RNG that is returned to the caller.

Mathematically speaking, the random number generated by the Jitter RNG
is:

aux_t = SHA-3(Jitter RNG state data)

Jitter RNG block = SHA-3(time_i || aux_i || time_(i-1) || aux_(i-1) ||
... || time_(i-255) || aux_(i-255))

when assuming that the OSR = 1, i.e. the default value.

This operation implies that the Jitter RNG has an output-blocksize of
256 bits instead of the 64 bits of the LFSR-based Jitter RNG that is
replaced with this patch.

The patch also replaces the varying number of invocations of the
conditioning function with one fixed number of invocations. The use
of the conditioning function consistent with the userspace Jitter RNG
library version 3.4.0.

The code is tested with a system that exhibited the least amount of
entropy generated by the Jitter RNG: the SiFive Unmatched RISC-V
system. The measured entropy rate is well above the heuristically
implied entropy value of 1 bit of entropy per time delta. On all other
tested systems, the measured entropy rate is even higher by orders
of magnitude. The measurement was performed using updated tooling
provided with the user space Jitter RNG library test framework.

The performance of the Jitter RNG with this patch is about en par
with the performance of the Jitter RNG without the patch.

Signed-off-by: Stephan Mueller <smueller@chronox.de>
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

crypto: jitter - permanent and intermittent health errors

According to SP800-90B, two health failures are allowed: the intermittend
and the permanent failure. So far, only the intermittent failure was
implemented. The permanent failure was achieved by resetting the entire
entropy source including its health test state and waiting for two or
more back-to-back health errors.

This approach is appropriate for RCT, but not for APT as APT has a
non-linear cutoff value. Thus, this patch implements 2 cutoff values
for both RCT/APT. This implies that the health state is left untouched
when an intermittent failure occurs. The noise source is reset
and a new APT powerup-self test is performed. Yet, whith the unchanged
health test state, the counting of failures continues until a permanent
failure is reached.

Any non-failing raw entropy value causes the health tests to reset.

The intermittent error has an unchanged significance level of 2^-30.
The permanent error has a significance level of 2^-60. Considering that
this level also indicates a false-positive rate (see SP800-90B section 4.2)
a false-positive must only be incurred with a low probability when
considering a fleet of Linux kernels as a whole. Hitting the permanent
error may cause a panic(), the following calculation applies: Assuming
that a fleet of 10^9 Linux kernels run concurrently with this patch in
FIPS mode and on each kernel 2 health tests are performed every minute
for one year, the chances of a false positive is about 1:1000
based on the binomial distribution.

In addition, any power-up health test errors triggered with
jent_entropy_init are treated as permanent errors.

A permanent failure causes the entire entropy source to permanently
return an error. This implies that a caller can only remedy the situation
by re-allocating a new instance of the Jitter RNG. In a subsequent
patch, a transparent re-allocation will be provided which also changes
the implied heuristic entropy assessment.

In addition, when the kernel is booted with fips=1, the Jitter RNG
is defined to be part of a FIPS module. The permanent error of the
Jitter RNG is translated as a FIPS module error. In this case, the entire
FIPS module must cease operation. This is implemented in the kernel by
invoking panic().

The patch also fixes an off-by-one in the RCT cutoff value which is now
set to 30 instead of 31. This is because the counting of the values
starts with 0.

Reviewed-by: Vladis Dronov <vdronov@redhat.com>
Signed-off-by: Stephan Mueller <smueller@chronox.de>
Reviewed-by: Marcelo Henrique Cerri <marcelo.cerri@canonical.com>
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

crypto: jitter - add oversampling of noise source

The output n bits can receive more than n bits of min entropy, of course,
but the fixed output of the conditioning function can only asymptotically
approach the output size bits of min entropy, not attain that bound.
Random maps will tend to have output collisions, which reduces the
creditable output entropy (that is what SP 800-90B Section 3.1.5.1.2
attempts to bound).

The value "64" is justified in Appendix A.4 of the current 90C draft,
and aligns with NIST's in "epsilon" definition in this document, which is
that a string can be considered "full entropy" if you can bound the min
entropy in each bit of output to at least 1-epsilon, where epsilon is
required to be <= 2^(-32).

Note, this patch causes the Jitter RNG to cut its performance in half in
FIPS mode because the conditioning function of the LFSR produces 64 bits
of entropy in one block. The oversampling requires that additionally 64
bits of entropy are sampled from the noise source. If the conditioner is
changed, such as using SHA-256, the impact of the oversampling is only
one fourth, because for the 256 bit block of the conditioner, only 64
additional bits from the noise source must be sampled.

This patch is derived from the user space jitterentropy-library.

Signed-off-by: Stephan Mueller <smueller@chronox.de>
Reviewed-by: Simo Sorce <simo@redhat.com>
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

crypto: jitter - quit sample collection loop upon RCT failure

The jitterentropy collection loop in jent_gen_entropy() can in principle
run indefinitely without making any progress if it only receives stuck
measurements as determined by jent_stuck(). After 31 consecutive stuck
samples, the Repetition Count Test (RCT) would fail anyway and the
jitterentropy RNG instances moved into ->health_failure == 1 state.
jent_gen_entropy()'s caller, jent_read_entropy() would then check for
this ->health_failure condition and return an error if found set. It
follows that there's absolutely no point in continuing the collection loop
in jent_gen_entropy() once the RCT has failed.

Make the jitterentropy collection loop more robust by terminating it upon
jent_health_failure() so that it won't continue to run indefinitely without
making any progress.

Signed-off-by: Nicolai Stange <nstange@suse.de>
Reviewed-by: Stephan Mueller <smueller@chronox.de>
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

crypto: jitter - don't limit ->health_failure check to FIPS mode

The jitterentropy's Repetition Count Test (RCT) as well as the Adaptive
Proportion Test (APT) are run unconditionally on any collected samples.
However, their result, i.e. ->health_failure, will only get checked if
fips_enabled is set, c.f. the jent_health_failure() wrapper.

I would argue that a RCT or APT failure indicates that something's
seriously off and that this should always be reported as an error,
independently of whether FIPS mode is enabled or not: it should be up to
callers whether or not and how to handle jitterentropy failures.

Make jent_health_failure() to unconditionally return ->health_failure,
independent of whether fips_enabled is set.

Note that fips_enabled isn't accessed from the jitterentropy code anymore
now. Remove the linux/fips.h include as well as the jent_fips_enabled()
wrapper.

Signed-off-by: Nicolai Stange <nstange@suse.de>
Reviewed-by: Stephan Mueller <smueller@chronox.de>
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

crypto: jitter - consider 32 LSB for APT

The APT compares the current time stamp with a pre-set value. The
current code only considered the 4 LSB only. Yet, after reviews by
mathematicians of the user space Jitter RNG version >= 3.1.0, it was
concluded that the APT can be calculated on the 32 LSB of the time
delta. Thi change is applied to the kernel.

This fixes a bug where an AMD EPYC fails this test as its RDTSC value
contains zeros in the LSB. The most appropriate fix would have been to
apply a GCD calculation and divide the time stamp by the GCD. Yet, this
is a significant code change that will be considered for a future
update. Note, tests showed that constantly the GCD always was 32 on
these systems, i.e. the 5 LSB were always zero (thus failing the APT
since it only considered the 4 LSB for its calculation).

Signed-off-by: Stephan Mueller <smueller@chronox.de>
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

crypto: jitter - drop kernel-doc notation

Drop "begin kernel-doc (/**)" entries in jitterentropy.c
since they are not in kernel-doc format and they cause
many complaints (warnings) from scripts/kernel-doc.

Signed-off-by: Randy Dunlap <rdunlap@infradead.org>
Cc: Stephan Mueller <smueller@chronox.de>
Cc: Herbert Xu <herbert@gondor.apana.org.au>
Cc: "David S. Miller" <davem@davemloft.net>
Cc: linux-crypto@vger.kernel.org
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

crypto: jitterentropy - Put constants on the right side of the expression

This patch fixes the following checkpatch.pl warnings:

crypto/jitterentropy.c:600: WARNING: Comparisons should place the constant on the right side of the test
crypto/jitterentropy.c:681: WARNING: Comparisons should place the constant on the right side of the test
crypto/jitterentropy.c:772: WARNING: Comparisons should place the constant on the right side of the test
crypto/jitterentropy.c:829: WARNING: Comparisons should place the constant on the right side of the test

Signed-off-by: Milan Djurovic <mdjurovic@zohomail.com>
Reviewed-by: Stephan Mueller <smueller@chronox.de>
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

crypto: Replace HTTP links with HTTPS ones

Rationale:
Reduces attack surface on kernel devs opening the links for MITM
as HTTPS traffic is much harder to manipulate.

Deterministic algorithm:
For each file:
If not .svg:
For each line:
If doesn't contain `\bxmlns\b`:
For each link, `\bhttp://[^# \t\r\n]*(?:\w|/)`:
If neither `\bgnu\.org/license`, nor `\bmozilla\.org/MPL\b`:
If both the HTTP and HTTPS versions
return 200 OK and serve the same content:
Replace HTTP with HTTPS.

Signed-off-by: Alexander A. Klimov <grandmaster@al2klimov.de>
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

crypto: jitter - SP800-90B compliance

SP800-90B specifies various requirements for the noise source(s) that
may seed any DRNG including SP800-90A DRBGs. In November 2020,
SP800-90B will be mandated for all noise sources that provide entropy
to DRBGs as part of a FIPS 140-[2|3] validation or other evaluation
types. Without SP800-90B compliance, a noise source is defined to always
deliver zero bits of entropy.

This patch ports the SP800-90B compliance from the user space Jitter RNG
version 2.2.0.

The following changes are applied:

- addition of (an enhanced version of) the repetitive count test (RCT)
from SP800-90B section 4.4.1 - the enhancement is due to the fact of
using the stuck test as input to the RCT.

- addition of the adaptive proportion test (APT) from SP800-90B section
4.4.2

- update of the power-on self test to perform a test measurement of 1024
noise samples compliant to SP800-90B section 4.3

- remove of the continuous random number generator test which is
replaced by APT and RCT

Health test failures due to the SP800-90B operation are only enforced in
FIPS mode. If a runtime health test failure is detected, the Jitter RNG
is reset. If more than 1024 resets in a row are performed, a permanent
error is returned to the caller.

Signed-off-by: Stephan Mueller <smueller@chronox.de>
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

crypto: jitter - add header to fix buildwarnings

Fix the following build warnings by adding a header for
the definitions shared between jitterentropy.c and
jitterentropy-kcapi.c. Fixes the following:

crypto/jitterentropy.c:445:5: warning: symbol 'jent_read_entropy' was not declared. Should it be static?
crypto/jitterentropy.c:475:18: warning: symbol 'jent_entropy_collector_alloc' was not declared. Should it be static?
crypto/jitterentropy.c:509:6: warning: symbol 'jent_entropy_collector_free' was not declared. Should it be static?
crypto/jitterentropy.c:516:5: warning: symbol 'jent_entropy_init' was not declared. Should it be static?
crypto/jitterentropy-kcapi.c:59:6: warning: symbol 'jent_zalloc' was not declared. Should it be static?
crypto/jitterentropy-kcapi.c:64:6: warning: symbol 'jent_zfree' was not declared. Should it be static?
crypto/jitterentropy-kcapi.c:69:5: warning: symbol 'jent_fips_enabled' was not declared. Should it be static?
crypto/jitterentropy-kcapi.c:74:6: warning: symbol 'jent_panic' was not declared. Should it be static?
crypto/jitterentropy-kcapi.c:79:6: warning: symbol 'jent_memcpy' was not declared. Should it be static?
crypto/jitterentropy-kcapi.c:93:6: warning: symbol 'jent_get_nstime' was not declared. Should it be static?

Signed-off-by: Ben Dooks <ben.dooks@codethink.co.uk>
Reviewed-by: Stephan Mueller <smueller@chronox.de
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

crypto: jitter - fix comments

One should not say "ec can be NULL" and then dereference it.
One cannot talk about the return value if the function returns void.

Signed-off-by: Alexander E. Patrakov <patrakov@gmail.com>
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

crypto: jitter - update implementation to 2.1.2

The Jitter RNG implementation is updated to comply with upstream version
2.1.2. The change covers the following aspects:

* Time variation measurement is conducted over the LFSR operation
instead of the XOR folding

* Invcation of stuck test during initialization

* Removal of the stirring functionality and the Von-Neumann
unbiaser as the LFSR using a primitive and irreducible polynomial
generates an identical distribution of random bits

This implementation was successfully used in FIPS 140-2 validations
as well as in German BSI evaluations.

This kernel implementation was tested as follows:

* The unchanged kernel code file jitterentropy.c is compiled as part
of user space application to generate raw unconditioned noise
data. That data is processed with the NIST SP800-90B non-IID test
tool to verify that the kernel code exhibits an equal amount of noise
as the upstream Jitter RNG version 2.1.2.

* Using AF_ALG with the libkcapi tool of kcapi-rng the Jitter RNG was
output tested with dieharder to verify that the output does not
exhibit statistical weaknesses. The following command was used:
kcapi-rng -n "jitterentropy_rng" -b 100000000000 | dieharder -a -g 200

* The unchanged kernel code file jitterentropy.c is compiled as part
of user space application to test the LFSR implementation. The
LFSR is injected a monotonically increasing counter as input and
the output is fed into dieharder to verify that the LFSR operation
does not exhibit statistical weaknesses.

* The patch was tested on the Muen separation kernel which returns
a more coarse time stamp to verify that the Jitter RNG does not cause
regressions with its initialization test considering that the Jitter
RNG depends on a high-resolution timer.

Tested-by: Reto Buerki <reet@codelabs.ch>
Signed-off-by: Stephan Mueller <smueller@chronox.de>
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

crypto: jitterentropy - Delete unnecessary checks before the function call "kzfree"

The kzfree() function tests whether its argument is NULL and then
returns immediately. Thus the test around the call is not needed.

This issue was detected by using the Coccinelle software.

Signed-off-by: Markus Elfring <elfring@users.sourceforge.net>
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

crypto: jitterentropy - avoid compiler warnings

The core of the Jitter RNG is intended to be compiled with -O0. To
ensure that the Jitter RNG can be compiled on all architectures,
separate out the RNG core into a stand-alone C file that can be compiled
with -O0 which does not depend on any kernel include file.

As no kernel includes can be used in the C file implementing the core
RNG, any dependencies on kernel code must be extracted.

A second file provides the link to the kernel and the kernel crypto API
that can be compiled with the regular compile options of the kernel.

Signed-off-by: Stephan Mueller <smueller@chronox.de>
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

crypto: drbg - use pragmas for disabling optimization

Replace the global -O0 compiler flag from the Makefile with GCC
pragmas to mark only the functions required to be compiled without
optimizations.

This patch also adds a comment describing the rationale for the
functions chosen to be compiled without optimizations.

Signed-off-by: Stephan Mueller <smueller@chronox.de>
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

crypto: jitterentropy - remove timekeeping_valid_for_hres

The patch removes the use of timekeeping_valid_for_hres which is now
marked as internal for the time keeping subsystem. The jitterentropy
does not really require this verification as a coarse timer (when
random_get_entropy is absent) is discovered by the initialization test
of jent_entropy_init, which would cause the jitter rng to not load in
that case.

Reported-by: kbuild test robot <fengguang.wu@intel.com>
Signed-off-by: Stephan Mueller <smueller@chronox.de>
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

crypto: jitterentropy - add jitterentropy RNG

The CPU Jitter RNG provides a source of good entropy by
collecting CPU executing time jitter. The entropy in the CPU
execution time jitter is magnified by the CPU Jitter Random
Number Generator. The CPU Jitter Random Number Generator uses
the CPU execution timing jitter to generate a bit stream
which complies with different statistical measurements that
determine the bit stream is random.

The CPU Jitter Random Number Generator delivers entropy which
follows information theoretical requirements. Based on these
studies and the implementation, the caller can assume that
one bit of data extracted from the CPU Jitter Random Number
Generator holds one bit of entropy.

The CPU Jitter Random Number Generator provides a decentralized
source of entropy, i.e. every caller can operate on a private
state of the entropy pool.

The RNG does not have any dependencies on any other service
in the kernel. The RNG only needs a high-resolution time
stamp.

Further design details, the cryptographic assessment and
large array of test results are documented at
http://www.chronox.de/jent.html.

CC: Andreas Steffen <andreas.steffen@strongswan.org>
CC: Theodore Ts'o <tytso@mit.edu>
CC: Sandy Harris <sandyinchina@gmail.com>
Signed-off-by: Stephan Mueller <smueller@chronox.de>
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>