If you’ve written a great library to generate random numbers with a microcontroller, what’s the first thing you would do? Build an electronic pair of dice, of course.
[Walter] created the entropy library for AVRs for a reliable source of true random numbers. It works by using the watchdog timer’s natural jitter; not fast by any means but most sources of entropy aren’t that fast anyway. By sampling a whole lot of AVR chips and doing a few statistical tests, it turns out this library is actually a pretty good source of randomness, at least as good as a pair of dice.
The circuit itself uses two 8×8 LED matrices from Adafruit, an Arduino, and a pair of buttons. The supported modes are 2d6, 2d4, 2d8, 2d10, 1d12, 1d20, a deck of cards, a single hex number, a single 8-bit binary number, or an eight character alphanumeric password. It’s more than enough for D&D or when you really need an unguessable password. Video demo below.
yada yada … State of sin…. yada yada…
The full quote is “Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin” This device is NOT using arithmetical methods to produce random numbers. It is using timer jitter, which actual testing has shown to be entirely consisten so far with what an ideal true random number generator would produce.
In it’s various guises “timer jitter” is best described in most datasheets as “undefined behaviour”. That is no promise of randomness at all.
Well obviously the companies creating microcontrollers didn’t create the watchdog timer as a source of random entropy. To them, ideally it would have no jitter. But that doesn’t mean it doesn’t have flaws that can be exploited to generate random numbers.
It doesn’t really matter if there’s no promise of randomness. Any source of entropy will need to be tested, and with a few exceptions the entropy lib is pretty damn random.
Actually, Brian those couple of exceptions are actually good ‘proof’ of the basic validity of the mechanism as a TRUE random number source. Unlike the typical PRNG, a TRUE source should have such ‘failures’ in about the frequency we are seeing. Indeed, the few tests that have failed have been continued, and the ‘failures’ go away as more data is collected from the device. Which is precisely what a true random number source should do.
I like random numbers a lot, and when I need to test some source I’m sampling, I use this: http://csrc.nist.gov/groups/ST/toolkit/rng/stats_tests.html
If you run at alpha= 99%, you expect ~1% of blocks of data to fail most tests. You’ll observe some slightly different amount. Run a chi-square test on that. I forget how to do power analysis on a chi square, but that might be useful after.
I recommend 100 megabits of data split into blocks of 1 megabit each as a bare minimum.
The world is replete with sources that claim to promise randomness. Most of which TESTING has shown that they less than fulfill that promise. Further, even if the basic source provides randomness, that is no guarantee the IMPLEMENTATION will fulfill that promise. That is the purpose of my site, to actually show how (and to actually measure how well) those promises might work out in the real world. BTWm the randomness is not simply the jitter associated with the WDT, but rather the combined jitterness between the WDT and the system timer (TMR01). The two have different clock sources, which are why this is working so well. In the case of the ARM chips this has been implemented and studied on, it is two different timers being used, that may even be using the same clock source (I haven’t checked into the details of the three chips yet).
One of the most common mistakes I see is a naive implementation of the random(max) and the random(min,max) functions that make use of the modulus operator. While the modulus operator is the fastest way to perform the calculation, its nature introduces significant bias in the resulting numbers that reduce the resultant randomness considerably.
“This video has been removed by the user”
But the one on the linked article works.
Sorry about that, there was a glitch with the original, so I had to re-upload it. Here is the correct link http://youtu.be/S5YeHWBv0AU
Pretty nice! The idea of using an LED grid gives it much more potential than the traditional electronic dice. I like the alternative modes it has.
+1 – inspired choice of output.
Oh, and the library/approach has been tested on three different types of ARM chips using timer jitter (STM32F103RB, MK20DX128, and the MX20DX256). All three appear to work as well as the AVR chips for this purpose. On the SAM3X8E the library uses the chips hardware-rng (also tested).
I dream of pair’o’, pair’o’, pair’o’dice every time I close my eyes… doo doo dooo doo doo dooo doo doo doo do doo doo dooo doo doo dooo doo doo dooooo…
Pretty cool. A couple differences I would like to see would be a selector switch (or rotary encoder) for the modes instead of the button press. That would make it easier to change die type without having to re-power or loop through all the modes. Second would be to place the displays closer together to make reading passwords easier.
But, those are only personal preferences. I still think it is a great project.
Buttons are so yesterday. Should add 3 axis accelerometer as the trigger for “rolling” the dice and as part of the seed.
Without question, the scrolling text needs to account for the gap between displays.
Also appears to have an off-by-one error, you can see it when a vertical-line (eg a T) crosses the gap, it’s displayed on both displays.
While there are tests to determine that a source of data is *not* random, there is no test to confirm that a data source is random. While its likely that some randomness exists in timer jitter, it very easy to overestimate the amount available without understanding the processes that produce the jitter.
You are exhibiting the traditional laymen’s lack of understanding. If a particular methodology is subjected to extensive testing to determine if their is bias or patterns in its data stream and those tests fail to produce a positive result, we can reasonably be sure that the data is random. Timer jitter has an extensive background in such testing, not just my testing, and it has never been shown to be non-random. Until such evidence is produced that it isn’t random, we can be fairly comfortable in using it as a random source.
SpikenzieLabs sells a dice kit that has a piezo for the random seed. The number to show up on the die is generated by reading the analog voltage to the right of the decimal point, which gets translated into a number 1-6
Have they done (and documented) any testing to indicate if their chosen source is actually random?
no idea, it looks like a fun novelty soldering kit, not intended for pro-gaming I thinks…
Point a video camera at something that’s in constant motion, like a busy street or sidewalk, a cloudy sky or a leafy tree in a breeze. Or a half dozen LavaLite Lamps like SGI did with their LavaRAND project.
Natural chaotic motion, or even linear motion of non-repetitive large objects (such as cars on a road or walking people) is an excellent source of truly random data when the raw video stream is used to periodically sample seeds from for any random number generator.
Cascade the output of the random number generator through one or more additional generators that use different methods and there is not going to be any repeatable pattern.
Are they for sale?