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.

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 94,080 other followers