Go Down

Topic: Additional Information on Avalanche Noise for entropy gathering (Read 3451 times) previous topic - next topic

wanderson

I have updated the google code page with additional information on my research into the long term performance of using valanche noise to generate entropy (random numbers).  In addition to adding more detailed information on the first 811 10,000,000 byte samples that were collected as of last year, I have added another 400 samples from the same circuit.  This was after leaving the circuit powered off for about eight months.

The results are intriguing, as you can see from this graph of the median calculated prior to the generation of each 10,000,000 byte sample file.



The medians start out much higher than they were in the first set of samples, but after about three weeks they settled into much the same pattern that had existed in the first set of samples.

One modification, I made in Mr. Seward's idea of performing a 'calibration' by calculating a median of the first few bytes.  It is these medians that are displayed in the above graph.  The preliminary analysis of the entropy's performance, particularly in relation to the median calculated for that particular set indicate that no relationship exists.  This would be partially explained by the additional whitening operations (von Newman, etc...) performed by the software.  I suspect that two factors are in play.  First, one needs only the approximate middle value to determine 1's and 0's for the whitening algorithms to produce reliable uniform randomness.  Secondly, I believe that regular median calibration will help maintain the generation rate of the circuit.  Since, the von Newman portion of the whitening algorithm serves to remove any consecutive bits with the same value.

If you want to look at the more detailed results from these initial studies, they are available from http://code.google.com/p/avr-hardware-random-number-generation/wiki/AvalancheNoise  The following is available for each of the 1200+ 10,000,000 byte entropy files gathered to date.

Code: [Select]


Value Char Occurrences Fraction
   0         40002017  0.5000252125
   1         39997983  0.4999747875
Total:       80000000  1.0000000000


Value Char Occurrences     Fraction Expectation    Deviation
   0           39,303  0.393030000%   39,062.50     240.5000
   1           38,890  0.388900000%   39,062.50     172.5000
...
254           39,026  0.390260000%   39,062.50      36.5000
255           39,074  0.390740000%   39,062.50      11.5000
Total:     10,000,000  100.0000000%      Mean =     159.1172

Entropy = 7.999982 bits per byte.

Optimum compression would reduce the size
of this 10,000,000 byte file by 0.00%

Chi square distribution for 10,000,000 samples is 249.24, and randomly
would exceed this value 58.99% percent of the time.

Arithetic mean value of data bytes is 127.5027 (127.5 = random)
Serial correlation coefficient is 0.000010 (totally uncorrelated = 0.0).




Of note is that none of the produced files have failed the ent style entropy tests since the very first few, while I was still revising the whitening algorithm...  And preliminary tests using more rigourous testing procedures have yet to find any issues with the data produced.  A caution for those considering using this type of circuit in any critical area.  The electronics are very sensitive to construction issues, and outside noise sources.  The whitening helps filter out the latter, but a strong enough outside signal source could compromise the circuit.  Assembly in an EMI shielded case, and other precautions should be implemented with any critical application.

MarkT

[ I will NOT respond to personal messages, I WILL delete them, use the forum please ]

wanderson

That is a much more complicated question than you might be aware of.  First the diehard series of tests have a number of known flaws, which is why they have been superceded by other more refined tests such as dieharder and TestU01 among others.  All of these testing suites are really designed to test psuedo-random number generators so they have an issue with true random generators which by definition will occasionally fail some of their tests, but if tested again with a new batch of data will not fail in the same area.  PRNG's will tend to fail in very predictable ways, where TRNG will only fail the tests occasionally and with no predictable pattern.

A simple illustration of this issue can be found by looking at the results for the chi-squared probabilities provided...  The general rule is that probabilities of < 2.5% or > 97.5% are considered fails...  So if you simply use those measures you find a fair number of fails among the 1200+ samples produced.  However, such occasional 'failures' are in fact very consistent with the behavior expected from a truly random source.  If the source were flawed one would expect failures from much further along the 'tails' of the distribution and that those failures would be more frequent (and predictable).

So to answer you question, I am continuing to run dieharder and TestU01 tests on the data as new data samples become available (dieharder required a minimum of 400 MB of random data) and while the occasional test is found to have been 'failed', no pattern or consistency is found when the same suite of tests is performed on the next round of data samples.

So far it appears that the real area of concern with this source of entropy is not the entropy capability itself, but rather its potential susceptibility to outside influence if the circuit is not properly implemented, tested, and kept shielded.  In short the physical security of the device is paramount to maintain the integrity of the entropy source.

MarkT

