Entropy And The Arduino: When Clock Jitter Is Useful

January 8, 2018 by Jenny List 37 Comments

What do you do, when you need a random number in your programming? The chances are that you reach for your environment’s function to do the job, usually something like rand() or similar. This returns the required number, and you go happily on your way.

A shift register configured as a pseudo-random number generator. — A shift register configured as a pseudo-random
number generator. [by KCAuXy4p CC0 1.0]

Except of course the reality isn’t quite that simple, and as many of you will know it all comes down to the level of randomness that you require. The simplest way to generate a random number in software is through a pseudo-random number generator, or PRNG. If you prefer to think in hardware terms, the most elementary PRNG is a shift register with a feedback loop from two of its cells through an XOR gate. While it provides a steady stream of bits it suffers from the fatal flaw that the stream is an endlessly repeating sequence rather than truly random. A PRNG is random enough to provide a level of chance in a computer game, but that predictability would make it entirely unsuitable to be used in cryptographic security for a financial transaction.

There is a handy way to deal with the PRNG predictability problem, and it lies in ensuring that its random number generation starts at a random point. Imagine the shift register in the previous paragraph being initialised with a random number rather than a string of zeros. This random point is referred to as the seed, and if a PRNG algorithm can be started with a seed derived from a truly unpredictable source, then its output becomes no longer predictable.

Selecting Unpredictable Seeds

Computer systems that use a PRNG will therefore often have some form of seed() function alongside their rand() function. Sometimes this will take a number as an argument allowing the user to provide their own random number, at other times they will take a random number from some source of their own. The Sinclair 8-bit home computers for example took their seed from a count of the number of TV frames since switch-on.

The not-very-random result of a thousand analogRead() calls.

The Arduino Uno has a random() function that returns a random number from a PRNG, and as you might expect it also has a randomSeed() function to ensure that the PRNG is seeded with something that will underpin its randomness. All well and good, you might think, but sadly the Atmel processor on which it depends has no hardware entropy source from which to derive that seed. The user is left to search for a random number of their own, and sadly as we were alerted by a Twitter conversation between @scanlime and @cybergibbons, this is the point at which matters start to go awry. The documentation for randomSeed() suggests reading the random noise on an unused pin via analogRead(), and using that figure does not return anything like the required level of entropy. A very quick test using the Arduino Graph example yields a stream of readings from a pin, and aggregating several thousand of them into a spreadsheet shows an extremely narrow distribution. Clearly a better source is called for.

Noisy Hardware or a Jittery Clock

As a slightly old-school electronic engineer, my thoughts turn straight to a piece of hardware. Source a nice and noisy germanium diode, give it a couple of op-amps to amplify and filter the noise before feeding it to that Arduino pin. Maybe you were thinking about radioactive decay and Geiger counters at that point, or even bouncing balls. Unfortunately though, even if they scratch the urge to make an interesting piece of engineering, these pieces of hardware run the risk of becoming overcomplex and perhaps a bit messy.

The significantly more random result of a thousand Arduino Entropy Library calls.

The best of the suggestions in the Twitter thread brings us to the Arduino Entropy Library, which uses jitter in the microcontroller clock to generate truly random numbers that can be used as seeds. Lifting code from the library’s random number example gave us a continuous stream of numbers, and taking a thousand of them for the same spreadsheet treatment shows a much more even distribution. The library performs as it should, though it should be noted that it’s not a particularly fast way to generate a random number.

So should you ever need a truly random number in your Arduino sketch rather than one that appears random enough for some purposes, you now know that you can safely disregard the documentation for a random seed and use the entropy library instead. Of course this comes at the expense of adding an extra library to the overhead of your sketch, but if space is at a premium you still have the option of some form of hardware noise generator. Meanwhile perhaps it is time for the Arduino folks to re-appraise their documentation.

The subject of entropy and generating random numbers is one that has appeared on these pages many times. [Voja Antonic] made a in-depth study using uninitialized RAM as an entropy source for microcontrollers. If you have an insatiable appetite for understanding Linux entropy, we point you at [Elliot Williams]’ comprehensive examination of the subject.

[Arduino image: DustyDingo Public domain]

What Is Entropy And How Do I Get More Of It?

November 2, 2017 by Elliot Williams 55 Comments

Let’s start off with one of my favorite quotes from John von Neumann: “Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin. For, as has been pointed out several times, there is no such thing as a random number — there are only methods to produce random numbers, and a strict arithmetic procedure of course is not such a method.”

What von Neumann is getting at is that the “pseudo” in pseudorandom number generator (PRNG) is really a synonym for “not at all”. Granted, if you come in the middle of a good PRNG sequence, guessing the next number is nearly impossible. But if you know, or can guess, the seed that started the PRNG off, you know all past and future values nearly instantly; it’s a purely deterministic mathematical function. This shouldn’t be taken as a rant against PRNGs, but merely as a reminder that when you use one, the un-guessability of the numbers that it spits out is only as un-guessable as the seed. And while “un-guessability” isn’t a well-defined mathematical concept, or even a real word, entropy is.

