The jitterentropy library is written by Stephan Mueller, is available at https://github.com/smuellerDD/jitterentropy-library, and is documented at http://www.chronox.de/jent.html. In Zircon, it's used as a simple entropy source to seed the system CPRNG.
This document describes and analyzes two (independent) configuration options of jitterentropy:
- Whether to use a variable, pseudorandom number of iterations in the noise generating functions.
- Whether to post-process the raw noise samples with jitterentropy's internal processing routines.
I consider these basic configuration options because the affect the basic process that jitterentropy uses. I'm contrasting them to tunable parameters (like the precise value used for loop counts if they are not chosen pseudorandomly, or the size of the scratch memory used internal by jitterentropy), since the tunable parameters don't greatly affect the means by which jitterentropy collects entropy, just the amount it collects and the time it takes.
My full conclusions are at the end of this document, but in summary I think that we should avoid both choosing pseudorandom iteration numbers and using the jitterentropy post-processed data.
Brief explanation of jitterentropy
The author's documentation is available in HTML form at http://www.chronox.de/jent/doc/CPU-Jitter-NPTRNG.html, or in PDF form at http://www.chronox.de/jent/doc/CPU-Jitter-NPTRNG.pdf. In brief, the library collects random bits from variations in CPU instruction timing.
Jitterentropy maintains a random state, in the form of a 64-bit number that is affected by many of the jitterentropy functions, and ultimately is used as the output randomness.
There are two noise sources, both of which are blocks of relatively slow-running code whose precise runtime is measured (using a system clock, requiring roughly nanosecond resolution). The precise time to complete these blocks of code will vary. We test these times to ensure that they are unpredictable; while we can't be perfectly certain that they are, the test results (including the results below) are encouraging. Note however that the purpose of this document is not to justify our estimates for the min-entropy in jitterentropy samples, but rather to discuss the two configuration options listed above.
The first of the code blocks used as a noise source is a CPU-intensive LFSR
loop, implemented in
the jent_lfsr_time function.
The number of times the LFSR logic is repeated is controlled by the
kernel.jitterentropy.ll cmdline ("ll" stands for "LFSR loops"). If ll = 0,
a pseudorandom count is used, and otherwise the value of ll is used.
Looking at the source code, the outer loop repeats according to the ll
parameter. The inner loop advances an LFSR by 64 steps, each time XOR-ing in
one bit from the most recent time sample. Passing the time sample through the
LFSR this way serves as a processing step, generally tending to whiten the
random timesteps. As described in the
entropy quality testing doc, it's important to
skip this processing when testing the entropic content of the CPU time
variations. It's also the case that enabling the processing increases the
entropy estimates by a suspicious amount in some cases (see
the "Effects of processing the raw samples" section).
The second noise source is a memory access loop, in
the jent_memaccess function.
The memory access loop is repeated according to the kernel.jitterentropy.ml
cmdline ("ml" for "memory loops"), where again a value of 0 activates the
pseudorandom loop count, and any non-zero value overrides the pseudorandom
count. Each iteration of the actual memory access loop both reads and writes a
relatively large chunk of memory, divided into kernel.jitterentropy.bc-many
blocks of size kernel.jitterentropy.bs bytes each. The default values when I
wrote the current document are bc = 1024 and bs = 64; up-to-date defaults
should be documented in
the cmdline document. For comparison, the defaults in
the jitterentropy source code are bc = 64 and bs = 32,
defined here.
Per the comment above the jent_memaccess function, the total memory size
should be larger than the L1 cache size of the target machine. Confusingly,
bc = 64 and bs = 32 produce a memory size of 2048 bytes, which is much
smaller than even most L1 caches (I couldn't find any CPU with more than 0 bytes
but less than 4KB of L1). Using bs = 64 and bc = 1024 result in 64KB of
memory, which is usually enough to overflow L1 data caches.
Option 1: Pseudorandom loop counts
Jitterentropy was originally designed so that the two noise generating functions
run a pseudorandom number of times. Specifically,
the jent_loop_shuffle function
mixes together (1) the time read from the high-resolution clock and (2)
jitterentropy's internal random state in order to decide how many times to run
the noise sources.
We added the ability to override these pseudorandom loop counts, and tested jitterentropy's performance both with and without the override. The results are discussed in more depth in the "Effects of pseudorandom loop counts" section, but in summary: the statistical tests suggested that the pseudorandom loop counts increased the entropy far more than expected. This makes me mistrust these higher entropy counts, so I recommend using the lower estimates and preferring deterministic loop counts to pseudorandom.
Jitterentropy's random data processing
As mentioned above, jitterentropy can process its random data, which makes the data look "more random". Specifically, the processing should decrease (and ideally remove) the deviation of the random data from the uniform distribution, and reduce (ideally, remove) any intercorrelations between random bytes.
The main function of interest for generating processed samples is
jent_gen_entropy,
which is called in a loop by
jent_read_entropy
to produce an arbitrarily large number of random bytes.
In essence, jent_gen_entropy calls the noise functions in a loop 64 times.
Each of the 64 invocations of jent_lfsr_time mixes the noisy time measurement
into the jitterentropy random state.
After these 64 iterations, the random state is optionally "stirred" in
jent_stir_pool
by XOR-ing with a "mixer" value, itself dependent on the jitterentropy random
state. As noted in the source code, this operation cannot increase or decrease
the entropy in the pool (since XOR is bijective), but it can potentially improve
the statistical appearance of the random state.
In principle, invoking the noise source functions 64 times should produce 64
times as much entropy, up to the maximum 64 bits that the random state can hold.
This assumes that the mixing operation in jent_lfsr_time is cryptographically
sound. I'm not an expert in cryptanalysis, but a LFSR itself is not a
cryptographically secure RNG, since 64 successive bits reveal the entire state
of a 64-bit LFSR, after which all past and future values can be easily
computed. I am not sure that the jitterentropy scheme — XOR-ing the time
measurement into the "bottom" of the LFSR as the LFSR is shifted — is more
secure. Without careful cryptographic examination of this scheme (which for all
I know may exist, but the I did not see it mentioned in the jitterentropy
documentation), I would lean towards using unprocessed samples, and mixing them
into our system entropy pool in a known-good way (e.g. SHA-2, as we do now).
That said, I did run the NIST test suite against processed data samples. My results are in the "Effects of processing the raw samples" section) below.
Testing process
The procedure for running entropy source quality tests is documented in the entropy quality tests document.
These preliminary results were gathered on a Zircon debug build on Raspberry Pi
3, built from commit 18358de5e90a012cb1e042efae83f5ea264d1502 in the now-obsolete project: https://fuchsia.googlesource.com/zircon/+/a1a80a6a7d
"[virtio][entropy] Basic virtio-rng driver". The following flags were set in
my local.mk file when building:
ENABLE_ENTROPY_COLLECTOR_TEST=1
ENTROPY_COLLECTOR_TEST_MAXLEN=1048576
I ran the boot-time tests after netbooting the debug kernel on the Pi with the
following kernel cmdline, varying the values of $ML, $LL, and $RAW:
kernel.entropy-test.src=jitterentropy
kernel.jitterentropy.bs=64
kernel.jitterentropy.bc=1024
kernel.jitterentropy.ml=$ML
kernel.jitterentropy.ll=$LL
kernel.jitterentropy.raw=$RAW
Test results and analysis
Effects of pseudorandom loop counts
Raw Data
Following the logic in the jitterentropy source code (search for
MAX_FOLD_LOOP_BIT
and
MAX_ACC_LOOP_BIT)
the pseudorandom loop counts vary within these ranges:
ml: 1 .. 128 (inclusive)
ll: 1 .. 16 (inclusive)
I have included the overall min-entropy estimate from the NIST suite in this table, as well as two contributing estimates: the compression estimate and the Markov estimate. The NIST min-entropy estimate is the minimum of 10 different estimates, including these two. The compression estimate is generally the smallest for jitterentropy raw samples with deterministic loop counts, and the Markov estimate is generally smallest for jitterentropy with other configurations.
ml |
ll |
min-entropy (bits / byte) | Compression estimate | Markov estimate |
|---|---|---|---|---|
| random (1 .. 128) | random (1 .. 16) | 5.77 | 6.84 | 5.77 |
| 128 | 16 | 1.62 | 1.62 | 3.60 |
| 1 | 1 | 0.20 | 0.20 | 0.84 |
In other words, varying the loop counts pseudorandomly increased the min-entropy estimate for raw samples by 4.15 bits (or 250%), compared to the deterministic version that always used the maximum values from the pseudorandom ranges.
Analysis
The pseudorandom loop count values are determined by adding one extra time sample per noise function. First, these time samples are not independent of the noise function time measurements, since the gaps between the loop count time samples correspond predictably to the noise function time measurements. As a result it would be highly questionable to assume that they increase the min-entropy of the output data at all. Second, it is absurd to imagine that the loop count time samples were somehow about 250% as random as the noise function time measurements, since both rely on the same noise source, except that the very first loop count time samples maybe get a small boost from the random amount of time needed to boot the system enough to run the test.
Consequently, I suspect that what happened is that the pseudorandom loop counts were enough to "fool" the particular suite of statistical tests and predictor-based tests in the NIST suite, but that a predictor test written with specific knowledge of how the jitterentropy pseudorandom loop counts are derived could in fact predict the output with far better accuracy. I think the "true" min-entropy in the pseudorandom loop count test, against an adversary that's specifically targeting our code, is within the bounds of the two deterministic tests, i.e. between about 0.20 and 1.62 bits per byte.
Using pseudorandom counts forces us to make an additional decision: do we
conservatively estimate the actual entropy content at 0.20 bits per byte (as if
the pseudorandom count function always chose ml = 1 and ll = 1)? Or do we
chose an average entropy content (there is probably a more intelligent averaging
technique than to compute (1.62 + 0.20) / 2 = 0.91 bits / byte, but that will
serve for the purpose of this discussion) and risk the pseudorandom loop counts
occasionally causing us to undershoot this average entropy content? If we are
too conservative, we will spend more time collecting entropy than is needed; if
we are too optimistic, we might have a security vulnerability. Ultimately, this
forces a trade-off between security (which prefers conservative entropy
estimates) and efficiency (which prefers optimistic entropy estimates).
Effects of processing the raw samples
Raw Data
I repeated the three tests reported above, but with jitterentropy's internal
processing turned on (with kernel.jitterentropy.raw = false instead of the
default value true). For convenience, the tables below include both the raw
sample results (copied from above) in the top three rows, and the processed
results (newly added) in the bottom three rows.
ml |
ll |
raw | min-entropy (bits / byte) | Compression estimate | Markov estimate |
|---|---|---|---|---|---|
| random (1 .. 128) | random (1 .. 16) | true | 5.77 | 6.84 | 5.77 |
| 128 | 16 | true | 1.62 | 1.62 | 3.60 |
| 1 | 1 | true | 0.20 | 0.20 | 0.84 |
ml |
ll |
raw | min-entropy (bits / byte) | Compression estimate | Markov estimate |
|---|---|---|---|---|---|
| random (1 .. 128) | random (1 .. 16) | false | 5.79 | 6.59 | 5.79 |
| 128 | 16 | false | 5.78 | 6.97 | 5.78 |
| 1 | 1 | false | 5.77 | 6.71 | 5.77 |
Analysis
The post-processing min-entropy estimates are all essentially equal (up to slight variations easily explained by randomness), and also equal to the min-entropy estimate for raw samples with pseudorandom loop counts.
Recall that jitterentropy's processed entropy is formed from 64 separate random
data samples, mixed together in a 64-bit internal state buffer. Each of the raw
samples corresponds to a sample in the raw = true table. In particular, it's
absurd to think that combining 64 samples with ml = 1 and ll = 1 then
processing these could produce (5.77 * 8) = 46.2 bits of entropy per 8 bytes of
processed output, since that would imply (46.2 / 64) = 0.72 bits of entropy per
unprocessed sample as opposed to the measured value of 0.20 bits.
This argument applies against the ml = 1, ll = 1, raw = false measurement,
but does not apply to ml = 128, ll = 16, raw = false. In particular,
combining 64 raw samples with ml = 128 and ll = 16 could in principle
collect (1.64 * 64 / 8) = 13.1 bits of entropy per processed byte, except that
of course there is a hard limit at 8 bits per byte.
Interestingly, the minimal entropy estimator switches from the compression estimate to the Markov estimator. My theory is that the additional "confusion" from post-processing is enough to "fool" the compression estimate. If there is a cryptographic vulnerability in the jitterentropy processing routine, it may be possible to write a similar estimator that reveals a significantly smaller min-entropy. If we use the general-purpose tests to decide how many raw samples to collect in order to have 256 of min-entropy, but an adversary uses a targeted attack, then (relative to this targeted attack) our system may have less entropy in its entropy pool than we expect. This is a security vulnerability.
If there is a very bad weakness in the jitterentropy processing routine, it may
in fact be reducing the "true" entropy in jitterentropy's internal pool. The
arithmetical argument regarding ml = 1 and ll = 1 shows that we can't trust
the NIST test suite to accurately measure the actual min-entropy in the
processed data, so it is possible that the processing actually reduces
min-entropy and our tools just can't detect the loss. This would exacerbate the
vulnerability described in the previous paragraph.
Conclusions
Jitterentropy's pseudorandom loop counts are of questionable benefit at best, and if used they force us to make a security/efficiency trade-off. Unless we can show convincing evidence that the pseudorandom times really do drastically increase entropy estimates rather than just defeating the NIST test suite, we should use deterministic loop counts, ideally tuned for performance on a per-target basis.
Jitterentropy's processing is also questionable, since (to my knowledge) it hasn't been subjected to enough cryptographic analysis and testing to be trusted. Furthermore, we can't directly measure the min-entropy in the post-processed data via the NIST test suite, so if there is a cryptographic vulnerability we can't easily detect it. I think we should instead rely on the entropy mixing code in the Zircon CPRNG (based on SHA-2), and leave jitterentropy's processing disabled.
TODOs
- Repeat the tests reported above against different versions of Zircon, and ensure that the entropy estimates remain consistent.
- Repeat the tests on different platforms and targets (note: x86 targets don't currently have access to a system clock during early boot, so the early boot entropy tests and early boot CPRNG seeding don't yet support jitterentropy on x86).
Automate the process of running the tests and generating the reports in this document. Specifically, the tests should compare:
- pseudorandom loop counts versus various deterministic loop count values
- raw samples versus processed data