Is there code to both collect entropy from such a circuit and also perform basic sanity
checking to detect circuit malfunction (before releasing the supposed entropy to the
caller)?

I've been playing with the new Due and have yet to try out its built in RNG.
[ I will NOT respond to personal messages, I WILL delete them, use the forum please ]

Coding Badly


Have you tried / considered using something like this for whitening...

• Save reading A
• Save reading B
• If A == B start over
• If A < B output zero otherwise output one

I believe that's essentially how atomic decay based generators whiten (using time between events instead of analog value).  It should eliminate the need to calculate / refresh a median and should naturally compensate for changes in the hardware.

MarkT

That's mentioned amongst many other useful things in chapter 9 of "Cryptography Engineering" I believe.  Worth reading (the whole book).  Fergusson/Schneier/??
[ I will NOT respond to personal messages, I WILL delete them, use the forum please ]

wanderson

#6
Dec 24, 2013, 03:47 pm Last Edit: Dec 24, 2013, 04:03 pm by wanderson Reason: 1

Is there code to both collect entropy from such a circuit and also perform basic sanity
checking to detect circuit malfunction (before releasing the supposed entropy to the
caller)?

I've been playing with the new Due and have yet to try out its built in RNG.


The ent utility was created to perform the exact procedure you are describing.  
John Walker uses it to monitor samples from his radioactive decay based TRNG as a QC measure.  He discards his 'entropy' as it is read.  Using the more sophisticated tests, such as dieharder or TestU01 would be problematic, since they require hundreds of megabytes of data to perform a complete test and even then, true RNG's will fail the occasional parts of those tests, just not in a predictable way.  That is why multiple test runs are nescessary to ensure that the TRNG is producing valid output.  The Chi square test is the best way to identify a problem quickly with a TRNG.  If two consecutive test results are outside the range 0.01 > p < 0.99 then a given TRNG has a problem.  Of couse, the 'test' passage doesn't mean that the TRNG doesn't have other subtler problems, which is why the more strident tests are needed.

If you want to implement the chi-square test in the Due, the source from the ent utility would be a good place to start.  It implements the chi-square calculation AND the cummulative probaility density function needed to convert the raw ChiSq value to a probability.

wanderson



Have you tried / considered using something like this for whitening...

• Save reading A
• Save reading B
• If A == B start over
• If A < B output zero otherwise output one

I believe that's essentially how atomic decay based generators whiten (using time between events instead of analog value).  It should eliminate the need to calculate / refresh a median and should naturally compensate for changes in the hardware.



Yes, I incorporate the Von Neumann whitening as one of the whitening techniques I use in the source for this project...  Of possible interest, is that by itself, it didn't work to provide a uniform distribution to the entropy produced by my radioactive decay (RD) test bed either.   I suspect that the bias issues I noted were caused by the physical measurement devices used (ie Arduino Mega) since the radioactive decay is considered the 'ideal' random entropy source.  Even Mr. Walker notes, that his set-up requires whitening (the Von Neumann you mention), which does seem to confirm that simply 'measuring' the time between decays introduces some bias.

I haven't seen any reports of the issues that arose with my RD tests, but I have abandoned further testing on that area since I am tired of replacing expensive geiger counters.  Using the same Arduino Mega computation bed, I started out with an Aware RM60 (same as John Walker's Hot bits) and sealed the counter and a radioactive source in a lead box.  Over a period of time, the counter showed progressively higher generation rates that had me wondering if my source was getting more 'radioactive'...  Though not normally possible, if some aspect of the test setup was generating neutrons it was theorectically possible,,,

I purchased a second counter, to get an independant estimate of the radioactivity of my source.  As should have been the case, it hadn't changed.  Indeed the RM60 showed the same extraordinarily high count levels, even when it was only being subjected to normal background radiation.  My conclusion was that some aspect of the counter's circuitry failed.  So I replaced the RM60 with the Images SI counter I had used to verify the radioactivity level.  That lasted about six months (about 1/4 the time it took for the RM60 to fail) until it too exhibited the exact same problem.  I sent Mr. Walker an email to see if he had ever encountered a similar problem; however, I never received a response.  Given the several hundred dollar cost for these 'cheap' geiger counters I didn't want to ruin a third.  I suspect some aspect of these counters circuitry fails if left running 24x7...

Curiously, the RM60 failed completely shortly after it was removed from the test environment.  The Images SI counter still works, technically; however, it reports a count level that one might expect inside a nuclear core when it is only subjected to normal background radiation.  I haven't gotten around to trying  to diagnose the problem.

Go Up