Jitterentropy: basic configuration

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:

1. Whether to use a variable, pseudorandom number of iterations in the noise generating functions.
2. 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.

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.

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

1. Repeat the tests reported above against different versions of Zircon, and ensure that the entropy estimates remain consistent.
2. 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).

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