On Sat, 25 May 2013 11:19:09 +0200 Andy Polyakov <[email protected]> wrote:
Hi Andy, > Hi, > > > You would think that you are correct since the system should be > > deterministic. > > I don't have to think it, program output gives evidence. On P4 I get > just 80, on an Atom system I get 22-33-22-33-22-33-..., on a > Bulldozer 40-44-40-44-40-... Once again, "[rdtsc readings] can form > complex yet periodic structure." Well, above are not exactly complex, > but undoubtedly periodic. > > > But it does not show such deterministic behavior. And > > when you say that after a few hundred cycles all should be settled, > > why do I see some 200,000 outputs from the code of yours on an > > otherwise idle system? > > It is *your* job to explain it. I am fully on your side that I have to explain it. And I do not dispute what you see. But allow me to explain a bit more what the RNG is doing. To explain the RNG concept, I would like to step a bit away from the pure time gathering we just discussed. As stated in the documentation, the RNG consists of two components: the folding loop and the entropy collection loop. With each entropy collection loop, one time stamp is read and the delta to the previous round is calculated. That delta is given to the folding loop. That means that during one iteration of the entropy collection loop, the folding loop is executed. The entropy collection loop rests on the assumption that the time delta per round contains one bit of entropy. The time delta in the entropy collection loop, however, depends on the execution time of the folding loop. Thus you can say: the time variation over the folding loop must return at least one bit of entropy. When you compare this to the pure foundation of getting two time stamps immediately after each other, you now have some code between the reading of the two time stamps to get one delta. Now, to really judge whether sufficient entropy is collected, the time variation over the folding loop must be tested instead of taking two time stamps immediately after each other. In the code, I use 4 knobs to turn this entire model: MIN|MAX_LOOP_COUNT_BIT -- setting the number of entropy collection loops MIN|MAX_FOLD_LOOP_BIT -- setting the number of folding loops I see that the current settings of the FOLD_LOOP_BIT are too low and the settings for LOOP_COUNT_BIT are too high (note: the entropy collection loop does NOT provide any entropy but ensures that it is collected properly). I adjusted these knobs a bit and get the following distribution of the folding loop when executing it with the exact minimum numbers of 1<<6 folding loops (note the graph cuts off outliers with higher variations): http://www.chronox.de/jent/devel/userspace-foldtime-time-dist-delta-12250-hist.png In this picture you see, with the minimum number of folding loops -- the worst case --, on my system I already have more than 6 bits of (Shannon) entropy. And I only need 1 bit. So, I have a leeway of 5 bits in the worst case that I am "wasting". My hope is that this leeway is sufficient for even the more problematic systems. When executing the folding loop over the entire range of loop counts of 64 different loop count values (as done in the regular operation), I get http://www.chronox.de/jent/devel/userspace-foldtime-time-dist-delta-25000-hist.png There you see 64 spikes, where each spike is one instance of the first graph, moved by the slightly longer duration of the folding loop when having 65 foldings instead of 64, 66 foldings instead of 64, and so on. This is the regular case and the graph shows more than 12 bits of (Shannon) entropy where I only need 1 bit. So I have a leeway of 11 bits in the regular case that I am "wasting". Again, my hope is that this leeway is sufficient for even the more problematic systems. 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 Please execute make -f Makefile.foldtime and simply execute ./jitterentropy-foldtime > output. Could you please either give the output file to me or I can give you the R-project files that can generate the graphs? Thanks a lot Stephan -- | Cui bono? | ______________________________________________________________________ OpenSSL Project http://www.openssl.org Development Mailing List [email protected] Automated List Manager [email protected]
