Hardware Random Number Generator

Posted June 6, 2014 by Ian Kilgore

This page describes the implementation of (Yet Another) avalanche noise hardware random number generator. This is a device which has been implemented many times [e.g. Rob Seward, Aaron Logue], including some commercial offerings [e.g. Entropy Key, TrueRNG]. The goal of this project is not to build something novel or exceed existing specifications. This is an exercise in designing a device beyond the prototype.

Many hobby projects are described affectionately as "hacks" and typically exist at varying levels of technological sophistication, but are typically characterized by low-cost, rapid, jury-rigged design. This is not a value judgment; it is often well-worth stopping at the prototype stage. That's the fun part. The rest is plumbing and, especially in software development, is often the time-consuming, repetitive, and boring part. Still, I thought I should learn some plumbing. My goal was to implement the hack (the first eighty percent), and incrementally improve it into a faster, cleaner, and more compact design (the second and third eighty percents).

A very brief overview of the physics (it is covered adequately elsewhere) is followed by a description of the prototype and my experience with each successive iteration, ending with a note about equipment and a conclusion.

Theory

The need for true random sources is motivated in an overwhelming body of research which reveals systematic human bias when generating or interpreting random data ([1], [2], and [3] are filled with anecdotes and references). Moreover, deterministic psuedo-random algorithms are unsuitable for high-volume or high-security applications such as lotteries [4] and gaming [5], or cryptography.

Random physical sources such as quantum effects (e.g. the action of a photon incident upon a beam splitter), or chaotic systems (e.g. weather) are sampled and conditioned and are thought to provide truly random1) streams.

This paper describes a True Random Number Generator (TRNG) based on avalanche breakdown noise in a PN junction. A PN junction is a semiconductor structure which forms a diode, allowing (ideally) electric current to flow in only one direction. Electric fields internal to the structure support a potential gradient allowing current to flow easily in one direction but creating a potential barrier for electrons driven in the reverse direction.

If strongly reverse-biased, however, electrons which overcome that potential barrier can have sufficient energy to cause impact ionization, leading to a multiplication effect [7]. An energetic electron impacting a silicon atom in the lattice can knock another electron out of the valence band (forming another electron-hole pair). In the presence of a strong reverse-biased electric field (needed to initiate this process in the first place), the liberated electron will accelerate and the process can continue, creating something like a sustained chain reaction.

Laying aside quantum effects and considering electrons in our PN junction to act as a Newtonian gas2, avalanche breakdown is formally a chaotic process: It depends upon strongly nonlinear interactions between a large number of elements3 and exhibits topological mixing (the charge carriers mix throughout the structure and effects are not localized). Chaos means that this system, even if theoretically deterministic (I believe it is not), is highly sensitive to a tremendously large and unknowable set of initial conditions, rendering it unpredictable.

Prototype

The prototype is based upon a design by Will Ware. The physical random source is a reverse-biased PN junction (actually two terminals of a bipolar junction transistor). Part of a transistor is used, rather than a diode, because diodes are typically designed with either very high breakdown voltage (as in the case of rectifying diodes) or low breakdown voltages but with minimal avalanche noise (e.g. zener diodes which are meant to be used in breakdown). A schematic is shown below (click to enlarge).

The PN junction formed by the base and emitter of $T_1$ is reverse-biased by an 18V source (realized by two 9V batteries). The collector is left floating. The output is amplified by common-emitter amplifier $T_3$ and DC coupled through $C_1$ to another common-emitter stage ($T_2$).

I constructed this prototype on perfboard and sampled the output using the ADC on-board an Arduino Uno. After correcting the output distribution using Von Neumann's algorithm, the effective data rate was around 1000 random bits per second, and the device passed the diehard suite of statistical tests.

With a working prototype, I set out to create an integrated PCB, increase the data rate, and add a USB interface (eliminating the Arduino interface)

Iteration 1: PCB 1, power supply

The first iteration adds an 18V supply based on the Texas Instruments TPS61040 DC/DC boost converter designed for LCD and LED display lighting applications. The datasheet contains a reference design (Figure 16, pg. 14) for an 18V output from a 5V supply. This eliminates the (bulky, variable) 9V batteries and allows the design to be powered from USB.

A PCB was created (using the free version of CadSoft EAGLE®) containing the power supply, physics package, and amplifiers. I used surface mount technology (using 0603 passives) and replaced the through-hole 2N3904 transistor from the prototype with the MMBT3904, a surface-mounted equivalent.

The PCB, shown above, was manufactured by Seeed Studio Fusion, a low-cost4 PCB service. It was assembled and tested with the Arduino, with favourable results.

Iteration 2: PCB 2, ADC and LPC1343

Next, I needed a faster interface. After some research I chose to use the LPC1343, a 32-bit ARM Cortex-M3 microprocessor which has a native USB interface and runs at up to 72 MHz. Olimex offers a LPC1343 dev board with published schematics. Using the LPC1343's on-board ADC, I was able to get about a 40x speedup over the Arduino.

I adapted reference USB mass storage code for the LPC1343 and created a virtual mass storage interface for the device (this is not ideal). When inserted, the TRNG enumerates as a mass storage device (e.g. a USB thumbdrive) of arbitrary capacity. It would appear to, e.g. Linux, as a block device. Writes do nothing and return success. Reads return blocks of random data sampled from the noise circuit.

Next, I found the Intersil HI5767/2CBZ, a fast (up to 20 megasamples per second) dedicated 10-bit ADC in a SOIC-28 package. Driving the ADC at the LPC1343's clock frequency (12 MHz) led to an overall speedup of 400x vs the prototype.

I created a SSOIC-28 breakout board using a PCB from Adafruit and built a test circuit for the ADC on perfboard (pictured below), following a reference schematic in the HI5767 datasheet (Figure 19, pg. 13).

The HI5767 has an input dynamic range of no more than 1Vp-p, and I found that removing the second amplifier from the amplifier chain in my physics package reduced the output to within this level. I was able to hack the PCB (pictured below) to achieve this, saving me considerable time.

The test setup, shown below, consists of the Arduino Uno (now providing only a 5V power supply!), the LPC1343 (providing a USB interface), The physics package PCB #1 from above (hacked for 1V output), and my ADC test circuit. It is a mess.

Iteration 3: Integration

Finally, I created a single integrated PCB. I am not an expert, but I attempted to follow some basic rules of mixed-signal design (single sided PCB with large ground pour on reverse, isolating analog and digital circuitry, short clock traces, etc) to avoid contaminating the analog noise source with radiated high-frequency components of the clock or digital outputs. It seems ironic to take measures to protect a noise signal from interference, but we must avoid introducing predictable patterns.

The final schematic, board layout, and images of the completed device are shown below. A PDF copy of the schematic is also available. The final device, after moving the whitening logic to firmware (for completeness sake, but at a significant speed expense), achieved 9 kB/sec random data.

Tools

I used a temperature-controlled soldering station, a hot air rework station, and a boom-mounted stereo inspection microscope (on a low magnification) to assemble and inspect the device, particularly the LPC1343's LQFP48 package. These tools are relatively expensive for the hobbyist (although I have by no means gone to extremes), but are well worth it as they eliminate a significant opportunity cost of time, frustration, and damaged parts.

Conclusion

This design, like many others in its class (including some commercial offerings) is flawed and should not be used by anyone. It is not a differential design and is easily influenced by external fields. Unlike some commercial products, it has no tampering detection or countermeasures, leaving it vulnerable to manipulation.

I am done iterating and there are loose ends I do not intend to clean up. In particular, the USB mass storage interface, while fast, is idiosyncratic and should be replaced by a more suitable type, perhaps USB CDC (?). The board size could be significantly reduced by using 0402 or smaller passives, decreasing spacing between components, and using a 4-layered board. Finally, the whitening logic could be done by a CPLD rather than in firmware, leading to a significant speedup and possibly the elimination of the microcontroller in favour of a specialized USB implementation.

This was for me an interesting exercise in attempting to create a polished product in an amateur setting using amateur tools, techniques, and an amateur mind. I have no doubt that my inexperience led me to make several and important naïve mistakes, but I am satisfied with the result. I hope that I will not be satisfied with it when I look back in two years' time.

Links/misc

Slides from my talk at the NCSU Linux Users' Group

Test output from the dieharder test suite

I may never get around to cleaning and uploading the firmware source code. Anyway, there is nothing relevant to this application. The firmware just implements a USB mass storage device on the LPC1343. Feel free to e-mail me (see the home page) with questions.

While not explicitly referenced, I found these links interesting or useful:

Footnotes

1 Or at least are demonstrably unpredictable. Whether a phenomenon is truly random is, pedantically, a philosophical question.

2 They certainly do not, but there is some question as to whether quantum effects are relevant at this scale, so I am being conservative.

3 A rough-but-conservative estimate of the number of interactions at hand follows, but note that this may still be a gross overestimate of the number of relevant interactions:

I'm likely very far off from the correct answer, but it is at least clear that we are dealing with large numbers.

4 The true cost of services like this is time. Because of the batching process which is typically how PCB manufacturing services are available at the hobbyist price point, and shipping from Hong Kong, it takes about one month to receive a finished PCB. This also means mistakes are very time-costly. I was fortunate enough to make no fatal errors throughout the project. Still, the project was completed over the course of six months of intermittent several-hour sessions.

References

[1] Mlodinow, Leonard. The drunkard's walk: How randomness rules our lives. Random House LLC, 2009.

[2] Silver, Nate. The signal and the noise: Why so many predictions fail-but some don't. Penguin, 2012.

[3] Goldacre, Ben. Bad science: Quacks, hacks, and big pharma flacks. Random House LLC, 2010.

[4] Jabr, Ferris. "Lottery wins come easy, if you can spot the loopholes." NewScientist.com. New Scientist, 19 Aug. 2011. Web. 18 Mar. 2014 http://www.newscientist.com/article/mg21128264.900-lottery-wins-come-easy-if-you-can-spot-the-loopholes.html.

[5] "PokerStars Random Number Generator." PokerStars.com. PokerStars. Web. 18 Mar. 2014 http://www.pokerstars.com/poker/rng/.

[6] Verwey, J.F.; Kramer, R.P.; De Maagt, B.J., "Mean free path of hot electrons at the surface of boron-doped silicon," Journal of Applied Physics, vol.46, no.6, pp.2612,2619, Jun 1975 doi: 10.1063/1.321938

[7] McIntyre, R. J. "Multiplication noise in uniform avalanche diodes." Electron Devices, IEEE Transactions on 13.1 (1966): 164-168.


(c) 2014 Ian Kilgore

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.