CPU Time Jitter Based Non-Physical True Random Number Generator

Stephan Müller <smueller@chronox.de>

1 Introduction

• Hardware events do not occur fast enough to satisfy the ever grown needs of high-quality random numbers. Today’s implementation of such hardware event based random number generators provide a hybrid formed by the joining of the hardware event collection which is post-processed by a deterministic whitening function. In case of insufficient entropy, the whitening function ensures that the continuously generated output still behaves random even when new entropy is lacking.
• Virtualized environments remove an operating system from direct hardware access. The properties of the observed hardware events in a virtualized environment do not match with the properties required by the non-physical true random number generators. The implication on the entropy collected by these random number generators is not well researched, but it is safe to assume that the entropy is overestimated by the standard operating system’s random number generators.
• Depending on the usage environment of the operating system, entire classes of hardware devices may be missing and can therefore not be used as entropy source. For example, a server system located in a server lab typically does not have any human interface devices attached.
• A number of the operating system’s non-physical true random number generators use block devices, such as hard disks as entropy source. The heart of the entropy lies in the timing variances when accessing such disks which depend on the spin angle of the disk or the location of the read heads at the time of the access request. The more and more often used Solid State Disks (SSDs) advertise themselves as block devices to the operating system but yet lack the physical phenomenon that is expected to deliver entropy. The implication is that the SSD block devices cannot be used as entropy source either, although they are partially still treated as entropy source by the standard operating system’s random number generators.
• On Linux, the majority of the entropy for the input_pool behind /dev/random is gathered from the random_get_entropy time stamp. However, that time stamp function returns 0 hard coded on several architectures, such as MIPS. Thus, there is not much entropy that is present in the entropy pool behind /dev/random or /dev/urandom.
• Current cache-based attacks allow unprivileged applications to observe the operation of other processes, privileged code as well as the kernel. Thus, it is desirable to have fast moving keys. This applies also to the seed keys used for deterministic random number generators.

1. The random number generator shall only operate on demand. Other random number generators constantly operate in its lifetime, regardless whether the operation is needed or not, binding computing resources.
2. The random number generator shall always return random numbers with a speed that satisfies today’s requirement for random numbers. The random number generator shall be able to be used synchronously with the random number consuming application, such as the seeding of a deterministic random number generator.
3. The random number generator shall not block the request for user noticeable time spans.
4. The random number generator shall deliver high-quality random numbers when used in virtualized environments.
5. The random number generator shall not require a seeding with data from previous instances of the random number generator.
6. The random number generator shall work equally well in kernel space and user space.
7. The random number generator implementation shall be small, and easily understood.
8. The random number generator shall provide a decentralized source of entropy. Every user that needs random numbers executes its own instance of the CPU Jitter random number generator. Any denial of service attacks or other attacks against a central entropy source with the goal to decrease the level of entropy maintained by the central entropy source is eliminated. The goal is that there is no need of a central /dev/random or /dev/urandom device.
9. The random number generator shall provide perfect forward and backward secrecy, even when the internal state becomes known.

• Discussion of the noise source in chapter 2↓
• Presentation of CPU Jitter random number generator design in chapter 3↓
• Discussion of the statistical properties of the random number generator output in chapter 4↓
• Assessment of the entropy behavior in the random number generator in chapter 5↓

1.1 Related Work

1.2 Applicable Code Version

2 CPU Execution Time Jitter

• CPU instruction pipelines. Their fill level have an impact on the execution time of one instruction. These pipelines therefore add to the CPU execution timing jitter.
• The CPU clock cycle is different than the memory bus clock speed. Therefore, the CPU has to enter wait states for the synchronization of any memory access where the time delay added for the wait states adds to time variances.
• The CPU frequency scaling which alters the processing speed of instructions.
• The CPU power management which may disable CPU features that have an impact on the execution speed of sets of instructions.
• Instruction and data caches with their varying information – tests showed that before the caches are filled with the test code and the CPU Jitter random number generator code, the time deltas are bigger by a factor of two to three;
• CPU topology and caches used jointly by multiple CPUs;
• Different types of memory (L1, L2, L3 caches, main memory) are operated with different frequencies which require the introduction of wait states to synchronize the CPU accessing these memory components.

• CPU frequency scaling depending on the work load;
• Branch prediction units;
• TLB caches;
• Moving of the execution of processes from one CPU to another by the scheduler;
• Hardware interrupts that are required to be handled by the operating system immediately after the delivery by the CPU regardless what the operating system was doing in the mean time;
• Large memory segments whose access times may vary due to the physical distance from the CPU.

2.1 Assumptions

• Attacker having hardware level privileges or attacker controlling the execution environment [A]  [A] Virtual Machine Monitors, Simulators, Emulators, Hypervisors, etc. of the operating system are assumed to be not present. With hardware level privilege, on some CPU it may be possible to change the state of the CPU such as that caches are disabled. In addition, millicode may be changed such that operations of the CPU are altered such that operations are not executed any more. The assumption is considered to be unproblematic, because if an attacker has hardware level privilege, the collection of entropy is the least of our worries as the attacker may simply bypass the entropy collection and furnish a preset key to the random numbers-seeking application.
• Attacker with physical access to the CPU interior is assumed to be not present. In some CPUs, physical access may allow enabling debug states or the readout of the entire CPU state at one particular time. With the CPU state, it may be possible to deduct upcoming variations when the CPU Jitter random number generator is executed immediately after taking a CPU state snapshot. An attacker with this capability, however, is also able to read out the entire memory. Therefore, when launching the attack shortly after the entropy is collected, the attacker could read out the key or seed material, bypassing the entropy collection. Again, with such an attacker, the entropy collection is the least of our worries in this case.

2.2 Jitter Depicted

