SD16 random number generator

After brief look in your paper I see that you do not test whole package of NIST tests. Few serial tests does not count. You shall show reasonably large NIST test sample data on 10^6 bit sequences to demonstrate that you got true RNG.

Hello Ilmars,

Thanks again for your useful comments on the earlier thread.

This is another interesting comment on an important issue. As with some of your previous ones, what is interesting is why I disagree.

First, yes it would be good to do more tests from the NIST set. The situation here limited me to just that one for now. Perhaps I can fill in later. If someone else gets to it first, then please tell us all about the results.

But no, doing all of the tests in the suite continuously for years would not guarantee a true random number generator. You can't test for true randomness. You have to first make sure that the physical source is truly random, and then look for errors in capturing that random behavior. In a less brief read of the note you will find the appendix in which I explain all that.

In any case, it is certain that the NIST suite contains no tests for true randomness: Carefully constructed pseudo-random generators can pass all of them.

We need to build in the physical randomness and detect errors of construction. That is why I am so interested in a better look inside the SD16, and less interested in more statistical tests beyond the value frequency (histogram) and autocorrelation tests, plus that one from the NIST suite (via Dieharder)  that happened to be convenient. Yes, more NIST tests would have some value, but they are not high on my list.

Cheers,

Phil

Phil Ekstrom said:

We need to build in the physical randomness and detect errors of construction.

Exactly. To judge properties of your RNG, single (serial) test is not enough. For example what about 1 and 0 balance which is checked by frequency test? Please run and publish results of whole test suite, statistically reasonable amount of runs.

example:

http://www.cryptography.com/public/pdf/Intel_TRNG_Report_20120312.pdf

Phil Ekstrom said:

In any case, it is certain that the NIST suite contains no tests for true randomness: Carefully constructed pseudo-random generators can pass all of them.

Of course! So what? Does it automagically mean that NIST suite cannot test hardware RNG? Actually all the argumentation is written in chapter "4. Testing Strategy and Result Interpretation" of NIST doc. It's also said that if your RNG consistently tend to fail at least one of the tests, then it is not good RNG.

Phil,

Due to our AC power frequency, I often see 60Hz or 120Hz noise everywhere. I wonder if they also sneak into the numbers you generated. The effects are probable very small and not obvious. But if you do a Fourier Analysis of your 10^6 numbers, you should be able to detect  their existence near 60 or 120 Hz in the frequency domain.

-- OCY.

OCY,

Sorry for the delay in responding.

We have not directly done a Fourier analysis of the data, but the spectral density of a signal is the Fourier transform of its autocorrelation function (Weiner-Khintchine theorem) so we can look at the autocorrelation function, which we did calculate, and try to find any evidence of a periodic signal in it. The range of lag L we covered (up to 20 at 256usec per unit) only spans about 5msec of time, not the16msec that would be ideal in looking for 60Hz signals, but still if there is anything intruding we should see about 1/3 cycle of a 60Hz signal, 2/3 cycle of 120 Hz and so on. There is certainly nothing obvious in the graph of the autocorrelation function. Any harmonics up to 2KHz or so would make a positive contribution to the first few correlation values, and we see nothing incompatible with noise.

Actually there are two reasons that I don't expect to see any. First, the ADC is looking at a short-circuited input where the short is actually on the chip, and the module has been designed to do its ADC bit when run from a real-world power supply with finite regulation. It would be surprising to me if there were any way that power-line hum could get in. Second, the variation in effective input voltage due to any added hum that did get in would be slow in comparison to the sampling rate, and should be rejected for the same reasons discussed in the note about rejecting changes in the input voltage to the ADC.

I mentioned the data first, since a theoretical argument is always more convincing when explaining data than when predicting it - until one does the experiment. Then a prediction looks either better or worse - depending on what the data turn out to be.

Here's some more data, now after the prediction. lmars has been pushing me to run the whole NIST STS test suite on the output of the generator, and my colleague Ray Glaze has now done that (in addition to having already done all the previous desktop calculation) and has joined me as an author of the note.  The generator passed all tests. His results are now included in yet another appendix to the latest version of the note, which I will attach.

The note is now getting pretty long, but I guess I won't apologize. This is an area where care is important. European chip-and-PIN smart cards are being successfully hacked these days because of a faulty RNG. Some of the Snowden revelations also concern weakened pseudo-RNGs.

Phil

Phil Ekstrom said:

lmars has been pushing me to run the whole NIST STS test suite on the output of the generator

I just tried to tell newcomer automobile manufacturer that passing just fuel consumption test is not enough to convince potential customers :)

Phil Ekstrom said:

The generator passed all tests.

Now cryptoanalytics maybe even pay attention to your job - if you let hem know. Well done!

Ilmars,

I agree; pushing me on that was indeed a useful thing to do.

Perhaps I should have directed a reply to you also. Thinking about that now it seems that it would have been courteous of me. But I guessed - correctly it would seem - that if I just answered the last message in the thread you would see it.

I'd still like to get a comment from someone in the SD16 design effort before I go any more public about this. I did send a message to them via the tech support group and was told to post the material here, but no response yet.

Phil

Phil Ekstrom said:

I'd still like to get a comment from someone in the SD16 design effort before I go any more public about this.

You shall try to post data converters forum. Then you will have better chances to get needed attention from delta-sigma ADC expert

Thanks for the suggestion. I have now posted in the data converters forum.

Phil Ekstrom

To all,

Some units of the SD16_A produce a biased LSB when used as a random byte generator in the way that we suggested doing. Each byte is then worth only a little more than 7 bits of entropy instead of 8. While a minority of SD16_A modules operate in this less satisfactory way (4 out of 14 MSP430F2013s tested so far), the rest (10 of 14) work as originally described.

The good ones stay good, the poorer ones stay as they are through power cycles and program reloads. There is a simple test to screen out the biased ones.

All this and some other new stuff can be found in Rev H if our note attached to this message.

Phil Ekstrom

Attaching the document Phil is referencing.

Regards,

BrianSD16_A RNG Rev H.pdfSD16_A RNG Rev H.pdf

3757.SD16_A RNG Rev H.pdfExperiment in attaching: