The Most Random Electronic Dice Yet

di

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.

Comments

  1. w says:

    yada yada … State of sin…. yada yada…

    • planofuji says:

      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.

      • w says:

        In it’s various guises “timer jitter” is best described in most datasheets as “undefined behaviour”. That is no promise of randomness at all.

        • John says:

          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.

          • planofuji says:

            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.

          • Sean says:

            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.

        • planofuji says:

          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.

  2. mh says:

    “This video has been removed by the user”

  3. Greenaum says:

    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.

  4. planofuji says:

    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).

  5. hackliptik says:

    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…

  6. Trav says:

    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.

  7. tekkieneet says:

    Buttons are so yesterday. Should add 3 axis accelerometer as the trigger for “rolling” the dice and as part of the seed.

  8. Edd. says:

    Without question, the scrolling text needs to account for the gap between displays.

  9. Russ says:

    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.

  10. Jean Lesage says:

    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

  11. Galane says:

    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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 96,710 other followers