True random number generator using atomic decay with NetBSD

More fun with Raspberry Pis and NetBSD

This is a continuation of the stratum 1 NTP clock stuff I did involving Raspberry PI boards and NetBSD. This is a active work in progress. This page may change often, as may the links.

What was created?

True random numbers can only be brought about by using something that has no particular period to it, in a nut shell. I don't really understand the math that is involved here, but there are a lot of sites and papers which describe what goes on.

What I did was took a DIY Geiger counter kit from MightyOhm and coupled it to a Raspberry PI 3 running NetBSD 8.99.3. The MightOhm kit has a nice 3.3V output pulse that can be easily fed into a GPIO pin on the RPI3. In addition, NetBSD has a very good entropy pool management infrastructure in the kernel that made it pretty simple to shove one bit of entropy into the pool.

The second need in this project was a source of atomic decay. It turns out that it is pretty simple and pretty inexpensive to get low level radioactive ore from United Nuclear. I bought a small amount of granular fragments that will serve as a atomic decay source for the geiger counter to detect.

The last part needed for this was to choose an algorithm and understand what makes a pulse from the counter a random event. NetBSD is helpful in this respect as the entropy pool infrastructure has the ability to measure the time between events in the pool. So, this resulted in what I called Method #0, simply send the event to the pool and collect entropy on the time.

However, that is not the only way to do things. Reading the paper RANDy - A True-Random Generator Based On Radioactive Decay the author talks about three possible ways to extract bits from radioactive decay.

I implemented all three of the algorithms mentioned in the paper as well as a couple of antibias, or unbias algorithms.

I also implemented a couple of additional methods.

The driver code build upon the work done on the stratum 1 NTP servers I did a while ago. The following patches to the NetBSD code base should be applied after the patches used for the NTP servers:

In a addition to the above patches, a kernel was built with a larger entropy pool. This is done by adding this:
makeoptions     COPTS+="-DRND_POOLWORDS=2048"
to the kernel config file and building the kernel. There are some warning in the sys/rnd.h about how this symbol must be formed. In particular, it needs to be a power of 2 and I believe it will not go any larger than 2048. With this set to 2048, the entropy pool is increased from 4096 bits to 65536 bits.

The hardware consists of:

(Image taken during testing, top of the lead box not shown)

The geiger counter kit from MightyOhm is not calibrated. The main way to do that would be to acquire a standard radioactive decay source and measure it, adjusting the voltage going to the tube. However, these standards are quite expensive. Mostly I wanted to know if I was over driving the voltage on the tube. However, the amps are very low any any normal DMM will influence the reading you are trying to get, so in order to get a ball park idea as to the voltage being fed into the tube, I acquired a 1GOhm resister from Mouser and made a probe from it. If you know the input impedance of a DMM you can calculate what about what the voltage going into the tube is.

How well does it work?

The $64,000 question is, of course, how well does it work. There are a couple of subquestions hidden in that, however:
  1. How efficient is it in creating random bits?
  2. How good are the random bits that are created?
For #1, the atomic decay source that I used is not very strong. According to the paper I got with the sample, it is between 500 and 2000 counts per minute which very much makes it a low level radiation source. The MightyOhm provides a serial interface that can be used to read the number of counts per minutes, and it agrees with United Nuclear. Using Method #3 and reading from /dev/gpiorng0 using the dd command I get 3 bytes per second and from watching with the rndctl command the filling of the kernel entropy pool it takes at least 15 minutes to fill up the pool to the maximum 65,536 bits of randomness.

On the whole this is not a very high rate, but is also not unexpected given the rather modest source used.

For #2, I have turned to the dieharder package which is suppose to be able to tell you if a generator is "good" or not. However, it wants a very large number of samples to work with and from reading about dieharder. The practical issue here is that if you only get 3 bytes per second /dev/gpiorngN, using Method #3, you will need a very long time to get the needed amount of random numbers. It will not be practical to use dieharder to test this source.

To get an estimate of the quality of the randomness I simply sampled the raw output and counted the number of 0 bits and the number of 1 bits. These should be nearly to exactly the same. It was discovered that there is some inherent bias in this project, the source of which is not fully understood. It was discovered that overdriving the tube, even a little, seems to produce worse results and adjustments were made to back off the power on the tube, while still keeping the number of events as high as possible given the ore being used.

The NetBSD random pool infrastructure in the kernel has some built in analysis of the pool quality. If allowed to run long enough, it seems to try and give some indication when there might be trouble with the entropy input. It was noticed that if the generator is allowed to run over night, there will be instances where the quality check fails.

Random generation rates
These are the unbiased rate of each method using the ore that I have available
MethodNumber of bytes per second
0Unknown, but appears to be the faster of all
1less than 1
2Around 1
3Around 3
4Around 1, but variable

The use of antibias / unbias algorithms cuts the rate either by 75% or 50% depending on which one is used. But even in the best case, the rate of random number generation is pretty low. The ore source I am using produces around 33 cps, which is low indeed...

Making use of the randomness

