Am Dienstag, 28. Mai 2013, 09:36:25 schrieb Andy Polyakov:
Hi Andy,
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:
- Linux kernel support: 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 optimizations 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)
>No specific distribution of samples necessarily speaks in favour of its
>randomness. Well, one can argue that its wideness kind of does, but
>it's not sufficient. Shannon entropy is not measure of randomness, but
>rather redundancy of data representation. It's used to put certain
>value on random data, but putting this value on any given data set
>doesn't tell anything about it being random. For example you can
>characterize following set by its distribution and entropy value, but
>it's not in any way random.
>
>* * *
> * * * * *
> * * * * *
> * * *
Please reconsider chapter 4 of [2]. This chapter discusses the
statistical properties of the data generated by the random number
generator. That section explains that no patterns are identified.
To cover your particular suggestion, I added section 4.4.2 to [2]. As
the CPU Jitter RNG does not use a cryptographic whitening function,
patterns will be visible in particular with the Chi-Square testing of
the output. As the Chi-Square tests indicate that output of the RNG does
not have a pattern, i.e. resembles White Noise, the suggestions for
patterns is not warranted.
And with the absence of patterns, the statistical Shannon Entropy
measurements and the information theoretical entropy have to be
considered identical.
>
>Yes, two rdtsc's one after another is extreme example, but it was a
>reaction to statement that *any* instruction sequence is subject to
>variations, which is simply not true. [Recall there was "if compiled
>with optimization on", but what about optimization? With optimization
>off, there is a number of redundant references to memory generated by
>compiler which makes output vary. But even then output is periodic and
>predictable. BTW, even *if* there was some actual randomness, do we
>want it to depend on user-selectable optimization level? Absolutely
>not.] More complex instruction sequences do execute in predictable
>manner. Because processors are *designed* that way, they are also
>designed to amortize eventual deviations [in interactions with memory
>subsystem] and do it pretty efficiently. And as already mentioned, OS
>gives *a lot* of opportunities for processor to exercise its
>capacities. If found, it is unamortized deviations that need
>explanation, not vice versa. In such case they even need ways to be
>detected, monitored and quantified [at run time]. "Hope that it's
>sufficient on another system" or vague references to "root cause"
>don't really cut it. HyperThreaded thread? Integrated graphics? Poor
>power supply? TurboBoost? For example TurboBoost is driven by thermal
>detector and moment of transition is likely to be viable source of
>real randomness, but how do you reliably detect that it's even option
>on arbitrary arbitrarily loaded system? [Keep in mind that it would
>make the code *highly* processor-specific].
Your description triggered the implementation of another test as
described in section 5.1 [2]. That testing resulted in the requirement
that the RNG must be compiled without optimizations.
With the initially shown implementation and documentation I did not
really show that sufficient entropy is gathered from the CPU execution
jitter. With the 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.
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.
>
>Printing values between probes is a slippery way. Printing is capable
>of introducing variations (buffer flush results in system call, which
>is likely to trigger varying set of events affecting cache, branch
>prediction, TLB, etc.), but one should remember that target
>application won't be printing anything [at least you can't make such
>assumption]. Test programs should act more like target application
>[simply assume the least], run experiment in memory and print results
>*afterwards*. Yes, rdtsc snippet contradicts this, but think of it as
>following: even with print it can be *that* predictable.
A calling application that really is interested in using the RNG for
real work only calls the RNG for one or maybe two random numbers. Each
random number is 64 bit in size. After the RNG execution, the
application will do other operations. The measurements are always done
my timing the generation of one full random number. Therefore, the tests
are considered to be very close to reality.
Moreover, the test results of the latest test, especially the
measurements of the lower boundary of the Shannon Entropy has still much
"leeway". The minimum requirement is to collect 1 bit of entropy, yet
the minimum Shannon Entropy measurements are significantly higher than
that value.
However, to ease your concerns, I performed the following: The new test
outlined at the beginning is implemented with the following pseudo code:
while(1)
{
time1 = gettime()
fold_operation
time2 = gettime()
timediff = time2 - time1
printf(timediff)
}
On one system I reimplemented the test again as follows which removes
the impact of the printf() impact:
while(1)
{
timediff = 0
for(c=0;c<1000;c++)
{
time1 = gettime()
fold_operation
time2 = gettime()
timediff = time2 - time1
}
printf(timediff)
}
The results of both executions are remarkably similar considering the
cutoff of the test results discussed in section 5.1 of [2]. The first
implementation of the test (with the cutoff applied) shows results
varying between 240 and 250. With the latter code, the tests show again
results varying between 240 and 250.
Bottom line: the test results of the new test case all exclude the
impact on the printf() processing.
>
>> Andy, as you have access to hardware that seem to cause concerns for
>> the RNG, may I ask you to run the test on the entropy that I used to
>> generate the two pictures? The test is at
>> http://www.chronox.de/jent/devel/jitterentropy-20130527-devel.tar.bz2
>
>No, I won't run it until printing is performed "off-line". And do
Now I performed the testing on my own on about 200 systems as indicated.
If you wish to perform the testing on your system, execute the test
explained at [3].
>switch on optimization.
As mentioned, optimizations are required to be turned off as they modify
the code in unknown ways. Especially when using the Clang compiler, the
optimizations on X86 are really amazing.
[1] http://www.chronox.de/jent/jitterentropy-20130724.tar.bz2
[2] http://www.chronox.de/jent/doc/CPU-Jitter-NPTRNG.pdf
[3] http://www.chronox.de/
Ciao
Stephan
--
| Cui bono? |
______________________________________________________________________
OpenSSL Project http://www.openssl.org
Development Mailing List [email protected]
Automated List Manager [email protected]