static inline void jent_get_nstime(uint64_t *out)
{
...
        if (clock_gettime(CLOCK_REALTIME, &time) == 0)
...
}
​
void main(void)
{
...
        for(i = 0; (SAMPLE_COUNT + CACHE_KILL) >i ; i++)
        {
...
                jent_get_nstime(&time);
                jent_get_nstime(&time2);
                delta = time2 - time;
...

Figure 1 Distribution of time variances in user space over 1.000.000 loops

• The bar diagram shows the relative frequency of the different delta values measured by the code. For example, the delta value of 22 (nanoseconds – note the used timer returns data with nanosecond precision) was measured at 25% of all deltas. The value 23 (nanoseconds) was measured at about 25% of all time deltas.
• The red and blue vertical lines indicate the mean and median values. The mean and median is printed in the legend below the diagram. Note, they may overlap each other if they are too close. Use the legend beneath the diagram as a guidance in this case.
• The two green vertical lines indicate the first and third quartile of the distribution. Again, the values of the quartiles are listed in the legend.
• The red dotted line indicates a normal distribution defined by the measured mean and the measured standard derivation. The value of the standard derivation is given again in the legend.
• Finally, the legend contains the value for the Shannon Entropy that the measured test sample contains. The Shannon Entropy is calculated with the formula specified in section 5.1↓ using the observations after cutting off the outliers above the threshold mentioned above.

static int jent_timer(char *data, size_t len)
{
        __u64 time, time2;
        time = time2 = 0;
...
        time = random_get_entropy();
        time2 = random_get_entropy();
        snprintf(data, len, "%lld\n", (time2 - time));
...

Figure 2 Distribution of time variances in kernel space over 10.000.000 loops

• The timer delta value has obvious holes in its distribution. The reason for that is the following observation: the processor cycle counter does not increment in steps of one, but in steps of three [C]  [C] It is important to note that this was observed on an Intel Core i7-2620 processor. Other processors and especially other architectures may show a different pattern in the incrementation..
• However, the user space time stamp delta is much more narrowly distributed around the mean of the distribution. The kernel time stamp deltas have a much wider range. Therefore, the Shannon Entropy value of the kernel space distribution is larger than the one from the user space distribution.

Figure 3 Distribution of time variances in user space over 1.000.000 loops at 800 MHz

1. The random number generator design must be capable of preserving and collecting the entropy from the discussed phenomenon. Thus, the random number generator must be able to ‘‘compress’’ the entropy phenomenon.
2. The random number generator must use the observed CPU execution time jitter to generate an output bit string that delivers the random numbers to a caller. That output string must not show any statistical anomalies that allow an observer to deduce any random numbers or increase the probability when guessing random numbers and thus reducing its entropy.

3 Random Number Generator Design

3.1 Maintenance of Entropy

Figure 4 Entropy Collection Operation

1. invokes memory accesses to induce timing variations,
2. fetches a time stamp to calculate a delta to the time stamp of the previous loop iteration,
3. inject the time delta value into the entropy pool by hashing the content of the entropy pool with the new value to form a new state of the entropy pool, and
4. verifies that basic properties of the time stamp are met by applying a health test.

3.1.1 Noise Source: Memory Access

• Size of a memory block,
• State of a pseudo random number generator which defines the next memory location in the memory block..

3.1.2 Obtaining Time Delta

1. Reading a time stamp,
2. Subtracting that time stamp from the time stamp calculated in the previous loop iteration,
3. Storing the current time stamp for use in the next loop iteration to calculate the next delta.

3.1.3 Noise Source: Inject Time Delta Into Entropy Pool Using SHA-3

3.2 Generation of Random Number Bit Stream

1. Check whether the requested size is smaller than 256 bits. If yes, generate one 256 bit random number, copy the requested amount of bits to the target memory and stop processing the request. The unused bits of the random number are not used further. If a new request arrives, a fresh 256 bit random number is generated.
2. If the requested size is larger than 256 bits, generate one random number, copy it to the target. Reduce the requested size by 256 bits and decide now whether the remaining requested bits are larger or smaller than 256 bits and based on the determination, follow either step 1 or step 2.

3.3 Jitter RNG Data Processing

1. Hashing: One 64-bit time delta data value t_n received from measuring the execution time of the SHA-3 and memory access operations is hashed together with the previous state of the entropy pool EP_n − 1 to generate new entropy pool output of EP_n. The implementation is provided with function jent_hash_time:
   (1) EP_n = SHA(EP_n − 1||t_n||n)
2. Entropy Collection Loop: 256 (multiplied by the oversampling rate – which is considered to be 1 in this example) time delta values t_{n − 255} through t_n are obtained and processed with the hashing operation outlined in equation 1↑ as implemented in jent_random_data. After processing the last time delta, the entropy pool EP_kblock is considered to be the output block of the CPU Jitter RNG.
   (2) EP_kblock = EP_n{n = 0..(256⋅osr − 1)}
   This formula implies that when 256 times the oversampling rate time deltas are to be mixed into the entropy pool.
   This implies that for obtaining one output block of the Jitter RNG, the entropy pool is iteratively hashed with the time deltas up to a maximum of 256⋅osr times.
3. Concatenation with truncation: To generate the requested number of random bytes, the result of equation 2↑ is concatenated with the previous completion of equation 2↑ and so on. If the requested amount of random data is not a multiple of 256 bits, the required most significant bits from the current entropy pool state is used - the implementation is provided with function jent_read_entropy:
   (3) RAND = EP_{(k − sizeof(RAND) ⁄ 256)block}|| ... ||EP_{(k − 1)block}||MSB_{sizeof(RAND) mod 256}(EP_kblock)

3.4 Runtime Health Tests

• Stuck Test
• Repetition Count Test
• Adaptive Proportion Test
• Lag Predictor Test

3.4.1 Stuck Test

3.4.2 Repetition Count Test

3.4.3 Adaptive Proportion Test

3.4.4 Lag Predictor Test

3.5 Initialization

1. Allocation and zeroization of memory used for the entropy pool and helper variables – struct rand_data defines the entropy collector which holds the entropy pool and its auxiliary values.
2. Invoking the entropy collection loop once – this fills the entropy pool with the first random value which is not returned to any caller. The idea is that the entropy pool is initialized with some values other than zero. In addition, this invocation of the entropy collection loop implies that the entropy collection loop counter value is set to a random value in the allowed range.
3. If FIPS 140-2 is enabled by the calling application, the SP800-90C compliant oversampling of the noise source for conditioning is applied by obtaining 64 more bits of entropy than extracted from the SHA3-256 operation.

3.6 Memory Protection

3.7 Locking

3.8 Programming Dependencies on Operating System

• Time stamp gathering: jent_get_nstime should deliver the high resolution time stamp. This function is an architecture dependent function with the following implementations:\begin_inset Separator latexpar\end_inset
  • User space:\begin_inset Separator latexpar\end_inset
    • On Mach systems like MacOS, the function mach_absolute_time is used for a high-resolution timer.
    • On AIX, the function read_real_time is used for a righ resolution timer.
    • On POSIX systems, the clock_gettime function is available for this operation.
  • Linux kernel space: In the Linux kernel, the random_get_entropy function obtains this information. The directory arch/ contains various assembler implementations for different CPUs to avoid using an operating system service. If random_get_entropy returns 0, which is the case on a large number of architectures the kernel-internal call __getnstimeofday is invoked which uses the best available clocksource implementation. The goal with the invocation of __getnstimeofday is to have a fallback for random_get_entropy returning zero. Note, if that clocksource clock also is a low resolution timer like the Jiffies timer, the initialization function of the CPU Jitter Random Number Generator is expected to catch this issue.
• jent_zalloc is a wrapper for the malloc function call to obtain memory.
• jent_zfree is a wrapper for calling the free function to release the memory.
• __u64 must be a variable type of a 64 bit unsigned integer – either unsigned long on a 64 bit system or unsigned long long on a 32 bit system.

• memcpy
• memset

3.8.1 Environments Without High-Resolution Time Stamps

4 Random Generator Statistical Assessment

4.1 Statistical Properties of Entropy Pool

Figure 5 Bit sum of last round of entropy collection loop user space

Figure 6 Bit sum of last round of entropy collection loop kernel space

Figure 7 Bit sum of set bits per bit position in user space

Figure 8 Bit sum of set bits per bit position in kernel space

• It is a smooth distribution showing no breaks.
• It is a symmetrical distribution whose symmetry point is the mean.

Figure 9 Bit sum of bit variations per bit position in user space

Figure 10 Bit sum of bit variations per bit position in kernel space

4.2 Statistical Properties of Random Number Bit Stream

Figure 11 Distribution of bit count per bit position of RNG output

Figure 12 Box plot of variations in bit count per bit position of RNG output

• ent
• dieharder
• BSI Test Procedure A

$ dd if=/sys/kernel/debug/jitterentropy/seed of=random.out bs=8 count=10000000
​
# Byte stream
$ ent random.out 
Entropy = 7.999998 bits per byte.
​
Optimum compression would reduce the size
of this 80000000 byte file by 0 percent.
​
Chi square distribution for 80000000 samples is 272.04, and randomly
would exceed this value 25.00 percent of the times.
​
Arithmetic mean value of data bytes is 127.4907 (127.5 = random).
Monte Carlo value for Pi is 3.141600679 (error 0.00 percent).
Serial correlation coefficient is 0.000174 (totally uncorrelated = 0.0).
​
# Bit stream
$ ent -b random.out 
Entropy = 1.000000 bits per bit.
​
Optimum compression would reduce the size
of this 640000000 bit file by 0 percent.
​
Chi square distribution for 640000000 samples is 1.48, and randomly
would exceed this value 25.00 percent of the times.
​
Arithmetic mean value of data bits is 0.5000 (0.5 = random).
Monte Carlo value for Pi is 3.141600679 (error 0.00 percent).
Serial correlation coefficient is -0.000010 (totally uncorrelated = 0.0).

• an Intel Atom Z530 processor;
• a MIPS CPU for an embedded device;
• an Intel Pentium 4 Mobile CPU;
• an AMD Semperon processor;
• KVM guest where the host was based on an Linux 3.8 kernel and with QEMU version 1.4 without any special configuration of hardware access;
• OpenVZ guest on an AMD Opteron processor.

4.3 Anti-Tests

4.3.1 Static Increment of Time Stamp

4.3.2 Pattern-based Increment of Time Stamp

static unsigned int pad = 0;
static __u64 tmp = 0;
static inline void jent_get_nstime(__u64 *out)
{
        tmp += 23;
        pad++;
        *out = (tmp + pad);

4.3.3 Disabling of System Features

5 Entropy Behavior

5.1 Base Entropy Source

5.1.1 Noise Sources Depicted

• The hash loop shall inject the time delta value into the entropy pool.
• The delta of two time stamps before and after the folding loop is given to the hash loop to be injected into the entropy pool.

Figure 13 Lower boundary of entropy over LFSR loop in user space

Figure 14 Lower boundary of entropy over LFSR loop and constant memory access in user space

Figure 15 Upper boundary of entropy over LFSR loop in user space

Figure 16 Upper boundary of entropy over LFSR loop and constant memory access in user space

Figure 17 Lower boundary of entropy over LFSR loop in kernel space

Figure 18 Upper boundary of entropy over LFSR loop in kernel space

Figure 19 FFT of minimum LFSR and memory access loop counts

Figure 20 FFT of normal operation of LFSR and memory access loop counts

Figure 21 Variations of the execution time jitter over time when performing LFSR loop jitter measurements with Frequency Scaling / Power Management

Figure 22 Variations of the execution time jitter over time when performing LFSR loop jitter measurements with Frequency Scaling / Power Management – ‘‘zoomed in at measurements 1,000 - 3,000’’

Figure 23 Variations of the execution time jitter over time when performing LFSR loop jitter measurements with Frequency Scaling / Power Management – ‘‘zoomed in at measurements 42,000 - 44,000’’

Figure 24 Variations of the execution time jitter over time when performing LFSR loop jitter measurements with Frequency Scaling / Power Management disabled

Figure 25 Variations of the execution time jitter over time when performing LFSR loop jitter measurements with Frequency Scaling / Power Management disabled – ‘‘zoomed in at measurements 1,000 - 3,000’’

Figure 26 Variations of the execution time jitter over time when performing LFSR loop jitter measurements with Frequency Scaling / Power Management disabled – ‘‘zoomed in at measurements 42,000 - 44,000’’

6 Assessment of Noise Sources

6.1 CPU Execution Timing Jitter

• Lower boundary of entropy: 3.06
• Upper boundary of entropy: 9.21

6.1.1 Serialization Instruction

• Baseline test code which eliminates all jitter by using a serialization instruction:
  

  asm volatile(
          "cpuid\n\t"
          "cpuid\n\t"
          "cpuid\n\t"
  );
  asm volatile("rdtsc" : "=A" (a));
  asm volatile("rdtsc" : "=A" (b));
  

  \begin_inset Separator latexpar\end_inset
  The delta between the variables a and b does not vary. Therefore, the CPU execution timing variations draw from on the internal state of the CPU which a serialization instruction can reset.
• Now, considering that the serialization operation eliminates the variation as seen in the preceding, an attack against the RNG can be planned. When executing the following code on each CPU, the question now arises, whether the statistical properties of the RNG output would change:
  

  void main(void)
  {
          asm volatile("cpuid");
  }
  

  \begin_inset Separator latexpar\end_inset
  While that code is now executing on all CPUs to ensure that the entropy collection code of the RNG executes on a CPU where this serialization instruction has been executed before hand, the statistical properties of the RNG output does not show any weaknesses. The Chi-Squared test result of the binary output of the RNG marks it as white noise.
• Placing the invocation of the serialization instruction into a function:
  

  void cpuid(void)
  {
          asm volatile(
                  "cpuid\n\t"
                  "cpuid\n\t"
                  "cpuid\n\t"
          );
  }
  void test(void)
  {
          cpuid();
          asm volatile("rdtsc" : "=A" (a));
          asm volatile("rdtsc" : "=A" (b));
  }
  

  \begin_inset Separator latexpar\end_inset
  With this invocation of the serialization instruction, small variations start to appear.
• When re-implementing the function call with assembler code, however, still no variations are visible:
  

  asm volatile(
          "jl 1f\n"
          "sub:\t"
          "cpuid\n\t"
          "ret\n\t"
          "1:"
          "call sub\n\t"
  );
  asm volatile("rdtsc" : "=A" (a));
  asm volatile("rdtsc" : "=A" (b));
  

  \begin_inset Separator latexpar\end_inset
  Thus, it is not clear what the difference between this code and the preceding code is.
• Even when enlarging the memory space between the CPUID instruction and the time stamp gathering, still no variations are visible:
  

  asm volatile(
          "jl 1f\n"
          "sub:\t"
          "cpuid\n\t"
          "ret\n\t"
          "1:"
          "nop\n\t" //This instruction now 500 times
          "call sub\n\t"
  );
  asm volatile("rdtsc" : "=A" (a));
  asm volatile("rdtsc" : "=A" (b));
  

  \begin_inset Separator latexpar\end_inset
  Thus, no proximity of the serialization instruction to the timing has no impact to the absence of variations.
• Placing the serialization instruction inbetween the time reading instructions:
  

  asm volatile(
          "cpuid\n\t"
          "cpuid\n\t"
          "cpuid\n\t"
  );
  asm volatile("rdtsc" : "=A" (a));
  asm volatile("cpuid");
  asm volatile("rdtsc" : "=A" (b));
  

  \begin_inset Separator latexpar\end_inset
  This code now shows significant variations of the execution time. This means that the flushing of the CPU state with the serialization instruction varies significantly with no apparent reason.
• When using other serialization instructions, like WBINVD, or INVD, the same results as with CPUID are visible. That means that all serialization instructions have an equal effect on the execution timing jitter. Therefore, invoking a serialization instruction causes the CPU state that is the basis of the jitter to reset.
• When replacing the serialization function with a memory barrier using the MFENCE instruction, the execution variations did not decrease compared to simply reading the timing values without any special treatment. Therefore, the memory barrier has no effect on the CPU execution timing variations.

6.1.2 Prevention of System Call And Branch Prediction Interference

int i = 0;
for(i=0; i<1000; i++)
        duration = jent_fold_var_stat(NULL, 0);
for(i=0; i<1000; i++)
        duration_min = jent_fold_var_stat(NULL, 1);
printf("%llu %llu\n", duration, duration_min);

• Lower boundary of entropy: 3.86
• Upper boundary of entropy: 9.48

6.1.3 Flush of CPU Instruction Pipeline

#define mb() asm volatile("mfence":::"memory")
mb();
duration = jent_fold_var_stat(NULL, 0);
mb();
duration_min = jent_fold_var_stat(NULL, 1);
mb();

• Lower boundary of entropy: 3.66
• Upper boundary of entropy: 9.33

6.1.4 Flush of CPU Caches

#define wbinvd() asm volatile("wbinvd": : :"memory");
wbinvd();
duration = jent_fold_var_stat(NULL, 0);
wbinvd();
duration_min = jent_fold_var_stat(NULL, 1);
wbinvd();

• Lower boundary of entropy: 6.43
• Upper boundary of entropy: 10.58

6.1.5 Disabling of Preemption

preempt_disable();
duration = jent_fold_var_stat(NULL, 0);
duration_min = jent_fold_var_stat(NULL, 1);
preempt_enable();

• Lower boundary of entropy: 3.46
• Upper boundary of entropy: 8.68

6.1.6 TLB Flush

native_write_cr3(native_read_cr3());
duration = jent_fold_var_stat(NULL, 0);
duration_min = jent_fold_var_stat(1);

• Lower boundary of entropy: 3.22
• Upper boundary of entropy: 8.52

6.1.7 Pinning of Entropy Collection to one CPU

mkdir /sys/fs/cgroup/cpuset/foldtime
/bin/echo 2 > cpuset.cpus
/bin/echo 0 > cpuset.mems
/bin/echo <PID_of_proc> > tasks
/bin/echo 1 > cpuset.mem_hardwall

• Lower boundary of entropy: 3.32
• Upper boundary of entropy: 9.12

6.1.8 Disabling of Frequency Scaling and Power Management

• Lower boundary of entropy: 2.59
• Upper boundary of entropy: 9.25

6.1.9 Disabling of L1 and L2 Caches

__asm__("push   %rax\n\t"
        "mov    %cr0,%rax;\n\t"
        "or     $(1 << 30),%rax;\n\t"
        "mov    %rax,%cr0;\n\t"
        "wbinvd\n\t"
        "pop    %rax"
       );

echo "disable=00" >| /proc/mtrr

• Lower boundary of entropy: 8.48
• Upper boundary of entropy: 11.53

6.1.10 Disabling of L1 and L2 Caches And Interrupts

local_irq_save(flags);
local_irq_disable();
duration = jent_fold_var_stat(NULL, 0);
duration_min = jent_fold_var_stat(NULL, 1);
local_irq_restore(flags);
local_irq_enable();

• Lower boundary of entropy: 8.37
• Upper boundary of entropy: 12.11

6.1.11 Disabling of All CPU Mechanisms

local_irq_save(flags);
local_irq_disable();
wbinvd();
mb();
for(i=0; i<1000; i++)
        duration = jent_fold_var_stat(0);
wbinvd();
mb();
for(i=0; i<1000; i++)
        duration_min = jent_fold_var_stat(1);
wbinvd();
mb();
local_irq_restore(flags);
local_irq_enable();

$ ent /tmp/out && ent -b /tmp/out 
Entropy = 7.999936 bits per byte.
​
Optimum compression would reduce the size
of this 2911816 byte file by 0 percent.
​
Chi square distribution for 2911816 samples is 257.43, and randomly
would exceed this value 44.55 percent of the times.
​
Arithmetic mean value of data bytes is 127.5091 (127.5 = random).
Monte Carlo value for Pi is 3.146313017 (error 0.15 percent).
Serial correlation coefficient is -0.000537 (totally uncorrelated = 0.0).
Entropy = 1.000000 bits per bit.
​
Optimum compression would reduce the size
of this 23314880 bit file by 0 percent.
​
Chi square distribution for 23314880 samples is 0.06, and randomly
would exceed this value 81.14 percent of the times.
​
Arithmetic mean value of data bits is 0.5000 (0.5 = random).
Monte Carlo value for Pi is 3.146391175 (error 0.15 percent).
Serial correlation coefficient is -0.000004 (totally uncorrelated = 0.0).

6.2 Memory Access Testing

• Size of memory blocks: The description of the memory access noise source explains that the memory used for measuring access times is segmented into memory blocks. With the configuration of the size of memory blocks the access pattern to the memory is altered.
• Number of memory blocks: In addition to the size of one memory block, the number of used memory blocks defines the size of the entire memory used for access. The modification of the size of the entire memory influences the number of memory addresses the CPU sees.
• Number of loop iterations to access memory: The design of the memory access noise source implies that various bytes out of the allotted memory are accessed. Each loop iteration reads and writes one byte.

6.2.1 Noise Source Discussion

6.2.2 Noise Source Measurements

• The maximum and minimum observed values depicted with the blue lines.
• The mean of the observed values depicted with the red line. As expected, the red line will always be within the two blue lines.

Figure 27 Average time duration for memory accesses

Figure 28 Standard deviation of time duration for memory accesses

Figure 29 Variation coefficient of time duration for memory accesses

Figure 30 Number of different of time durations for memory accesses

Figure 31 Shannon Entropy of time durations for memory accesses

Figure 32 Impact of Selectively Disabling of CPU Mechanisms on Memory Access Timing Variations

• Using a serialization instruction like CPUID which removed all timing variations for the CPU execution time jitter does not have any impact on the measurements for memory access timing.
• Flushing the branch prediction unit of the CPU does not have a measurable impact on the memory access timing variations.
• Flushing the instruction pipeline or the TLB cache does not show any impact on the memory access timing variations.
• Disabling L1 and L2 caches showed a significant impact by dramatically increasing the memory access timing variations. This is expected, because the CPU now always has to access the main memory. As the accesses to main memory are subject to more wait states than L2 accesses, the variations must increase.

6.2.3 Memory Accesses and LFSR Loop

Figure 33 LFSR loop without memory accesses on Intel Xeon E5504 – lower boundary

Figure 34 LFSR loop with memory accesses on Intel Xeon E5504 – lower boundary

Figure 35 LFSR loop without memory accesses on Intel Xeon E5504 – upper boundary

Figure 36 LFSR loop with memory accesses on Intel Xeon E5504 – upper boundary

6.3 Noise Source Testing Without Operating System

• Enabling / Disabling of the L1/L2 cache during the measurements. To ensure a responsive test framework, the caches are always enabled when not executing tests. The caches are disabled as outlined in section 6.1.9↑.
• Enabling / Disabling L1/L2 Cache Flush: Before the execution of a test, the L1/L2 cache can be flushed as discussed in section 6.1.4↑.
• Enabling / Disabling of Pipeline Flush: The CPU instruction pipeline can be flushed before the execution of each test as outlined in section 6.1.3↑.
• Enabling / Disabling of TLB Flush: The TLB can be flushed before the execution of each test as outlined in section 6.1.6↑.
• Enabling / Disabling of serialization: Before the execution of each test, a serialization instruction is invoked. The code uses the CPUID instruction invoked with zero as input parameters in EAX and EDX.
• Enabling / Disabling of Mem Jitter: This flag toggles whether the memory access operation shall be invoked when testing the operation of the entropy collection loop. By disabling this flag, the testing would only measure the LFSR loop operation. This flag is only relevant for test 2.
• Enabling / Disabling of Morse Results: When the automated testing is selected, the displayed test results of the statistical data calculated after completing testing can be transferred to another computer using the Morse code. As the test framework has no drivers, the only way to extract data is by Morse code. The individual values are separated by commas and the line separator is a dash. The WPM of the Morse communication is about 21. The following command can be used for capturing data:

  demorse -f 21 -phw:0 -rCapture  -lCapture -uleft -d8
  

• Branch Pred Fl Lp: The number of branch prediction flush loops defines the number of loops discussed in section 6.1.2↑.
• Memory Access Loops: The number of memory access loops can be set here.
• Test Loops: The number of test executions before displaying the histogram and various statistical data of measurements can be set here. Per default, the value is set to 10,000. This value only applies to test 4.
• Number of Mem Blks: The number of memory blocks defining the size of the memory to be accessed is set here.
• Jitter LFSR Iter: The number of loop iterations of the LFSR loop is defined with this value. If set to zero, the automated selection of the number of loop iterations as found in normal operation of the RNG is done. This value applies to test 2 only.
• Memory Block Size: The size of one memory block in bytes is defined with this configuration option.

Figure 37 Execution of Bare-Metal CPU Execution Jitter Test on KVM

• In the upper right corner, the currently executed test is referenced.
• In the row in the middle of the screen lists the selected options. All options can be set by hitting the character c during operation.
• In the lower part, parts of the recorded histogram of timing data is shown. A group of two numbers delimited by a colon shall be interpreted together. The left hand side of the colon is the time duration for one LFSR loop operation. The right hand side is the number of occurrences that were counted for the test. The groups of value pairs can be considered to form a histogram. For example, the following results are observable from the screenshot above: The LFSR loop execution duration of 2312 cycles is observed 1 time. The LFSR loop execution duration of 1552 cycles is observed 12 times. The LFSR loop execution duration of 1524 cycles is observed 26 times, And so on. Note, only a subset of all recorded histogram slots is depicted due to space constraints.
• Below the histogram, different statistical values are shown with a divisor used as a scaling factor in the following. To keep the test framework minimal, only integer calculation is possible. To limit the calculation error due to truncation performed with divisions, the formulas partially increase the dividend to obtain values which are greater than 1. The reader now must manually divide the shown number by the displayed divisor. For each statistical value, the minimum observed value, the maximum observed value and the mean value during the test cycle is listed. The following statistical values are shown:\begin_inset Separator latexpar\end_inset
  • Shannon Entropy: The calculation of the Shannon Entropy is calculated with the formula
    H = ^{i ≤ 200}⎲⎳_i = 1p_i⋅log₂p_i = ^{i ≤ 200}⎲⎳_i = 1(s_i)/(l)⋅log₂(s_i)/(l) = ^{i ≤ 200}⎲⎳_i = 1(s_i)/(l)⋅(log₂s_i − log₂l)
    where s_i specifies the number of observations in the histogram for one timing value and l specifies the number of test loops performed. The scaling factor f is added by modifying the formula above as follows
    H⋅f = ^{i ≤ 200}⎲⎳_i = 1(s_i⋅f)/(l)⋅(log₂(s_i⋅f) − log₂(l⋅f))
    Warning: Due to the integer calculation for the logarithm, the result of the formula overestimates the Shannon Entropy by up to one bit. Therefore, that value shall not be used as a blank statement of the entropy contained, but rather as a reference to the variations found in the time deltas of the test sample. Nonetheless, the Shannon Entropy is not lower than the calculated value minus one (bit). When comparing this value with Shannon Entropy measurements from other tests, always consider the Sigma and the Variation Coefficient in addition.
  • Delta Mean: This value simply calculates the mean of the histogram for one test execution:
    x = (s_i⋅v_i)/(l)
    where s_i specifies the number of observations in the histogram for one timing value, v_i specifies the timing value in the histogram, and l specifies the number of test loops performed.
  • Sigma: The standard derivation is calculated by first calculating the variance followed by calculating the square root of the variance. The following formula is used:
    σ = √(^{i ≤ 200}⎲⎳_i = 1(v_i − x)⋅(v_i − x)⋅s_i)
    where the variables have the same meaning as outlined above.
  • The variation coefficient is a scaling of the standard derivation to the mean of the data set. The following formula shows the calculation of the variation coefficient V
    V = (σ)/(x)
    As the variation coefficient can be smaller than 1, it is scaled with the factor f
    V⋅f = (σ⋅f)/(x)
  • The number of switches specifies how often a different time delta compared to the immediately previously seen time delta value is recorded. For example, consider the following series of time delta measurements: 100, 100, 101, 102, 102, 100. The number of switches here is 3.
  • The value for used slots simply lists how many of the 200 available slots in the histogram are actually filled. That means, how many different time delta values are recorded.

7 Standards Compliance

7.1 FIPS 140-2 Compliance

7.1.1 FIPS 140-2 IG 7.18 Requirement For Statistical Testing

• Raw Entropy Tests: The tests obtain the raw unconditioned and unprocessed noise information and records it for analysis with the SP800-90B non-IID statistical test tool. The test tool includes the gathering of raw entropy for one execution run as well as for the restart tests required in SP800-90B section 3.1.4. The tool adjusts the data to be processed by the SP800-90B statistical test tool. The test tool provides the SP800-90B minimum entropy values for the lower and upper boundaries documented in section 5↑. The testing was successfully conducted on Intel x86-based systems, ARM-based systems including smart phones, embedded devices with MIPS and ARM CPU, IBM POWER, IBM System-Z Mainframes.
• Jitter RNG Output Tests: The Jitter RNG output is captured and processed with the SP800-90B IID statistical tests.
• Health Test Assessments: The Adaptive Proportion Test and Repetition Count Tests are validated independently from the noise source to validate the false-rejection rate as well as false acceptance rate. The test tool invokes these tests while the Jitter RNG is operational. The test verifies whether the online health tests trigger alarms.

7.1.2 FIPS 140-2 IG 7.18 Heuristic Analysis

7.1.3 FIPS 140-2 IG 7.18 Additional Comment 1

7.1.4 FIPS 140-2 IG 7.18 Additional Comment 2

7.1.5 FIPS 140-2 IG 7.18 Additional Comment 3

7.1.6 FIPS 140-2 IG 7.18 Additional Comment 4

7.1.7 FIPS 140-2 IG 7.18 Additional Comment 6

7.1.8 FIPS 140-2 IG 7.18 Additional Comment 9

7.2 SP800-90B Compliance

7.2.1 SP800-90B Section 3.1.1

7.2.2 SP800-90B Section 3.1.2

7.2.3 SP800-90B Section 3.1.3

1. Gathering of the raw entropy data of the time stamps for both, the lower and upper boundary.
2. Obtaining the four least significant bits of each time delta and concatenate them to form a bit stream. Two bit streams are gathered, one for the upper and one for the lower boundary.
3. The bit stream is processed with the SP800-90B entropy testing tool to gather the minimum entropy. Two minimum entropy values are obtained, one for the lower and one for the upper boundary.

• Using the 4 least significant bits of the upper boundary time deltas: 3.55952
• Using the 4 least significant bits of the lower boundary time deltas: 2.784276

7.2.4 SP800-90B Section 3.1.4

1. Gathering of the raw restart entropy data of the time deltas for both, the lower and upper boundary.
2. Obtaining the four least significant bits of each time delta either row-wise or column-wise and concatenate them to form a bit stream. There are 1,000 bit streams row-wise upper boundary, 1,000 bit streams row-wise lower boundary, 1,000 bit streams column-wise upper boundary and 1,000 bit streams column-wise lower boundary generated.
3. The bit streams are processed with the SP800-90B entropy testing tool to gather the minimum entropy.

• Using the 4 least significant bits of the upper boundary time deltas in column-wise assessment – lowest entropy value of all 1,000 column entries: 2.074924
• Using the 4 least significant bits of the lower boundary time deltas in column-wise assessment – lowest entropy value of all 1,000 column entries: 2.145488
• Using the 4 least significant bits of the upper boundary time deltas in row-wise assessment – lowest entropy value of all 1,000 column entries: 2.196152
• Using the 4 least significant bits of the lower boundary time deltas in row-wise assessment – lowest entropy value of all 1,000 column entries: 2.029292
• Sanity check of upper boundary 1,000 x 1,000 matrix passes with value of one
• Sanity check of lower boundary 1,000 x 1,000 matrix passes with value of one

7.2.5 SP800-90B Section 3.1.5

• Equation 1↑:
  • n_in equals to 384 bits by hashing the previous state of the entropy pool, the 64 bit value of the time delta and the 64 bit loop count value.
  • n_out is the message digest size of 256 bits.
  • nw is the message digest size in bits.
• Function 2↑ repeats the operation 1↑ 256 times with a new time delta. Thus does not alter input data sizes.
• Function 3↑ repeats the operation 3↑ as often as needed to produce the requested numbers of bits. Thus does not alter input data sizes.

7.2.6 SP800-90B Section 3.1.5.2

• The entropy content of the input h_in: The input entropy of the hash is equal to the entropy provided by the processed time delta and the entropy already present in the entropy pool considering that both data components are hashed at the same time to form a new entropy pool state. Of course, the entropy held in the entropy pool will never be larger than the digest size of the used hash which is compliant to [1] section 3.1.5.1.1 table 1.

• h_{outSHA3 − 256} = nw_{SHA3 − 256} = n_{outSHA3 − 256} = 256.

7.2.7 SP800-90B Section 3.1.6

7.2.8 SP800-90B Section 3.2.1 Requirement 1

7.2.9 SP800-90B Section 3.2.1 Requirement 2

7.2.10 SP800-90B Section 3.2.1 Requirement 3

7.2.11 SP800-90B Section 3.2.1 Requirement 4

7.2.12 SP800-90B Section 3.2.1 Requirement 5

1. Generate a time stamp.
2. Invoke the memory access operation
3. Invoke the hash operation
4. Generate a time stamp
5. Calculate the time delta using the two time stamps

7.2.13 SP800-90B Section 3.2.1 Requirement 6

7.2.14 SP800-90B Section 3.2.1 Requirement 7

7.2.15 SP800-90B Section 3.2.2 Requirement 1

7.2.16 SP800-90B Section 3.2.2 Requirement 2

7.2.17 SP800-90B Section 3.2.2 Requirement 3

7.2.18 SP800-90B Section 3.2.2 Requirement 4

7.2.19 SP800-90B Section 3.2.2 Requirement 5

7.2.20 SP800-90B Section 3.2.2 Requirement 6

7.2.21 SP800-90B Section 3.2.2 Requirement 7

7.2.22 SP800-90B Section 3.2.3 Requirement 1

7.2.23 SP800-90B Section 3.2.3 Requirement 2

7.2.24 SP800-90B Section 3.2.3 Requirement 3

7.2.25 SP800-90B Section 3.2.3 Requirement 4

7.2.26 SP800-90B Section 3.2.3 Requirement 5

7.2.27 SP800-90B Section 3.2.4 Requirement 1

7.2.28 SP800-90B Section 3.2.4 Requirement 2

7.2.29 SP800-90B Section 3.2.4 Requirement 3

7.2.30 SP800-90B Section 3.2.4 Requirement 4

7.2.31 SP800-90B Section 3.2.4 Requirement 5

7.2.32 SP800-90B Section 3.2.4 Requirement 6

7.2.33 SP800-90B Section 3.2.4 Requirement 7

7.2.34 SP800-90B Section 4.3 Requirement 1

7.2.35 SP800-90B Section 4.3 Requirement 2

7.2.36 SP800-90B Section 4.3 Requirement 3

• RCT: The false positive rate is α = 2^− 30 and therefore complies with the recommended false positive probability.
• APT: The cut-off value is set to 325 compliant to SP800-90B section 4.4.2 for non-binary data at a significance level of α = 2^− 30 with time stamp is assumed to at least provide one bit of entropy, i.e. H = 1 [J]  [J] Note, the referenced Excel function seems to be imprecise when calculating the value. The data has been obtained using R-Project with the formula of 1 + qbinom(1 − 2^− 30, 512, 2^− 1)..

7.2.37 SP800-90B Section 4.3 Requirement 4

7.2.38 SP800-90B Section 4.3 Requirement 5

7.2.39 SP800-90B Section 4.3 Requirement 6

7.2.40 SP800-90B Section 4.3 Requirement 7

• During startup, the RCT and the APT are applied to 1,024 samples. The startup test can be triggered again when the caller allocates a new Jitter RNG handle.
• At runtime, the RCT is applied to each received time delta. The APT collects the data from 512 samples. The APT health test is calculated once all time deltas are recorded. The passing results of both tests shall be confirmed before the generated Jitter RNG block is returned to the caller.

7.2.41 SP800-90B Section 4.3 Requirement 8

7.2.42 SP800-90B Section 4.3 Requirement 9

7.2.43 SP800-90B Sections 4.4 and 4.5

• When the RCT passes, the counter is set to zero for the next time delta to arrive. In mathematical terms, the verification of back-to-back values being not identical is the calculation of the first discrete derivative of the time deltas (or second discrete derivative of time stamps) to show that it is not zero. In addition, the Jitter RNG enhances the RCT by calculating also the first and third discrete derivative of the time stamp to be injected into the entropy pool by the SHA-3. With that, up to 8 consecutive time stamp values are assessed. All derivatives must always be non-zero in order to pass the RCT. If one discrete derivative shows a zero, the RCT counter is increased. Thus, the addition of the first and third derivative of the time stamp makes the RCT even more conservative. Hence, the first discrete derivative is considered to be identical to the ‘‘approved’’ RCT specified in SP800-90B section 4.4. In addition, linear and exponential patterns are identified with the first and third discrete derivative, respectively. As the additional pattern recognition do not invalidate the mandatory pattern recognition, this RCT approach therefore is considered to be an enhanced version of the ‘‘approved’’ RCT and thus meets the requirement (a) of SP800-90B section 4.5.

7.3 NIST Clarification Requests

7.3.1 Sensitivity of Jitter Measurements

7.3.2 Dependency Between Jitter Measurements

7.4 Reuse of SP800-90B Analysis

1. Obtain raw noise data when executing the Jitter RNG on the intended target platform as explained in section 7.2.3↑. The obtained raw noise data must be processed by the SP800-90B tool to obtain an entropy rate which must be above 0.3331 bit of entropy per time delta.
2. Obtain the restart noise data when executing the Jitter RNG on the intended target platform as explained in section 7.2.4↑. The obtained raw noise data must be processed by the SP800-90B tool to verify:
   1. the sanity test to apply to the noise restart data must pass, and
   2. the minimum of the row-wise and column-wise entropy rate must not be less than half of the entropy rate from measurement (1) and the entropy assessment of the noise source based on the restart data must be at least 0.3331 bit of entropy per time delta.

7.5 SP800-90C Considerations

8 Conclusion

1. On demand operation is ensured by the fact that the entropy collection loop is triggered when the caller requests data. Multiple loops are initiated sequentially if the requested bit string is larger than 256 bits.
2. When compiled as a user space application, the CPU Jitter random number generator returns roughly 10 kBytes per second on an Intel Core i7 2nd generation with 2.7 GHz. In kernel space, the speed is roughly the same on the same test system. An Intel Atom Z530 system with 1.6 GHz produces output at about 2kBytes per second.
3. The design description explains that the CPU Jitter random number generator always returns entropy. The entropy is generated when the request for it is received.
4. In virtualized environments, the fundamental property of CPU execution time jitter is still present. Moreover, reading high-resolution timing information from the CPU is typically allowed by the virtualization environment and is not subject to virtualization itself [K]  [K] Although the discussion of virtualizing the CPU time stamp – e.g. the RDTSC x86 processor instruction – is conducted once in a while, no attempts to implement such virtualization has been made. The goal of such virtualization would only be to hide the existence of a hypervisor to a guest. But current virtualization environments do not pursue that goal.. Thus, a virtual environment can execute the CPU Jitter random number generator and deliver equal entropy. Due to the additional processing that typically is present to support reading the CPU time stamp, the CPU execution time jitter is expected to be higher and thus supportive to the CPU Jitter random number generator.
5. The design description explains that the CPU Jitter random number generator always generates fresh entropy.
6. The reference implementation work in both kernel and user space.
7. The CPU Jitter random number generator requires access to either a hardware high resolution timer or the POSIX threading support to implement a software-based timer. In Linux, that is granted to unprivileged processes. Therefore, every process that is in need of entropy can instantiate its own copy of the CPU Jitter random number generator.
8. The CPU Jitter random number generator generates a fresh 256 bit random number for each request. Even though it reuses the contents of the entropy pool that was used for previous random numbers, it makes no assumption whether entropy is present or not. Moreover, the data fed into the entropy pool is not deterministic. Thus, perfect forward and backward secrecy is considered to be maintained. The question is: How do we interpret the case when an observer gets access to the entropy pool when the first few iterations of one entropy collection loop operation are performed. Let us assume that an observer accesses the entropy pool after the first iteration of the loop completes. That iteration added some but very little entropy. The observer can ‘‘brute-force’’ the previous random number [L]  [L] The same applies for the new random number when the observer would access the entropy pool in the last few iterations before completion of entropy collection loop. by guessing the few added numbers. Therefore, how do we interpret forward and backward secrecy here? The definition we apply is the following: Perfect forward and backward secrecy is ensured when an observer gains access to one random number generated by the CPU Jitter random number generator. When an observer gains access to the entropy pool while a random number is generated, the perfect forward and backward secrecy applies to all random numbers before the last generated random number and after the currently generated random number, excluding the last and currently generated random number. To make sure that the last generated random number is not lingering in memory for too long, the code invokes the entropy collection loop one more time after completing the calling application’s request which changes the entropy pool such that in an event an observer can get access to the entropy pool, he gains nothing – this code is executed if the environment where the CPU Jitter random number generator is embedded into does not implement a secure memory handling.

8.1 Threat Scenario

• Direct readout of random number or the internal state of the CPU Jitter random number generator: This approach can be immediately refuted as the random number generator relies on the process separation and memory isolation offered by contemporary operating systems.
• Interleaving with the time stamp collection of the victim process.

8.1.1 Interleaving of Time Stamp Collection

Figure 38 Attack process interleaving with victim process

A Availability of Source Code

B Shared Library And Stand-Alone Daemon

C LFSR Loop Entropy Measurements

• the CPU,
• the word size (WS) of the software,
• whether the code compiled optimized with -O2 or not,
• the upper Shannon Entropy boundary,
• the lower Shannon Entropy boundary,
• the operating system, and
• whether the jent_entropy_init function would accept the CPU.

• a large range of CPUs ranging from embedded systems of MIPS and ARM CPUs, covering desktop systems with AMD, Intel and VIA x86 32 bit and 64 bit CPUs as well as Apple PowerPC, up to server CPUs of Intel Itanium, Sparc, POWER and IBM System Z;
• a large range of operating systems: Linux (different distributions and kernel versions), OpenBSD, FreeBSD, NetBSD, AIX, OpenIndiana (OpenSolaris), z/OS, Apple MacOS, Android, Windows, and microkernel based operating systems (Genode with microkernels of NOVA, Fiasco.OC, Pistachio);
• a range of different compilers: GCC, Clang, Microsoft Visual Studio, and the z/OS C compiler.

• Intel Mobile Celeron 733 MHz: The test shows that this CPU has insufficient execution jitter entropy. However, as this CPU is considered very old, the code has not been changed to catch this CPU behavior.
• IBM System Z 31 bit word size (marked as S/390 in the table above): The tests with optimized code indicates that the lower boundary has way too little entropy. However, when re-performing the tests on the same system without optimization, the lower and upper boundary again show significant improvements to values way above 1 bit. Therefore, non-optimized code is required for this system and word size which is granted for the compilation of the CPU Jitter random number generator. More details on this system is given in section C.46↓.
• Intel Xeon E5504: Section C.7↓ outlines that the test result is to be considered as an outlier. There are additional tests on a different Intel Xeon E5504 listed in the table above which show appropriate results for the lower boundary of the Shannon Entropy. When enabling memory access, the timing variations increase significantly above the threshold of 1 bit.

C.1 Intel Core i5 4200U

Figure 39 Lower boundary of entropy over LFSR loop in user space on Intel Core i7 3537U

Figure 40 Upper boundary of entropy over LFSR loop in user space on Intel Core i7 3537U

C.2 Intel Core i7 3537U

Figure 41 Lower boundary of entropy over LFSR loop in user space on Intel Core i7 3537U

Figure 42 Upper boundary of entropy over LFSR loop in user space on Intel Core i7 3537U

C.3 Intel Core i7 2620M compiled with Clang

Figure 43 Lower boundary of entropy over LFSR loop in user space on Intel Core i7 2620M – with optimizations

Figure 44 Upper boundary of entropy over LFSR loop in user space on Intel Core i7 2620M – with optimizations

Figure 45 Lower boundary of entropy over LFSR loop in user space on Intel Core i7 2620M – without optimizations

Figure 46 Upper boundary of entropy over LFSR loop in user space on Intel Core i7 2620M – without optimizations

C.4 Intel Core i5 2430M

Figure 47 Lower boundary of entropy over LFSR loop in user space on Intel Core i5 2430M

Figure 48 Upper boundary of entropy over LFSR loop in user space on Intel Core i5 2430M

C.5 Intel Core i5 2410M

Figure 49 Lower boundary of entropy over LFSR loop in user space on Intel Core i5 2410M

Figure 50 Upper boundary of entropy over LFSR loop in user space on Intel Core i5 2410M

C.6 Intel Core i7 Q720

Figure 51 Lower boundary of entropy over LFSR loop in user space on Intel Core i7 Q720

Figure 52 Upper boundary of entropy over LFSR loop in user space on Intel Core i7 Q720

C.7 Intel Xeon E5504

Figure 53 Lower boundary of entropy over LFSR loop in user space on Intel Xeon E5504 – with optimizations

Figure 54 Upper boundary of entropy over LFSR loop in user space on Intel Xeon E5504 – with optimizations

Figure 55 Lower boundary of entropy over LFSR loop in user space on Intel Xeon E5504 – without optimizations

Figure 56 Upper boundary of entropy over LFSR loop in user space on Intel Xeon E5504 – without optimizations

# byte wise
$ ./ent random.out 
Entropy = 7.999992 bits per byte.
​
Optimum compression would reduce the size
of this 22188032 byte file by 0 percent.
​
Chi square distribution for 22188032 samples is 260.80, and randomly
would exceed this value 50.00 percent of the times.
​
Arithmetic mean value of data bytes is 127.5139 (127.5 = random).
Monte Carlo value for Pi is 3.141290507 (error 0.01 percent).
Serial correlation coefficient is 0.000043 (totally uncorrelated = 0.0).
​
# bit wise
$ ./ent -b random.out 
Entropy = 1.000000 bits per bit.
​
Optimum compression would reduce the size
of this 178159616 bit file by 0 percent.
​
Chi square distribution for 178159616 samples is 1.39, and randomly
would exceed this value 50.00 percent of the times.
​
Arithmetic mean value of data bits is 0.5000 (0.5 = random).
Monte Carlo value for Pi is 3.141272175 (error 0.01 percent).
Serial correlation coefficient is -0.000187 (totally uncorrelated = 0.0).

C.8 Intel Core 2 Quad Q6600

Figure 57 Lower boundary of entropy over LFSR loop in user space on Intel Core 2 Quad Q6600 – with optimizations

Figure 58 Upper boundary of entropy over LFSR loop in user space on Intel Core 2 Quad Q6600 – with optimizations

Figure 59 Lower boundary of entropy over LFSR loop in user space on Intel Core 2 Quad Q6600 – without optimizations

Figure 60 Upper boundary of entropy over LFSR loop in user space on Intel Core 2 Quad Q6600 – without optimizations

C.9 Intel Core 2 Duo T5870

Figure 61 Lower boundary of entropy over LFSR loop in user space on Intel Core 2 Duo T5870

Figure 62 Upper boundary of entropy over LFSR loop in user space on Intel Core 2 Duo T5870

C.10 Intel Core 2 Duo With Windows 7

Figure 63 Lower boundary of entropy over LFSR loop in user space on Intel Core 2 Duo with Windows – without optimizations

Figure 64 Upper boundary of entropy over LFSR loop in user space on Intel Core 2 Duo with Windows – without optimizations

C.11 Intel Core Duo L2400

Figure 65 Lower boundary of entropy over LFSR loop in user space on Intel Core Duo L2400

Figure 66 Upper boundary of entropy over LFSR loop in user space on Intel Core Duo L2400

C.12 Intel Core Duo Solo T1300 With NOVA Microkernel

Figure 67 Lower boundary of entropy over LFSR loop in user space on Intel Core Duo Solo T1300 with Nova Microkernel

Figure 68 Upper boundary of entropy over LFSR loop in user space on Intel Core Duo Solo T1300 with Nova Microkernel

C.13 Intel Core Duo Solo T1300 With Fiasco.OC Microkernel

Figure 69 Lower boundary of entropy over LFSR loop in user space on Intel Core Duo Solo T1300 with Fiasco.OC Microkernel

Figure 70 Upper boundary of entropy over LFSR loop in user space on Intel Core Duo Solo T1300 with Fiasco.OC Microkernel

C.14 Intel Core Duo Solo T1300 With Pistachio Microkernel

Figure 71 Lower boundary of entropy over LFSR loop in user space on Intel Core Duo Solo T1300 with Pistachio Microkernel

Figure 72 Upper boundary of entropy over LFSR loop in user space on Intel Core Duo Solo T1300 with Pistachio Microkernel

C.15 Intel Atom Z530

Figure 73 Lower boundary of entropy over LFSR loop in user space on Intel Atom Z530

Figure 74 Upper boundary of entropy over LFSR loop in user space on Intel Atom Z530

C.16 Intel Core 2 Duo on Apple MacBook Pro

Figure 75 Lower boundary of entropy over LFSR loop in user space on Apple MacBook Pro – with optimizations

Figure 76 Upper boundary of entropy over LFSR loop in user space on Apple MacBook Pro – with optimizations

C.17 Intel Celeron

Figure 77 Lower boundary of entropy over LFSR loop in user space on Intel Celeron

Figure 78 Upper boundary of entropy over LFSR loop in user space on Intel Celeron

C.18 Intel Mobile Celeron 733 MHz

Figure 79 Lower boundary of entropy over LFSR loop in user space on Intel Mobile Celeron

Figure 80 Upper boundary of entropy over LFSR loop in user space on Intel Mobile Celeron

C.19 Intel Pentium P4 3GHz

Figure 81 Lower boundary of entropy over LFSR loop in user space on Intel Pentium P4 3GHz

Figure 82 Upper boundary of entropy over LFSR loop in user space on Intel Pentium P4 3GHz

C.20 Intel Pentium P4 Mobile

Figure 83 Lower boundary of entropy over LFSR loop in user space on Intel Pentium P4 Mobile

Figure 84 Upper boundary of entropy over LFSR loop in user space on Intel Pentium P4 Mobile

# byte-wise
$ ent random-p4mobile.data 
Entropy = 7.999998 bits per byte.
​
Optimum compression would reduce the size
of this 108351488 byte file by 0 percent.
​
Chi square distribution for 108351488 samples is 230.51, and randomly
would exceed this value 75.00 percent of the times.
​
Arithmetic mean value of data bytes is 127.5061 (127.5 = random).
Monte Carlo value for Pi is 3.141212037 (error 0.01 percent).
Serial correlation coefficient is 0.000075 (totally uncorrelated = 0.0).
​
# bit-wise
$ ent -b random-p4mobile.data 
Entropy = 1.000000 bits per bit.
​
Optimum compression would reduce the size
of this 866811904 bit file by 0 percent.
​
Chi square distribution for 866811904 samples is 0.12, and randomly
would exceed this value 50.00 percent of the times.
​
Arithmetic mean value of data bits is 0.5000 (0.5 = random).
Monte Carlo value for Pi is 3.141212037 (error 0.01 percent).
Serial correlation coefficient is 0.000023 (totally uncorrelated = 0.0).

C.21 AMD Opteron 6128

Figure 85 Lower boundary of entropy over LFSR loop in user space on AMD Opteron 6128

Figure 86 Upper boundary of entropy over LFSR loop in user space on AMD Opteron 6128

C.22 AMD Phenom II X6 1035T

Figure 87 Lower boundary of entropy over LFSR loop in user space on AMD Phenom II X6 1035T

Figure 88 Upper boundary of entropy over LFSR loop in user space on AMD Phenom II X6 1035T

C.23 AMD Athlon 7550

Figure 89 Lower boundary of entropy over LFSR loop in user space on AMD Athlon 7550 – with optimizations

Figure 90 Upper boundary of entropy over LFSR loop in user space on AMD Athlon 7550 – with optimizations

Figure 91 Lower boundary of entropy over LFSR loop in user space on AMD Athlon 7550 – without optimizations

Figure 92 Upper boundary of entropy over LFSR loop in user space on AMD Athlon 7550 – without optimizations

C.24 AMD Athlon 4850e

Figure 93 Lower boundary of entropy over LFSR loop in user space on AMD Athlon 4850e – with optimizations

Figure 94 Upper boundary of entropy over LFSR loop in user space on AMD Athlon 4850e – with optimizations

Figure 95 Lower boundary of entropy over LFSR loop in user space on AMD Athlon 4850e – without optimizations

Figure 96 Upper boundary of entropy over LFSR loop in user space on AMD Athlon 4850e – without optimizations

C.25 AMD E350

Figure 97 Lower boundary of entropy over LFSR loop in user space on AMD E350 – with optimizations

Figure 98 Upper boundary of entropy over LFSR loop in user space on AMD E350 – with optimizations

Figure 99 Lower boundary of entropy over LFSR loop in user space on AMD E350 – without optimizations

Figure 100 Upper boundary of entropy over LFSR loop in user space on AMD E350 – without optimizations

C.26 AMD Semperon 3GHz

Figure 101 Lower boundary of entropy over LFSR loop in user space on AMD Semperon 3GHz – with optimizations

Figure 102 Upper boundary of entropy over LFSR loop in user space on AMD Semperon 3GHz – with optimizations

Figure 103 Lower boundary of entropy over LFSR loop in user space on AMD Semperon 3GHz – without optimizations

Figure 104 Upper boundary of entropy over LFSR loop in user space on AMD Semperon 3GHz – without optimizations

# byte-wise
$ ent entropy.amdsemperon.O0 
Entropy = 7.999968 bits per byte.
​
Optimum compression would reduce the size
of this 5525504 byte file by 0 percent.
​
Chi square distribution for 5525504 samples is 247.18, and randomly
would exceed this value 50.00 percent of the times.
​
Arithmetic mean value of data bytes is 127.5252 (127.5 = random).
Monte Carlo value for Pi is 3.142346161 (error 0.02 percent).
Serial correlation coefficient is -0.000274 (totally uncorrelated = 0.0).
​
# bit-wise
$ ent -b entropy.amdsemperon.O0 
Entropy = 1.000000 bits per bit.
​
Optimum compression would reduce the size
of this 44204032 bit file by 0 percent.
​
Chi square distribution for 44204032 samples is 2.54, and randomly
would exceed this value 25.00 percent of the times.
​
Arithmetic mean value of data bits is 0.5001 (0.5 = random).
Monte Carlo value for Pi is 3.142346161 (error 0.02 percent).

C.27 VIA Nano L2200

Figure 105 Lower boundary of entropy over LFSR loop in user space on VIA Nano L2200

Figure 106 Upper boundary of entropy over LFSR loop in user space on VIA Nano L2200

C.28 MIPS 24KC v7.4

Figure 107 Lower boundary of entropy over LFSR loop in user space on MIPS 24KC v7.4

Figure 108 Upper boundary of entropy over LFSR loop in user space on MIPS 24KC v7.4

C.29 MIPS 24KC v4.12 Ikanos Fusiv Core

Figure 109 Lower boundary of entropy over LFSR loop in user space without optimization on MIPS 24KC v4.2

Figure 110 Upper boundary of entropy over LFSR loop in user space without optimization on MIPS 24KC v7.4

C.30 MIPS 4KEc V6.8

Figure 111 Lower boundary of entropy over LFSR loop in user space on MIPS 4KEc V6.8 – with optimizations

Figure 112 Upper boundary of entropy over LFSR loop in user space on MIPS 4KEc V6.8 – with optimizations

Figure 113 Lower boundary of entropy over LFSR loop in user space on MIPS 4KEc V6.8 – without optimizations

Figure 114 Upper boundary of entropy over LFSR loop in user space on MIPS 4KEc V6.8 – without optimizations

# byte-wise
$ ent random.fritz7270.out
Entropy = 7.999997 bits per byte.
​
Optimum compression would reduce the size
of this 58580496 byte file by 0 percent.
​
Chi square distribution for 58580496 samples is 241.25, and randomly
would exceed this value 50.00 percent of the times.
​
Arithmetic mean value of data bytes is 127.4989 (127.5 = random).
Monte Carlo value for Pi is 3.141300135 (error 0.01 percent).
Serial correlation coefficient is 0.000129 (totally uncorrelated = 0.0).
​
# bit-wise
$ ent -b random.fritz7270.out
Entropy = 1.000000 bits per bit.
​
Optimum compression would reduce the size
of this 468643968 bit file by 0 percent.
​
Chi square distribution for 468643968 samples is 0.01, and randomly
would exceed this value 75.00 percent of the times.
​
Arithmetic mean value of data bits is 0.5000 (0.5 = random).
Monte Carlo value for Pi is 3.141300135 (error 0.01 percent).
Serial correlation coefficient is 0.000042 (totally uncorrelated = 0.0).

C.31 MIPS 4KEc V4.8

Figure 115 Lower boundary of entropy over LFSR loop in user space on MIPS 4KEc V4.8 – without optimizations

Figure 116 Upper boundary of entropy over LFSR loop in user space on MIPS 4KEc V4.8 – without optimizations

C.32 ARM Exynos 5250 with Fiasco.OC Microkernel

Figure 117 Lower boundary of entropy over LFSR loop in user space on Exynos 5250 with Fiasco.OC – without optimizations

Figure 118 Upper boundary of entropy over LFSR loop in user space on Exynos 5250 with Fiasco.OC – without optimizations

C.33 ARMv7 rev 1 – Samsung Galaxy S2

$ cat /sys/devices/system/clocksource/clocksource0/available_clocksource
mct-frc
$ cat /sys/devices/system/clocksource/clocksource0/current_clocksource
mct-frc

Figure 119 Lower boundary of entropy over LFSR loop in user space on ARMv7 rev 1 – with optimizations

Figure 120 Upper boundary of entropy over LFSR loop in user space on ARMv7 rev 1 – with optimizations

Figure 121 Lower boundary of entropy over LFSR loop in user space on ARMv7 rev 1 – without optimizations

Figure 122 Upper boundary of entropy over LFSR loop in user space on ARMv7 rev 1 – without optimizations

C.34 ARMv7 rev 2 – LG Nexus 4.2

C.35 ARMv7 rev 0 – Samsung Galaxy S4

C.36 ARMv7 rev 1 – HTC Desire Z

C.37 ARMv6 rev 7

Figure 123 Lower boundary of entropy over LFSR loop in user space on ARMv6 rev 7 – with optimizations

Figure 124 Upper boundary of entropy over LFSR loop in user space on ARMv6 rev 7 – with optimizations

Figure 125 Lower boundary of entropy over LFSR loop in user space on ARMv6 rev 7 – without optimizations

Figure 126 Upper boundary of entropy over LFSR loop in user space on ARMv6 rev 7 – without optimizations

C.38 IBM POWER7 with AIX 6.1

Figure 127 Lower boundary of entropy over LFSR loop in user space on AIX 6.1 and POWER7 – with optimizations

Figure 128 Upper boundary of entropy over LFSR loop in user space on AIX 6.1 and POWER7 – with optimizations

Figure 129 Lower boundary of entropy over LFSR loop in user space on AIX 6.1 and POWER7 – without optimizations

Figure 130 Upper boundary of entropy over LFSR loop in user space on AIX 6.1 and POWER7 – without optimizations

C.39 IBM POWER7 with Linux

Figure 131 Lower boundary of entropy over LFSR loop in user space on IBM POWER7

Figure 132 Upper boundary of entropy over LFSR loop in user space on IBM POWER7

C.40 IBM POWER5 with Linux

Figure 133 Lower boundary of entropy over LFSR loop in user space on IBM POWER5

Figure 134 Upper boundary of entropy over LFSR loop in user space on IBM POWER5

C.41 Apple G5 QuadCore PPC 970MP

Figure 135 Lower boundary of entropy over LFSR loop in user space on Apple G5 with optimizations

Figure 136 Upper boundary of entropy over LFSR loop in user space on on Apple G5 with optimizations

Figure 137 Lower boundary of entropy over LFSR loop in user space on Apple G5 without optimizations

Figure 138 Upper boundary of entropy over LFSR loop in user space on on Apple G5 with optimizations

C.42 SUN UltraSparc IIIi

Figure 139 Lower boundary of entropy over LFSR loop in user space on SUN UltraSparc IIIi – with optimizations

Figure 140 Upper boundary of entropy over LFSR loop in user space on SUN UltraSparc IIIi – with optimizations

Figure 141 Lower boundary of entropy over LFSR loop in user space on SUN UltraSparc IIIi – without optimizations

Figure 142 Upper boundary of entropy over LFSR loop in user space on SUN UltraSparc IIIi – without optimizations

C.43 SUN UltraSparc II

Figure 143 Lower boundary of entropy over LFSR loop in user space on SUN UltraSparc II – with optimizations

Figure 144 Upper boundary of entropy over LFSR loop in user space on SUN UltraSparc II – with optimizations

C.44 SUN UltraSparc IIi (Sabre)

Figure 145 Lower boundary of entropy over LFSR loop in user space on SUN UltraSparc IIi – with optimizations

Figure 146 Upper boundary of entropy over LFSR loop in user space on SUN UltraSparc-IIi – with optimizations

Figure 147 Lower boundary of entropy over LFSR loop in user space on SUN UltraSparc IIi – without optimizations

Figure 148 Upper boundary of entropy over LFSR loop in user space on SUN UltraSparc IIi – without optimizations

C.45 IBM System Z z10

Figure 149 Lower boundary of entropy over LFSR loop in user space on z/OS – without optimizations

Figure 150 Upper boundary of entropy over LFSR loop in user space on zOS – without optimizations

C.46 IBM System Z z10

C.46.1 64 bit Word Size

Figure 151 Lower boundary of entropy over LFSR loop in user space on IBM System Z z10 – 64 bit with optimizations

Figure 152 Upper boundary of entropy over LFSR loop in user space on IBM System Z z10 – 64 bit with optimizations

Figure 153 Lower boundary of entropy over LFSR loop in user space on IBM System Z z10 – 64 bit without optimizations

Figure 154 Upper boundary of entropy over LFSR loop in user space on IBM System Z z10 – 64 bit without optimizations

C.46.2 31 bit Word Size

Figure 155 Lower boundary of entropy over LFSR loop in user space on IBM System Z z10 – 31 bit with optimizations

Figure 156 Upper boundary of entropy over LFSR loop in user space on IBM System Z z10 – 31 bit with optimizations

Figure 157 Lower boundary of entropy over LFSR loop in user space on IBM System Z z10 – 31 bit without optimizations

Figure 158 Upper boundary of entropy over LFSR loop in user space on IBM System Z z10 – 31 bit without optimizations

C.47 Intel Core i7 2620M With RDTSC Instruction

/* taken from Linux kernel */
#define DECLARE_ARGS(val, low, high)    unsigned low, high
#define EAX_EDX_VAL(val, low, high)     ((low) | ((__u64)(high) << 32))
#define EAX_EDX_RET(val, low, high)     "=a" (low), "=d" (high)
​
static inline void jent_get_nstime(__u64 *out)
{
        DECLARE_ARGS(val, low, high);
        asm volatile("rdtsc" : EAX_EDX_RET(val, low, high));
        *out = EAX_EDX_VAL(val, low, high);
}

• The user space of the operating system has an impact on the measurements. If a large number of user space applications are executing, including X11, the CPU execution time jitter is significantly larger compared to systems where hardly any user space application is running in parallel with the measurements.
• The size of the kernel has no significant impact on the CPU execution time jitter. Although the mean values of the tests on the BSD systems and the Linux system without X11 differ significantly, the jitter size itself represented by the number of different time delta values [M]  [M] I.e. the number of bars in the histogram. does not differ significantly.

C.47.1 Ubuntu Linux 13.04 with KDE

Figure 159 Lower boundary of entropy over LFSR loop in user space on Ubuntu Linux 13.04 with KDE and Intel Core i7 2620M

Figure 160 Upper boundary of entropy over LFSR loop in user space on Ubuntu Linux 13.04 with KDE and Intel Core i7 2620M

C.47.2 Ubuntu Linux 13.04 without X11

Figure 161 Lower boundary of entropy over LFSR loop in user space on Ubuntu Linux 13.04 without X11 and Intel Core i7 2620M

Figure 162 Upper boundary of entropy over LFSR loop in user space on Ubuntu Linux 13.04 without X11 and Intel Core i7 2620M

C.47.3 OpenIndiana 151a7

Figure 163 Lower boundary of entropy over LFSR loop in user space on OpenIndiana 151a7 and Intel Core i7 2620M

Figure 164 Upper boundary of entropy over LFSR loop in user space on OpenIndiana 151a7 and Intel Core i7 2620M

C.47.4 NetBSD 6.0

Figure 165 Lower boundary of entropy over LFSR loop in user space on NetBSD 6.0 and Intel Core i7 2620M

Figure 166 Upper boundary of entropy over LFSR loop in user space on NetBSD 6.0 and Intel Core i7 2620M

C.47.5 FreeBSD 9.1

Figure 167 Lower boundary of entropy over LFSR loop in user space on FreeBSD 9.1 and Intel Core i7 2620M

Figure 168 Upper boundary of entropy over LFSR loop in user space on FreeBSD 9.1 and Intel Core i7 2620M

D BSI AIS 20 / 31 NTG.1 Properties

• • BSI Test procedure A is passed.
  • BSI Test suite A is passed
  • dieharder test passed on kernel and user space generator
  • ent test passed
  Covered

E Bibliographic Reference

F Thanks

• Yi Mao
• Steve Weingart
• Jeremy Powell
• Gerald Krummeck
• Michael Robrecht
• Roman Drahtmüller
• Louis Losee
• Josef Söntgen
• Sandy Harris

G License

1. Redistributions of source code must retain the above copyright notice, and the entire permission notice in its entirety, including the disclaimer of warranties.
2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
3. The name of the author may not be used to endorse or promote products derived from this software without specific prior written permission.

H Change Log