Please help; hardware RNG using mains timing

Thread Starter

THE_RB

Joined Feb 11, 2008
5,438
Hi, I've been working on a hardware RNG based on gating the time period of a mains cycle (from a small 12v transformer) against a PIC timer running at 5MHz.

Currently it's going pretty good but I'd appreciate some feedback before finishing up the project. :)

Concept;
I knew from previous projects measuring the stability and average freq of the AC mains that each mains cycle (and half-cycle) had quite a few uS of error, due to the chaotic nature of the AC mains system and everything in the world connected to it.

I wanted a hardware based RNG that produces really good quality entropy, and wasn't happy with most of the typical solutions like diode junction noise etc, which are prone to a problem called "break" and produce a substandard entropy but you don't really know.

This concept was to capture the least significant bit of a free running 5MHz counter, for every mains half cycle (each 10mS as my mains is 50Hz). This is pretty much immune to "break" problems, and on any failure of the mains the RNG will simply stop.

Procedure;
The PIC 16F628A runs from regulated 5v, xtal of 20MHz, and its timer1 runs as a free running counter at 5MHz. 12v AC is taken from a plugpack, and rectified and set by a pot to be a 0v-5v waveform. That waveform is gated by the PIC comparator set to 1v setpoint, and debounced in software to give one gate per 10mS.

Every gate incident causes the PIC CCP1 module to capture the free running timer1, and only the least significant bit is used, these bits are compiled into bytes and sent out the serial port to a PC for logging. The RNG makes exactly 100 bits per second (12.5 bytes/sec).
 

Attachments

Thread Starter

THE_RB

Joined Feb 11, 2008
5,438
To give you an idea of the entropy available from timing a mains cycle to 200nS resolution (5MHz counter) here is a sample that I logged from the device.

This data is the deviation, ie the error in each mains half-cycle which should be 50000 counts. Resolution is 200nS so an error of 100 equals 20uS deviation compared to the "perfect" 10000uS period of a mains half-cycle;

Rich (BB code):
  51
-104
  61
-124
  78
-109
  62
- 71
  15
-104
  30
- 78
  58
- 92
  31
- 76
  26
- 94
  26
- 76
  51
-107
  40
- 81
  16
- 54
  24
- 79
  59
-116
  30
- 66
  41
- 80
You can see a definite 2nd harmonic error in the waveform, I assume this is from the total mains cycle being slightly asymmetrical, so this shows as tiny differences between the + and - half-cycles. There is also a possibility my bridge rectifier may have fractionally different forward voltages for the diode pairs, which would also contribute to this 2nd harmonic error.

For a RNG use this does not matter, what matters is that there is plenty enough chaos in the shape and timing of every mains half-cycle to produce unpredictability (entropy) to be captured by a high resolution timing system.

You can also see the mains freq is fast on average, compared to my 20MHz xtal. From past experience measuring the mains frequency I know it can be a few hundred parts per million fast or slow at any time, often for many minutes at a time. Again, for RNG use this does not matter.

