Introduction: Mouse Trap Entropy Engine
This instructable demonstrates how to extract truly random numbers from an ordinary optical mouse and Christmas bubble lights. The process is explained in detail further on, but the short overview is that a Christmas bubble light generates boiling bubbles, the bubbles are detected by an optical mouse as mouse movements, the mouse movements are measured and recorded by software to gather entropy, the movement values are filtered by the entropy gathering software to remove non-random bias, and the filtered values are finally output to be used as a source of truly random numbers.
As a hardware random number generator, the Mouse Trap Entropy Engine isn't very fast, only 6 B/s (that's six bytes per second), but it looks really nice and adds a warm, festive glow to an otherwise dull, drab computing facility. These videos show several entropy modules from a Mouse Trap Entropy Engine mounted in a standard 19" server rack, happily bubbling away with unbridled entropy.
http://www.youtube.com/watch?v=Yf4M3QeSdmA&hd=1
http://www.youtube.com/watch?v=P9OMS2A_75w&hd=1
As a hardware random number generator, the Mouse Trap Entropy Engine isn't very fast, only 6 B/s (that's six bytes per second), but it looks really nice and adds a warm, festive glow to an otherwise dull, drab computing facility. These videos show several entropy modules from a Mouse Trap Entropy Engine mounted in a standard 19" server rack, happily bubbling away with unbridled entropy.
http://www.youtube.com/watch?v=Yf4M3QeSdmA&hd=1
http://www.youtube.com/watch?v=P9OMS2A_75w&hd=1
Step 1: Entropy Generation Overview -- Where Random Numbers Come From
Random numbers in computers are usually generated using a Pseudo-Random Number Generator algorithm (PRNG). A PRNG is like a blender for numbers that mixes them together in complex ways to yield a sequence that appears random. The mixer needs a number to start with called a seed. For a given seed the PRNG will always generate the same sequence of pseudo-random numbers. The problem is that this makes a PRNG completely predictable, which isn't what you usually want from a random number, but if you use a truly random number to seed a PRNG then the resulting sequence is unpredictable and nearly indistinguishable from a sequence of truly random numbers. The trick is obtaining a truly random number to use as a seed for a PRNG.
Many operating systems maintain a source of random numbers called an 'entropy pool'. These numbers are truly random, not pseudo-random. A process dedicated to gathering entropy slowly fills the pool by recording the activity of hardware that is unpredictable. Some sources include the time between key strokes, time and distance between mouse movements, timing of the motion of a hard disk head, and noise from a microphone or video camera. All this activity is mixed and filtered to yield a truly random number which is added to the entropy pool for storage until consumed by any program that requires truly random numbers. The random numbers may be consumed and used directly from the pool, but this can be wasteful. The pool is a limited resource which is slow to refill. If all numbers in the pool are consumed then subsequent requests will be forced to stop and wait until entropy gathering process refills the pool. To conserve the pool only a few numbers may be taken and used as a seed to a PRNG, which can then generate far more numbers than the entropy pool can provide. And because the seed to the PRNG is truly random, the resulting sequence is nearly indistinguishable from truly random numbers (for most purposes).
The demand for truly random numbers on some systems is greater than what a slow entropy gathering process can provide. This has lead to the development of entropy generation hardware dedicated to quickly generating truly random numbers. These devices usually work by recording noise from thermal, electrical, or radio sources. It isn't difficult to build a hardware entropy generator. Many of them are quite simple, but the one I built here, which is based on an optical mouse and Christmas bubble lights, is not one of them. It also isn't fast, but it looks great mounted in a server rack.
Many operating systems maintain a source of random numbers called an 'entropy pool'. These numbers are truly random, not pseudo-random. A process dedicated to gathering entropy slowly fills the pool by recording the activity of hardware that is unpredictable. Some sources include the time between key strokes, time and distance between mouse movements, timing of the motion of a hard disk head, and noise from a microphone or video camera. All this activity is mixed and filtered to yield a truly random number which is added to the entropy pool for storage until consumed by any program that requires truly random numbers. The random numbers may be consumed and used directly from the pool, but this can be wasteful. The pool is a limited resource which is slow to refill. If all numbers in the pool are consumed then subsequent requests will be forced to stop and wait until entropy gathering process refills the pool. To conserve the pool only a few numbers may be taken and used as a seed to a PRNG, which can then generate far more numbers than the entropy pool can provide. And because the seed to the PRNG is truly random, the resulting sequence is nearly indistinguishable from truly random numbers (for most purposes).
The demand for truly random numbers on some systems is greater than what a slow entropy gathering process can provide. This has lead to the development of entropy generation hardware dedicated to quickly generating truly random numbers. These devices usually work by recording noise from thermal, electrical, or radio sources. It isn't difficult to build a hardware entropy generator. Many of them are quite simple, but the one I built here, which is based on an optical mouse and Christmas bubble lights, is not one of them. It also isn't fast, but it looks great mounted in a server rack.
Step 2: The Mouse Trap Entropy Engine Overview
Most mice today are optical; they actually have a tiny video camera on the bottom that is used to watch a surface move under the mouse. Many optical mice can be modified to watch other things move. I found that Christmas bubble lights make bubbles that are easily seen by many mice. Few will argue that the bubbles in a boiling fluid are a bad source of entropy.
All sources of entropy have some bias. The motion of the bubbles in a bubble light have a bias because the bubbles always move in the same direction, but this bias is easy to filter out. There may be other patterns of bias which may not be so obvious, but luckily the bias filter doesn't need any sort adjustment to address specific forms of bias. It will handle almost any bias. Imagine flipping a coin to generate random sequences. Now imagine the coin was weighted so it was heavier on one side. The coin tosses would still be random and unpredictable, but one side would tend to come up more often. Imagine trying to use this coin to bet which side would come up next. You could make the game fair by adjusting the payout to compensate for the skewed odds, but that would require that you make a detailed statistical model to estimate the bias. An alternate way would be to use a bias filter, which does not require foreknowledge of how a system is biased. Simple bias filters are not perfect. They can't force truly random numbers from a stream which is deliberately engineered to fool the filter. But assuming the input stream is truly random with only some "honest" bias then a bias filter works very well and is simple to use. The bias filter I use is called a von Neumann decorrelation filter. It is easy to implement in software.
All sources of entropy have some bias. The motion of the bubbles in a bubble light have a bias because the bubbles always move in the same direction, but this bias is easy to filter out. There may be other patterns of bias which may not be so obvious, but luckily the bias filter doesn't need any sort adjustment to address specific forms of bias. It will handle almost any bias. Imagine flipping a coin to generate random sequences. Now imagine the coin was weighted so it was heavier on one side. The coin tosses would still be random and unpredictable, but one side would tend to come up more often. Imagine trying to use this coin to bet which side would come up next. You could make the game fair by adjusting the payout to compensate for the skewed odds, but that would require that you make a detailed statistical model to estimate the bias. An alternate way would be to use a bias filter, which does not require foreknowledge of how a system is biased. Simple bias filters are not perfect. They can't force truly random numbers from a stream which is deliberately engineered to fool the filter. But assuming the input stream is truly random with only some "honest" bias then a bias filter works very well and is simple to use. The bias filter I use is called a von Neumann decorrelation filter. It is easy to implement in software.
Step 3: Parts -- the Key Components of the Entropy Engine
The Mouse Trap Entropy Engine is made up of a Central Processing Unit, software to collect entropy, and at least one Entropy Module (a bubble light and a mouse). The CPU may be any computer with a USB port. The entropy collection software is written in Python and is intended for Linux operating systems; although it may not be hard to port to other operating systems.
A cheap mouse is just as good as an expensive mouse. Not all mice work, so you may have to test a few different models to find one that works. I found that the Microsoft Compact Optical Mouse 500 v2.0 works well. It is cheap, easy to find, and easy to disassemble. To test a mouse you simply remove the sensor board from the mouse body, remove the prism and lens, plug the mouse into a computer, and then hold the sensor up to a bubble light. If the cursor on the screen wiggles and dances around then the mouse sensor is acceptable.
Bubble lights typically use a screw socket known as a candelabra socket. Candelabra socket fittings are a smaller version of the the common Edison screw socket fitting. The the candelabra socket is usually wired to a 120 VAC power supply. Bubble lights are available in many colors. A mouse optical sensor probably favors red light, but I have not tested green and blue bubble lights to say if it reallymatters. I have tested only red and yellow bubble lights.
The entropy collection software was written in Python for the Linux operating system. It is available on GitHub:
https://github.com/noahspurrier/mtee
See also my personal notes on this project here:
http://www.noah.org/wiki/Mouse_Trap_Bubble_Light_Entropy_Engine
Summary of parts:
A cheap mouse is just as good as an expensive mouse. Not all mice work, so you may have to test a few different models to find one that works. I found that the Microsoft Compact Optical Mouse 500 v2.0 works well. It is cheap, easy to find, and easy to disassemble. To test a mouse you simply remove the sensor board from the mouse body, remove the prism and lens, plug the mouse into a computer, and then hold the sensor up to a bubble light. If the cursor on the screen wiggles and dances around then the mouse sensor is acceptable.
Bubble lights typically use a screw socket known as a candelabra socket. Candelabra socket fittings are a smaller version of the the common Edison screw socket fitting. The the candelabra socket is usually wired to a 120 VAC power supply. Bubble lights are available in many colors. A mouse optical sensor probably favors red light, but I have not tested green and blue bubble lights to say if it reallymatters. I have tested only red and yellow bubble lights.
The entropy collection software was written in Python for the Linux operating system. It is available on GitHub:
https://github.com/noahspurrier/mtee
See also my personal notes on this project here:
http://www.noah.org/wiki/Mouse_Trap_Bubble_Light_Entropy_Engine
Summary of parts:
- A computer with a USB port
- Linux Operating System
- Python
- USB optical mouse
- Bubble light
- 120 VAC candelabra socket
Step 4: Disassemble a Mouse
The screws in most mice are under nylon sliders or under stickers. Some mice are also held together by snap tabs. The mouse I used has only one screw under a sticker. You can throw away the prism and lens assembly, the scroll wheel, and the case.
Step 5: Assemble a Bubble Module
Each Entropy Module is assembled quite easily. The photos show how to wire up a simple 120 VAC power supply. Observe standard precautions when working with dangerous electricity. When the Entropy Module is finished it should operate like this:
Step 6: Attach Mouse Sensor to Bubble Module
I use a black elastic band to hold the mouse sensor to the bubble light. The mouse sensor has a small pinhole opening. This pinhole is placed against the glass of the bubble light. The motion of the bubbles is interpreted as movement by the mouse. If you plugged the mouse into a computer you would see the cursor on the screen wiggle around randomly.
Step 7: Attach Entropy Module to CPU and Start Entropy Collection Software
I won't go into too much detail here, since this project is rather silly and I don't expect many people to actually use one of these. If there is more interest or questions on using the software then I will expand this section. The software is somewhat documented.
Once the entropy module is plugged into a computer and the bubble light is turned on it will take a few minutes for the light to warm up and for the bubbles to start. When the bubbles start you should hopefully see your mouse pointer begin to wiggle around the screen. This will quickly become annoying so unplug the mouse. The Mouse Trap Entropy Engine software includes instructions for identifying and disabling a mouse. Use the '--detect' option to identify the device name of your mouse. Then use the 'xinput' command to disable the mouse. This will only disable it from moving the mouse cursor. It will still be visible by the system.
The 'entropy-source' script is the main script your need to run. Start it with a given mouse device name and it will begin output random bytes.
Once the entropy module is plugged into a computer and the bubble light is turned on it will take a few minutes for the light to warm up and for the bubbles to start. When the bubbles start you should hopefully see your mouse pointer begin to wiggle around the screen. This will quickly become annoying so unplug the mouse. The Mouse Trap Entropy Engine software includes instructions for identifying and disabling a mouse. Use the '--detect' option to identify the device name of your mouse. Then use the 'xinput' command to disable the mouse. This will only disable it from moving the mouse cursor. It will still be visible by the system.
The 'entropy-source' script is the main script your need to run. Start it with a given mouse device name and it will begin output random bytes.
$ sudo ./entropy-source /dev/input/event4 | od -x
0000000 0bbd b360 4887 5b06 213e 53e3 becc bd08
0000020 4552 056f 6698 be45 2e67 f78a 43b1 44ee
0000000 0bbd b360 4887 5b06 213e 53e3 becc bd08
0000020 4552 056f 6698 be45 2e67 f78a 43b1 44ee
Step 8: Industrial Installation
This shows the Mouse Trap Entropy Engine installed in a standard 19" four post rack.
Step 9: Testing and Performance
The Mouse Trap Entropy Engine has had a dataset it generated of at least 12MB tested for quality of randomness. The dataset passes FIPS 140-2 and it performs well on the Dieharder test suite. The system has also been registered and tested with the CAcert Research Lab Random Number Generator Analyzer . Improvements could be made in the internal mixing and bias filtering. The internal bitstream could be fed into a spool prior to final output. The spool would be used to build blocks which are tested against a statistical suite such as FIPS 140-2. Blocks that do not meet a statistical standard would be rejected before output... Overall, the test results are decent, but not outstanding.
The Mouse Trap Entropy Engine software has built-in performance monitoring. It will report the number of random bytes per second output by the system. The average performance with 1 entropy module installed is about 6 Bytes per second. The software currently does not make full use of all available entropy, so it should be easy to increase performance by at least a factor of 3. The output performance is also highly dependent on the position of the mouse optical sensor. Sometimes moving it away from the surface of the glass bubble tube will greatly increase performance. This can be done with a cardboard shim between the bubble tube and the mouse sensor... Overall, the performance of the Mouse Trap Entropy Engine when compared to other hardware random number generators could best be classified as "abysmally low".
The Mouse Trap Entropy Engine software has built-in performance monitoring. It will report the number of random bytes per second output by the system. The average performance with 1 entropy module installed is about 6 Bytes per second. The software currently does not make full use of all available entropy, so it should be easy to increase performance by at least a factor of 3. The output performance is also highly dependent on the position of the mouse optical sensor. Sometimes moving it away from the surface of the glass bubble tube will greatly increase performance. This can be done with a cardboard shim between the bubble tube and the mouse sensor... Overall, the performance of the Mouse Trap Entropy Engine when compared to other hardware random number generators could best be classified as "abysmally low".