Making use of the random number in the places they need to be used is another practical concern. In particular, the problem I have an interest in actually solving is that I have a number of devices that can not generate much random entropy for their pools. In one case, I have cheated a bit and told the system to gather entropy from sources which are known to be suspect. In other cases, I have a belief that the source that is being used is being influenced in a negative way by how it is being used. In particular, in the second case, two of the stratum 1 NTP servers gather entropy from the USB tty port. However, I am not entirely trusting of this source given how the tty port is being used. The WWVB clock exhibits a problem where there is not a large entropy source in the system anywhere and my Xen PV guests do not have a good source either, as is the problem with many virtual guests.

To solve these issues a simple server and client was written in Perl that can read from the TRNG random source and send it over the network to a client in need. To do this safely requires some thought, however:

Even with a pool size of 65536, it is quite possible to exhaust the pool given the rate in which the bits are produced. Right now, the entropy server can handle only about 5 systems, 3 of which are NTP servers running in "peer" mode where random bits are used all of the time. Those three servers ask for bits every 2 minutes. The other two are just modest consumers, asking every 7 or so minutes.

Adding a diode avalanche random number source

With the ore sample I had it was not possible to get enough random numbers, so I built a diode avalanche circuit. There are a lot of articles out there on how to do this:

All of these designs drive the junction of a NPN transistor backwards to generate breakdown voltages that are then amplified and sent to the Raspberry PI. The trick in doing this is to generate noise only from the transistor and not anywhere else, and to make sure that the circuit does not pick up any stray noise from other sources.

I started out trying to build Random Sequence Generator based on Avalanche Noise. I did not have a good source for 13v, but improvised using a MAX232 chip as described in Hardware Random Bit Generator. The behavior was not as expected. It appears that the components I had on hand did not have the same specifications as to what was used in the various projects. In particular:

I was able to get something that seems to resemble avalanche noise if I used 8v plus a bit, but I did not get anything like 250mVpp mentioned in Random Sequence Generator based on Avalanche Noise. And I pretty much saw nothing at the opamps output. So, I built a variation based around the simpler design in Hardware Random Bit Generator.

The design called for 2.7K resister in the feed back for the inverter stages. I ended up changing this out for 27K resister and I added another inverter after the third one. This ended up with an output that went from 0 to 5v in what appeared to be pulses. I sent this to a level converter to get a 3v TTL out that would make the Raspberry PI happy. An earlier attempt at this design omitted the fourth inverter with a resulting signal that was nearly 2.5v. However, there was some transit spikes that went way above 3.3v and probably some amount of negative voltage. I still sent this to the Raspberry PI, but it is likely that I was abusing it.

The pulses could be random??

I also added a small box around the generator made up of the sheet lead I used for the atomic decay generator. This did isolate the generator some and appears to have reduced the amount of junk noise that was being picked up. A number of the designs used PC boards with very short traces and I did not have the ability to use something like that, hence the chances of creating an unintentional antenna was higher for me.

(With the diode generator and the cover on the atomic decay generator)

How well does it work?

As with the atomic decay generator a very real question is how well does it work?

From reading about diode avalanche generators, it was clear that I should expect a fairly high number of events and this appears to be the case. In fact, unless there is throttling in place, the number of events generated will be more than the system can processed by the driver. With the possibility of a large amount of entropy it became important that I actually understand how much entropy was required.

The systems that needed random numbers were are follows:
PurposeHow often is random consumedAsk interval
NTP stratum 1Every few secondsEvery 2 minutes
NTP stratum 1Every few secondsEvery 2 minutes
NTP stratum 1Every few secondsEvery 2 minutes
NTP stratum 2Every minuteEvery 2 minutes
NTP stratum 2 and Kerberos serverEvery minuteEvery 5 minutes
EmailEvery few minutes, couple times an hourEvery 10 minutes
IPsec and OpenVPN end pointEvery few minutes, couple of times an hourEvery 7 minutes
Edge firewallEvery few minutes, couple of times an hourEvery 10 minutes
General purposeEvery few hoursEvery 10 minutes
General purposeEvery few hoursEvery 10 minutes
General purposeEvery few hoursEvery 10 minutes
General purposeEvery few hoursEvery 10 minutes

By far the biggest consumer of random numbers is the Stratum 1 NTP servers. They are in a peering relationship that uses NTP keys with each other and this apparently needs random numbers. The Stratum 2 NTP servers are not in the same sort of relationship with each other and while they use random numbers, they do not consume them at the same rate as the Stratum 1 servers. Most of the rest are rather light users of random numbers and mostly just need them when someone does an ssh into the system, or the system does an ssh out. In the end, if the random number source can provide around 6 to 8 bytes a second, it would be able to keep up with the demands of the client systems, just barely. This all translates to wanting something like 1300 to 1500 random bytes needed every couple of minutes.

The diode avalanche generator appears to be able to generate many thousands of interrupts in a second, but at that rate runs the very real risk of running the system out of memory. The design of a number of the methods used by the device driver is such that it grabs the current time stamp from a fairly high resolution source this number is then put into a queue and passed off to a worker to actually process the time stamp. The queue member takes a certain amount of wired kernel memory and it is entirely possible that the number of events coming in will overwhelm the driver and run the system out of kernel memory if the rate throttle is not set correctly.

A vmstat -i sample:

interrupt                          total   rate
bcm2835 pic (cpu0) gpio[0]    7538137827 152813

I choose to set the rate limiter such that at least 150 bytes a second will be generated using Method 4 and the AMLS algorithm. This provides more than enough entropy to keep the random number pool completely full most of the time.