That’s why entropy matters to you. Almost anything that your computer wants to keep secret will require the generation of a secret random number at some point, and any series of “random” numbers that a computer generates will have only as much entropy, and thus un-guessability, as the seed used. So how does a computer, a deterministic machine, harvest entropy for that seed in the first place? And how can you make sure you’ve got enough? And did you know that your Raspberry Pi can be turned into a heavy-duty source of entropy? Read on!

Continue reading “What Is Entropy And How Do I Get More Of It?” →

DIY Ram Pump Obeys The Laws Of Physics

June 7, 2017 by Dan Maloney 45 Comments

Despite the claims of “free energy” on the title of the video below, this is not yet another wacky perpetual motion story. We here at Hackaday fully support the laws of thermodynamics, and we think you should too. But you have to admit that a pump that works without any apparent energy inputs looks kind of shady at first glance.

The apparatus in question is a ram pump, a technology dating back all the way to the 18th century. The version that [Junkyard – Origin of Creativity] built uses commonly available materials like PVC pipes and fittings. About the only things on the BOM that might be hard to scratch up are the brass check valves, which should probably be flap valves rather than the easier to find spring valves. And the only custom part is an adapter to thread the plastic soda bottle that’s used as an air chamber to the PVC, which a 3D printer could take care of if you choose not to hack a bottle cap like [Junkyard] did. The video below shows the impressive lift achieved just by tapping the kinetic energy of the incoming flow.

There, the Second Law of Thermodynamics remains inviolate. But if you still think you can get something for nothing, check out our roundup of perpetual motion and Overunity quackery.

Continue reading “DIY Ram Pump Obeys The Laws Of Physics” →

Dual-mode Avalanche And RF Random Number Generator

October 31, 2014 by Ethan Zonca 28 Comments

[Paul] designed a new open-hardware RNG (random number generator) that includes two sources of entropy in a small package. The first source of entropy is a typical avalanche diode circuit, which is formed by a pair of transistors. This circuit creates high-speed random pulses which are sampled by the onboard microcontroller.

What makes this design unique is a second entropy source: a CC2531 RF receiver. The RF receiver continuously skips around channels in the 2.5Ghz band and measures the RF signal level. The least-significant bit of the signal level is captured and used as a source of entropy. The firmware can be configured to use either source of entropy individually, or to combine both. The firmware also supports optionally whitening the entropy byte stream, which evens out the number of 1’s and 0’s without reducing entropy.

The OneRNG uses the USB-CDC profile, so it shows up as a virtual serial port in most modern operating systems. With the rngd daemon and a bit of configuration, the OneRNG can feed the system entropy source in Linux. [Paul] also has a good writeup about the theory behind the entropy generator which includes images of his schematic. Firmware, drivers, and hardware design files are open-source and are available for download.

The Most Random Electronic Dice Yet

May 24, 2014 by Brian Benchoff 26 Comments

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.

Continue reading “The Most Random Electronic Dice Yet” →

Improved Hourglass Entropy

January 25, 2013 by Mike Szczys 16 Comments

improved-hour-glass-entropy

[Wardy] built himself a high quality entropy source with parts he had lying around. It’s based on the hourglass entropy project we saw in a links post earlier this month. Just like that project, he is bouncing a laser off of the falling sand and reading the result. But he brings a few innovations to the party, and has test results to back up his work.

The first change is an obvious one; motorize the hourglass so that you don’t need to flip it by hand. We thought this might mess with the laser alignment but the clip after the break proved us wrong. He changed up the sensor, using an LED connected to the base of an NPN transistor. The next change was to mount the light sensor at an angle to the laser rather than straight on. This picks up reflections of the laser and not the direct beam itself, resulting in a wider range of readings.

He used an Ethernet shield to get the system on the network. It’s pushing 420k random numbers per second and was tested with the DieHarder suite. It didn’t get a very high score, but it did pass the test.

Continue reading “Improved Hourglass Entropy” →

Hackaday Links: January 17th, 2013

January 17, 2013 by Mike Szczys 17 Comments

Free-formed VFD clock

links-free-formed-vfd-clock [James] doesn’t need a circuit board or even some protoboard to get the job done. He free-formed all the circuits for his VFD clock. Right now this is the only project hosted on his blog so click around to see how he got to this point.

DIY LED traffic light

links-diy-traffic-light

Here’s a scratch-build traffic light which [Jarle] uses to display information about his server. If you’re unable to find your own storm damaged original this is a pretty easy way to build one.

FPGA space attack game

links-classic-shooter-running-on-fpga

This game is running on an FPGA, but it’s not written in HDL. Instead, [Johan] wrote the game in C to run on a soft processor loaded on the gate array.

Hourglass entropy

links-hour-glass-entropy

This is a fascinating idea for generating random numbers. [Gijs] is shining a laser onto a light dependent transistor. The beam of the laser is broken by the falling sand of an hourglass. This technique could be use as an entropy source for random number generation.

GPS clock source for a digital timepiece

It seems like massive overkill, but you can’t beat the time accuracy of using a GPS module as a clock source. We don’t expect that [Jay] kept the clock in one piece after finishing the project. It’s just a good way to practice decoding the GPS data.