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.
- Method #1 - Measure the number of pulses within a fixed time period and set a flip flop to flip with each pulse. The number of pulses within any fixed time period can not be determined and the state of the flip flop a the end of the time interval is the 1 bit of entropy. The interval of time that you must use needs to be at least 10 times the decay rate of the atomic source.
- Method #2 - Measure the length of time between two consecutive pulses and if the length between the first and second is longer then the length between the second and third, the bit is a 1, otherwise if the opposite then it is a 0. If the lengths are the same, ignore the result. This is the algorithm used by the Hotbits site.
- Method #3 - Measure the time between two pulses. If the time mod 2 is odd then the bit is a 1, otherwise if the time mod 2 is even the bit is a 0. This is my favored algorithm because it lets me see the raw bits and is the most event efficient.
- Type 1 - This is the algorithm described by von Neumann and is pretty simple to code. You take two consecutive bits. If they are 0 and 0 or 1 and 1, ignore the result. If they are 0 and 1, the result is 0. If they are 1 and 0 then the result is 1. This works as long as the bits are independent to each other and fails otherwise. For example, running it against the pattern 0101010101010101.
- Type 2 - This algorithm simply xors each consecutive bit together and was used by the Arduino True Random Number Generator project. This will also fail if the input is patterned.
I also implemented a couple of additional methods.
- Method 0 - This method uses the ability of the NetBSD kernel random number generation subsystem to count the time between pulses. It does not try to generate any sort of value.
- Method 4 - This implements the Advanced Multi-Level Strategy or AMLS algorithm as described Generating random binary data from Geiger counters. This technique takes the least significant byte from the difference between two clicks and pivots it around a percentage bias point. Those values less than this point are a 0 and those greater are a 1.
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:
- 6_gpiorng.tar - This adds a driver called gpiorng that will accept a pulse on an input GPIO pin. The various flags and options will determine which pin it will use and which method it will use for the bit derivation. For Methods #2 and #3, it also provides for a /dev/gpiorngN device which can be used to read the bits directly from the algorithm and not have them enter the kernel entropy pool.
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:
- Raspberry PI 3 V1.2 running NetBSD 8.99.3 with the above set of patches plus ones used for the NTP projects.
- A MightyOhm geiger counter kit from MightyOhm.
- A bit of radioactive ore from United Nuclear.
- A small "box" made up of lead sheeting also available from United Nuclear.
- Two "buck" DC-DC converters. One feeds 5V to the Raspberry PI 3 and the other feeds 3V to the geiger counter.
- The DC-DC converters are being fed by a 12V 2amp POE splitter.
(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:
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 4 bytes per second and from watching with the rndctl command the filling of the kernel entropy pool it takes around 15 minutes to fill up the pool to the maximum 65,536 bits of randomness.
- How efficient is it in creating random bits?
- How good are the random bits that are created?
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 4 bytes per second /dev/gpiorngN, using Method #3, you will need a very long time to get the needed amount of random numbers. The work to generate this output is still ongoing and may never be completed with the ore that is being used.
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
|Method||Number of bytes per second
|0||Unknown, but appears to be the faster of all
|1||less than 1
|4||Around 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:
- You do not want to read from the entropy source if it is low, and there is a quirk in the NetBSD /dev/random device where if you read more than 16 bytes at a time you will cause a reseed.
- You do not want to send the random bits over the network unencrypted, otherwise you will defeat any security benefits you get from having a good random source from a crypto point of view. The nasty here is that you would want to avoid or lessen the use of /dev/urandom or /dev/random to do the encryption. It was discovered that the Perl 5 Crypt::CBC module does, in fact, use /dev/urandom get generate random seeds and IVs, so you end up using random numbers to generate the encryption you are trying to use.
- For the Raspberry PI itself that will be getting the random events, it would seem reasonably that only the atomic decay source be used to feed the entropy pool. This is not a great issue to deal with, as the rndctl command can set this very simply. However, if the pool becomes exhausted, there is no fall back and the clients will be starved.
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:
- The MAX232 chip I had would put out only 8.2v and -8.2v instead of the 10v and -10v mentioned in Hardware Random Bit Generator. The specification sheet from the chip maker indicated that my observed specs were correct.
- The 2N3904 transistors I had according to the chip maker have a breakdown voltage of 6v, instead of the 18v or 13v mentioned in a lot of the web sites. In fact from watching the output with my scope I would see noise in the 8v range, and nothing as the voltage was increased into the 10v or more range. I am suspecting that this particular 2N3904 version has some sort of voltage and/or current protection in it.
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.