The full data text file (from a few minutes of testing) is attached. (Whoops! Forum won't let me attach it, file is over 25kb). I will place the file in a link;
http://www.romanblack.com/RNG_temp/test_deviate.txt
 

Thread Starter

THE_RB

Joined Feb 11, 2008
5,438
Extracting some entropy from the counter capture.

I programmed the PIC to keep only the 3 least significant counter bits, captured by the automatic CCP1 timer1 capture. These 3 bits were formatted to a number 0-7 and outputted by serial as text.

Here is what the entropy of the 3 bits looks like;
Rich (BB code):
Last 3 (LSB) bits of 16bit capture, every mains half-cycle.

Freq;
0 = 825
1 = 841
2 = 826
3 = 818
4 = 807
5 = 834
6 = 823
7 = 831

Data;
4441703441374033040326314265333365532742436115722437171425667072
1406654466175712415306235421604663313333413116572647324235754275
5072501166725737774061467513657257075617703023362666715770215500
5550616677112110126056375634425601410363771767515216114253505623
1420153611616666661607344267745604212443352131541534251073317020
1242731714156711464673271255143435256104756662152257061303622404
2340005307177230124251401146626570352427425745631155206277277723
2003047111442526662534153642254400311747545553737541354237001634
(The full 0-7 data above is available in a text file here)
http://www.romanblack.com/RNG_temp/test_b7.txt

As you can see these are a pretty good random result, at least from such a small sample. There is a reasonably equal chance of each digit being 0-7.

For the RNG it is currently only using the highest quality bit, the LSB, but it is good to see the other 2 bits have a fairly high quality entropy that hopefully can be used in some type of hash function to provide "whitening" of the good bit. (I'll say more about that later).
 
Last edited:

Thread Starter

THE_RB

Joined Feb 11, 2008
5,438
Hi Bertus, thanks for the link. The PIC can be set to a zero crossing detector by setting the comparator Vref to 0v, but for this app I wanted to detect 2 equal half cycles, as the PIC capture module needs to detect a / slope, so I used the 1v point on each half-cycle 0v-5v slope. It's minimum hardware too as the PIC internal Vref and comparator do all the work. :)

Randomness of the 1bit data;
This actually looks very good. I was pleasantly surprised. I logged 100kbytes of data which took a while since the RNG only makes 12.5 bytes per second! i run the data through some tests.

Bit count 100kb file, total 800264 bits;
bit0 = 399847
bit1 = 400417

So the "whiteness" is pretty good, but not perfect. This shows the 1 bit is 0.14% more common than the 0 bit. Some of this is down to randomness itself, as 800kbit is still a fairly small sample.

I did a 40kbyte (320kbit) test as well, and for that test the 1 bit was about 0.08% more common than the 0 bit. Based on both tests I believe there is a very small bias, and although a bias this small is excellent for a hardware RNG process it would be good to remove it with some "whitening" process.

Entropy testing with the standard software ENT.EXE
The results here were very nice for such a "small" sample of 100kbyte. Everything was in order;



This looks about as good as it gets from that sample size. The important Chi square and serial correlation stats look good, and the slight bias in the Pi value is likely attibutable to the small 1 bit bias mentioned above.

That bit 1 bias should also be represented in the arithmetic mean, but that is practically perfect, which surprised me. I expected with slightly more 1 bits in the samples that the mean of all samples added would be high, it's actually a bit low. Maybe a math guy could speak up, but for now I expect that is just due to the sample size being too small for the mean to properly represent the bit bias (ie many of the 1 bits just happen to be in the low bits within the bytes).

The 100kbytes of binary data are available in this file;
http://www.romanblack.com/RNG_temp/test_binary.dat
if you wanted to do your own tests.
 
Last edited:

Thread Starter

THE_RB

Joined Feb 11, 2008
5,438
Sorry it got late at night posting those and I didn't get around to the "asking for help" bit.

Since the output random data from the LSB is good quality but has a small bias, I wanted to use the other 2 bits that are available in each sample and use some hashing process to merge that data into the LSB output in a way that would remove the bias.

Ideally this would also introduce some more entropy to the output, so would not only fix the bias but might also increase the quality of the RNG output.

Since I have 3 seemingly "good" bits from each sample, my first thought was for every sample to put the bit1 and bit2 into their own shift registers, and after some amount of cycles hash the output bit from those shift registers with the new sample bit0. This would hash together 3 bits, taken from different points in time.

Hopefully this would fix the small 0:1 bias in the LSB. If there is still some bias, then I could also hash in a repeating 0101 sequence which would give a result of inverting every second bit, a rather strong way of removing the bias.

I'm interested in any feedback from people on the best way of doing this. From what I understand about XOR hashing it never loses any entropy from the data, but it may dilute it. For instance if I XOR the 4 separate bits; bit0, bit1, bit2, and the 01 pattern, then the LSB is only responsible for 1/4 of the entropy in the final data.

Although no entropy from the LSB is lost, I would prefer it if it is responsible for the majority of the output, and the other 2 or 3 bits only partially responsible. I prefer that because technically the LSB has the highest entropy of all the bits.
 

Thread Starter

THE_RB

Joined Feb 11, 2008
5,438
I've done some tests hashing the other 2 bits with the bit0, results are looking good.

The procedure is very simple, the bit1 and bit2 are shfited into two separate shift registers. Then for every new sample, the new bit0 (from this cycle) is XORed with the bit1 from 47 cycles ago and the bit2 from 29 cycles ago. Since there should be no statistical correlation between a random bit0 from this cycle and a random bitX from Y cycles ago, this adds additional randomness to the output and also the XOR process should be enough to remove the small bit bias that seemed to be in bit0.

I've collected a couple of sets of data and will soon post the results. :)

Since the hardware seemed to be sorted on the dev board, I soldered up a protoype on some veroboard and put it in a translucent 3"x2" zippy box. There is a 12v AC plug, which generates the RNG data and also poweres the device, a "data good" green LED, and the serial plug going out to the PC.



 

Thread Starter

THE_RB

Joined Feb 11, 2008
5,438
Just an update, the new software has been tested using this simple (non-math) XOR algorithm;



and the results all tested quite nicely;



So I have written the project up and put it to bed. :) The C source code and everything you might need to make one, or play with this concept are on my page here;
http://www.romanblack.com/HardRNG/HardRNG1.htm
 
Top