[PATCH][RFC] Tests on 200 different CPUs/Arches and OSes with CPU Jitter RNG

[PATCH][RFC] Tests on 200 different CPUs/Arches and OSes with CPU Jitter RNG

[Stephan Mueller]

Hi Sandy, Ted,

(this is a reply to [3])

I prepared a new release of the CPU Jitter RNG available at [1]. The 
core of the RNG remains unchanged. However, there are the following 
changes:

- addition of a patch to integrate the RNG into /dev/random as explained 
in appendix B.3 of [2], although the long-term goal of the RNG is rather 
the integration into the kernel crypto API when considering the Linux 
kernel as outlined in appendix B.1 of [2]

- ensure that the code is compiled without optimization based on the 
reasons outlined in section 5.1 of [2]

- addition of chapter 5.1 to [2] explaining how the entropy is collected

- additional code to execute the CPU Jitter RNG on different OSes 
(specifically AIX, MacOS and z/OS -- other Unixes are good without 
additional changes)


>On Tue, May 21, 2013 at 3:01 PM, Theodore Ts'o <tytso@mit.edu> wrote:

>> I continue to be suspicious about claims that userspace timing
>> measurements are measuring anything other than OS behaviour.

>
>Yes, but they do seem to contain some entropy. See links in the
>original post of this thread, the havege stuff and especially the
>McGuire et al paper.

With the initially shown implementation and documentation I did not 
really show that sufficient entropy is gathered from the CPU execution 
jitter -- i.e. that there is unpredictable jitter in the execution time. 
With a new test I now closed that hole. The newly added test 
measures the entropy gathered during execution jitter collection, i.e. 
heart of the RNG in terms of how much statistical entropy it provides. 
The description of the test is given in section 5.1 of [2]. To ensure 
that the statistical entropy measurements are indeed showing the 
information theoretical entropy, section 4.4 of [2] outlines that 
patterns are not identified in the output of the RNG which would 
diminish the information theoretical entropy compared to the statistical 
entropy.

That test was then executed on about 200 different systems with the 
results given in appendix F of [2]. The table stated there supported by 
the many graphs demonstrates that the CPU Jitter random number generator 
delivers high-quality entropy on:

- a large range of CPUs ranging from embedded systems of MIPS and ARM 
CPUs, covering desktop systems with AMD and Intel x86 32 bit and 64 bit 
CPUs up to server CPUs of Intel Itanium, Sparc, POWER and IBM System Z;

- a large range of operating systems: Linux (including Android), 
OpenBSD, FreeBSD, NetBSD, AIX, OpenIndiana (OpenSolaris), AIX, z/OS;

- a range of different compilers: GCC, Clang and the z/OS C compiler.

The test results show an interesting yet common trend -- i.e. common for 
the different CPU types: the newer the CPU is, the more CPU execution 
time jitter is present.

[2] appendix F.37 contains entropy measurements on different operating 
systems on the very same hardware, indicating that the jitter 
measurements are present regardless of the OS.

With the test results, Ted's concerns should be removed.

[...]


>> For devices like Linux routers, what we desperately need is hardware
>> assist;  [or] mix
>> in additional timing information either at kernel device driver
>> level,
>> or from systems such as HAVEGE.

The concern with HAVEGE is that it is very complex. The implementation 
is far from being straight forward.

>> 
>> What I'm against is relying only on solutions such as HAVEGE or
>> replacing /dev/random with something scheme that only relies on CPU
>> timing and ignores interrupt timing.

>
>My question is how to incorporate some of that into /dev/random.
>At one point, timing info was used along with other stuff. Some
>of that got deleted later, What is the current state? Should we
>add more?

Please see the suggestion for an integration with /dev/random given in 
appendix B.3 of [2]. The source code for the integration is given in 
patches/linux-3.9-random.patch which is described in patches/README. The 
patch only utilizes the CPU Jitter RNG when the entropy in the entropy 
pool falls below the low threshold, i.e. when no entropy from other 
sources is present.

[1] http://www.chronox.de/jent/jitterentropy-20130818.tar.bz2

[2] http://www.chronox.de/jent/doc/CPU-Jitter-NPTRNG.pdf

[3] http://www.gossamer-threads.com/lists/linux/kernel/1716565#1716565


Ciao
Stephan
-- 
| Cui bono? |

Re: [PATCH][RFC] Tests on 200 different CPUs/Arches and OSes with CPU Jitter RNG

[Stephan Mueller]

Am Sonntag, 18. August 2013, 20:05:52 schrieb Stephan Mueller:

Hi Ted, Sandy,

For FIPS 140-2, there is currently a draft of an Implementation Guidance 
discussed covering the requirements of seed sources for deterministic 
random number generators. The standard seed source when having no 
hardware RNGs is either /dev/urandom or /dev/random. Please note that 
the current discussion explicitly prohibits the use of /dev/urandom for 
FIPS 140-2 compliant systems.

In addition, the recommendation of SP800-90B is available in draft form 
at [1] placing quite severe requirements on seed sources. After 
assessing the above mentioned IG discussion and in discussions with the 
German BSI, these governmental folks seem to interpret the concept of 
entropy as solely information theoretical entropy. They seem to 
disregard cryptographic strength added by a whitening function. 
Therefore, my gut feeling is that /dev/urandom is also questioned by 
SP800-90B -- but I have no proof at this point.

That focus on information theoretical entropy ultimately implies that 
only /dev/random can be used and /dev/urandom must not be used. 
Naturally, many people are not happy with that due to the blocking 
behavior. Especially in a headless environment like server systems, 
Linux is currently starved of entropy. This is even more a problem with 
virtualized environments. For example, some time ago we tried to obtain 
48 bytes out of /dev/random on a PPC system after the entropy pools 
where completely drained. Well, we got it after some 20 hours as the 
system was quiet (it may now be a bit better with the interrupt usage in 
current kernels, but still there will be a noticeable block).

Now, people will scream: those governmental guys sell snake oil and we 
should still use /dev/urandom. And I have to concur. Yet, I am just 
delivering the message. With the German BSI, the last discussion showed 
that they are open to allowing /dev/urandom based on extensive 
discussions. Yet, you have to make quite a stance to prove that.

>- addition of a patch to integrate the RNG into /dev/random as
>explained in appendix B.3 of [2], although the long-term goal of the
>RNG is rather the integration into the kernel crypto API when
>considering the Linux kernel as outlined in appendix B.1 of [2]

All in all, with the suggested CPU Jitter RNG, all of this would be an 
issue of the past on systems the init function considers appropriate -- 
in my tests more than 95% of all systems are accepted. When using my 
patch on /dev/random, dd shows a throughput of about 6kb/s on my system 
when pulling out megabytes of data. It will be slower on slower systems, 
but yet it will not block. Moreover when pulling data for seed which is 
only a few bytes at a time, the invocation of /dev/random will not show 
any noticeable delay.

PS: As I mentioned earlier, however, my long term goal would be that 
callers would disregard /dev/random entirely as it is a central entropy 
source and therefore the prime spot for attacks to reduce entropy. With 
the jitter RNG, even unprivileged user space can have its own instance 
of a seed source.


[1] http://csrc.nist.gov/publications/PubsDrafts.html#SP-800-90-B


Ciao
Stephan
-- 
| Cui bono? |