Hi Stephan,
On Thursday, 2 January 2025 at 13:56:59 Stephan Mueller <smueller@xxxxxxxxxx> wrote:
> Am Donnerstag, 2. Januar 2025, 11:33:08 CET schrieb Francesco Valla:
>
> Hi Francesco,
>
> > That would be wonderful! Whenever you have the time, please let me know what
> > analysis you need.
> >
>
> Ok, some background: the Jitter RNG technically has 2 noise sources which are
> sampled concurrently:
>
> 1. variations of the execution of CPU instructions
>
> 2. variations of memory access times
>
> For (1) the Jitter RNG has a fixed set of instructions it performs the
> execution time measurements for: the SHA-3 conditioning operation
> (specifically the Keccak sponge function). For that, it performs a given set
> of Keccak operations.
>
> For (2) the Jitter RNG allocates a fixed set of memory and simply reads /
> writes data there and measures this timing.
>
>
> For (1), the more instructions are samples, the higher the entropy gathered.
> This means more time is required to sample that entropy. I.e. when you
> increase the number of measured Keccak operations, you get more entropy.
>
> For (2), when the memory is large enough to "spill over" into the next type of
> memory (from L1 to L2 to L3 to RAM), the higher the entropy gathered.
>
>
> So, for (2), to get more entropy, is invariant from the execution time. But
> for (1), the entropy rate depends on the execution time.
>
>
> Thus, what you want is to try to reduce the time spend for (1).
>
>
> The key now is that the overall entropy rate the Jitter RNG requires for
> functioning must be such that when gathering 256 bits of data from it, it
> contains 256 bits of entropy.
>
>
> Now, there are 2 "knobs" to turn via Kconfig:
>
> - the oversampling rate (OSR): given that the individual number of rounds for
> (1) and the number of accesses for (2) are kept the same, the OSR causes the
> Jitter RNG to multiply the round counts. For example, the baseline with OSR ==
> 1 is that for gathering 256 bits of entropy, 256 times both noise sources are
> sampled. For an OSR of, say, 3, to get 256 bits of entropy, 3 * 256 = 768
> times both noise sources are sampled. This value was changed from 1 to 3 for
> 6.11 because there were reports on some CPUs that the Jitter RNG did not
> produce sufficient entropy - most CPUs, however, can perfectly live with OSR
> == 1.
>
> - the amount of memory for (2) can be increased. The default is 2kBytes which
> usually means that the L1 can fully handle the accesses.
>
>
This was a very instructive read. I didn't (yet?) have the time to dive deep
into all the crypto "backbone", but I think I understood in broad terms.
Thank you!
> ======
>
>
> Now given the description, what can you do? I would apply the following steps:
>
> 1. measure whether the timer your system has is really a high-res timer (the
> higher the resolution, the higher the detected variations and thus the
> entropy)
>
Resolution reported by clock_getres() is 1ns. Is this sufficient?
> 2. assuming that test 1 shows a high res timer, reduce the OSR back to 1
> (CRYPTO_JITTERENTROPY_OSR) and measure the entropy rate -
>
Turned out my system already had the OSR set to 1, since CONFIG_CRYPTO_FIPS was
set to N.
> 3. if test 2 shows insufficient entropy, increase the amount of memory
> (CRYPTO_JITTERENTROPY_MEMSIZE_*) and measure the entropy rate
>
>
>
> The tool for measuring the entropy rate is given in [1] - check the README as
> you need to enable a kernel config option to get an interface into the Jitter
> RNG from user space. As you may not have the analysis tool, you may give the
> data to me and I can analyze it.
>
Here are the results (with default parameters for processdata.sh:
Opening file: '../results-analysis-runtime/raw_noise.0Fbitout.data' (SHA-256 hash 079f14467f309991a0bcaac2b667283ff1f19eba0ddf1fbd6b34e55a6d94ed87)
Loaded 1000000 samples of 16 distinct 4-bit-wide symbols
Number of Binary Symbols: 4000000
Running non-IID tests...
Running Most Common Value Estimate...
Bitstring MCV Estimate: mode = 2027350, p-hat = 0.50683750000000005, p_u = 0.50748139719173813
Most Common Value Estimate (bit string) = 0.978573 / 1 bit(s)
Literal MCV Estimate: mode = 68652, p-hat = 0.068652000000000005, p_u = 0.069303328207377918
Most Common Value Estimate = 3.850932 / 4 bit(s)
Running Entropic Statistic Estimates (bit strings only)...
Bitstring Collision Estimate: X-bar = 2.4981538638330933, sigma-hat = 0.49999674790330145, p = 0.53784137679559285
Collision Test Estimate (bit string) = 0.894747 / 1 bit(s)
Bitstring Markov Estimate: P_0 = 0.50683750000000005, P_1 = 0.49316249999999995, P_0,0 = 0.50927960145016893, P_0,1 = 0.49072039854983107, P_1,0 = 0.50432742976576173, P_1,1 = 0.49567257023423827, p_max = 3.0783392443248932e-38
Markov Test Estimate (bit string) = 0.973524 / 1 bit(s)
Bitstring Compression Estimate: X-bar = 5.2062336468660613, sigma-hat = 1.0200139851715606, p = 0.037082666137132736
Compression Test Estimate (bit string) = 0.792185 / 1 bit(s)
Running Tuple Estimates...
Bitstring t-Tuple Estimate: t = 18, p-hat_max = 0.5303003556530639666278, p_u = 0.5309431295223588315809
Bitstring LRS Estimate: u = 19, v = 43, p-hat = 0.50389349457067132, p_u = 0.50453743245287026
T-Tuple Test Estimate (bit string) = 0.913371 / 1 bit(s)
Literal t-Tuple Estimate: t = 4, p-hat_max = 0.0814448250695374631388, p_u = 0.08214935860193944897723
Literal LRS Estimate: u = 5, v = 9, p-hat = 0.063061514307713893, p_u = 0.063687630641525933
T-Tuple Test Estimate = 3.605607 / 4 bit(s)
LRS Test Estimate (bit string) = 0.986967 / 1 bit(s)
LRS Test Estimate = 3.972843 / 4 bit(s)
Running Predictor Estimates...
Bitstring MultiMCW Prediction Estimate: N = 3999937, Pglobal' = 0.50734663518092882 (C = 2026779) Plocal can't affect result (r = 25)
Multi Most Common in Window (MultiMCW) Prediction Test Estimate (bit string) = 0.978956 / 1 bit(s)
Literal MultiMCW Prediction Estimate: N = 999937, Pglobal' = 0.071847840262787413 (C = 71181) Plocal can't affect result (r = 6)
Multi Most Common in Window (MultiMCW) Prediction Test Estimate = 3.798911 / 4 bit(s)
Bitstring Lag Prediction Estimate: N = 3999999, Pglobal' = 0.50760302185063 (C = 2027836) Plocal can't affect result (r = 23)
Lag Prediction Test Estimate (bit string) = 0.978227 / 1 bit(s)
Literal Lag Prediction Estimate: N = 999999, Pglobal' = 0.07177509499573978 (C = 71113) Plocal can't affect result (r = 6)
Lag Prediction Test Estimate = 3.800373 / 4 bit(s)
Bitstring MultiMMC Prediction Estimate: N = 3999998, Pglobal' = 0.50910236964447519 (C = 2033833) Plocal can't affect result (r = 23)
Multi Markov Model with Counting (MultiMMC) Prediction Test Estimate (bit string) = 0.973972 / 1 bit(s)
Literal MultiMMC Prediction Estimate: N = 999998, Pglobal' = 0.06979561605633619 (C = 69142) Plocal can't affect result (r = 6)
Multi Markov Model with Counting (MultiMMC) Prediction Test Estimate = 3.840720 / 4 bit(s)
Bitstring LZ78Y Prediction Estimate: N = 3999983, Pglobal' = 0.50745980290740611 (C = 2027255) Plocal can't affect result (r = 25)
LZ78Y Prediction Test Estimate (bit string) = 0.978635 / 1 bit(s)
Literal LZ78Y Prediction Estimate: N = 999983, Pglobal' = 0.068264919012970812 (C = 67617) Plocal can't affect result (r = 5)
LZ78Y Prediction Test Estimate = 3.872712 / 4 bit(s)
H_original: 3.605607
H_bitstring: 0.792185
min(H_original, 4 X H_bitstring): 3.168741
---
Opening file: '../results-analysis-runtime/raw_noise.FFbitout.data' (SHA-256 hash 670cc4f908a3fa430112387c7490280b801fbc3e0d9b2eb5725a7382f1726353)
Loaded 1000000 samples of 256 distinct 8-bit-wide symbols
Number of Binary Symbols: 8000000
Running non-IID tests...
Running Most Common Value Estimate...
Bitstring MCV Estimate: mode = 4293572, p-hat = 0.53669650000000002, p_u = 0.53715061859478275
Most Common Value Estimate (bit string) = 0.896601 / 1 bit(s)
Literal MCV Estimate: mode = 25394, p-hat = 0.025394, p_u = 0.025799226085884197
Most Common Value Estimate = 5.276528 / 8 bit(s)
Running Entropic Statistic Estimates (bit strings only)...
Bitstring Collision Estimate: X-bar = 2.4368621131861672, sigma-hat = 0.4959976634888219, p = 0.67866590835207607
Collision Test Estimate (bit string) = 0.559227 / 1 bit(s)
Bitstring Markov Estimate: P_0 = 0.53669650000000002, P_1 = 0.46330349999999998, P_0,0 = 0.58912975024059222, P_0,1 = 0.41087024975940778, P_1,0 = 0.47595730335441655, P_1,1 = 0.52404269664558345, p_max = 3.5198162547162731e-30
Markov Test Estimate (bit string) = 0.764393 / 1 bit(s)
Bitstring Compression Estimate: X-bar = 5.1060913378184907, sigma-hat = 1.0602301402207321, p = 0.089700342434675784
Compression Test Estimate (bit string) = 0.579790 / 1 bit(s)
Running Tuple Estimates...
Bitstring t-Tuple Estimate: t = 24, p-hat_max = 0.6077535669643823323526, p_u = 0.608198213970942755998
Bitstring LRS Estimate: u = 25, v = 55, p-hat = 0.57377327555229816, p_u = 0.57422363845508301
T-Tuple Test Estimate (bit string) = 0.717387 / 1 bit(s)
Literal t-Tuple Estimate: t = 2, p-hat_max = 0.02539400000000000000072, p_u = 0.02579922608588419654918
Literal LRS Estimate: u = 3, v = 6, p-hat = 0.014678019585973216, p_u = 0.014987790126594754
T-Tuple Test Estimate = 5.276528 / 8 bit(s)
LRS Test Estimate (bit string) = 0.800315 / 1 bit(s)
LRS Test Estimate = 6.060069 / 8 bit(s)
Running Predictor Estimates...
Bitstring MultiMCW Prediction Estimate: N = 7999937, Pglobal' = 0.53749557635492473 (C = 4296298) Plocal can't affect result (r = 26)
Multi Most Common in Window (MultiMCW) Prediction Test Estimate (bit string) = 0.895675 / 1 bit(s)
Literal MultiMCW Prediction Estimate: N = 999937, Pglobal' = 0.031150330241116859 (C = 30704) Plocal can't affect result (r = 4)
Multi Most Common in Window (MultiMCW) Prediction Test Estimate = 5.004609 / 8 bit(s)
Bitstring Lag Prediction Estimate: N = 7999999, Pglobal' = 0.55941498930539801 (C = 4471702) Plocal can't affect result (r = 30)
Lag Prediction Test Estimate (bit string) = 0.838009 / 1 bit(s)
Literal Lag Prediction Estimate: N = 999999, Pglobal' = 0.024834737018808978 (C = 24437) Plocal can't affect result (r = 4)
Lag Prediction Test Estimate = 5.331497 / 8 bit(s)
Bitstring MultiMMC Prediction Estimate: N = 7999998, Pglobal' = 0.56384793754105667 (C = 4507169) Plocal can't affect result (r = 30)
Multi Markov Model with Counting (MultiMMC) Prediction Test Estimate (bit string) = 0.826622 / 1 bit(s)
Literal MultiMMC Prediction Estimate: N = 999998, Pglobal' = 0.026034084289744124 (C = 25627) Plocal can't affect result (r = 4)
Multi Markov Model with Counting (MultiMMC) Prediction Test Estimate = 5.263455 / 8 bit(s)
Bitstring LZ78Y Prediction Estimate: N = 7999983, Pglobal' = 0.55942260687547074 (C = 4471754) Plocal can't affect result (r = 30)
LZ78Y Prediction Test Estimate (bit string) = 0.837990 / 1 bit(s)
Literal LZ78Y Prediction Estimate: N = 999983, Pglobal' = 0.026039513473967817 (C = 25632) Plocal can't affect result (r = 4)
LZ78Y Prediction Test Estimate = 5.263154 / 8 bit(s)
H_original: 5.004609
H_bitstring: 0.559227
min(H_original, 8 X H_bitstring): 4.473812
---
>
> More details on tuning the Jitter RNG is given in [2] - it discusses to the
> user space variant, but applies to kernel as well.
>
> [1] https://github.com/smuellerDD/jitterentropy-library/tree/master/tests/raw-entropy/recording_runtime_kernelspace
>
> [2] https://github.com/smuellerDD/jitterentropy-library/tree/master/tests/raw-entropy#approach-to-solve-insufficient-entropy
>
> Ciao
> Stephan
>
Thank you again!
Francesco
