AVR Random Number Generator

Question

I've read an appnote from TI (slaa338) that describes a technique for generating "for real" (as opposed to "pseudo") random numbers. It exploits the somewhat exotic clock subsystem of the MSP430 to achieve this goal. Does anyone know of a technique that can be implemented on an AVR (I'm interested in the XMega's in particular) for generating "for real" random numbers?

Answer 1

How bad do you to use the XMega? If the crypto and random number generation are a big part of your project, Atmel's SecureAVR series has a hardware random number built in, and is designed for cryptographic applications.

Regardless, I doubt that you'll find a random seed source that has a good distribution. You'll want to run it through a pseudo random number generator a few times As long as you start with a different seed every time, this will give you a nice set of random numbers. An LGC is a quick and easy pseudo random generator:

static unsigned long Seed; 

/* Call before first use of NextVal */
unsigned long InitSeed()
{
   //Your code for random seed here

   // Correct distribution errors in seed
   NextVal();
   NextVal();
   NextVal();
   return NextVal();
}

 /* Linear Congruential Generator 
  * Constants from  
  * "Numerical Recipes in C" 
  * by way of 
   * <http://en.wikipedia.org/wiki/Linear_congruential_generator#LCGs_in_common_use>
   * Note: Secure implementations may want to get uncommon/new LCG values
  */
unsigned long NextVal()
{
  Seed=Seed*1664525L+1013904223L;
  return Seed;
} 

Answer 2

Connect up the ADC to a hardware noise source and use software to "whiten" the random numbers if needed.

Here's an AVR-based project that does this: Leon's Mini Portable Random Number Generator (mPRNG)

Depending on how cryptographically secure it needs to be, you could use the noise of a grounded analog input or the "internal temperature sensor" as your randomness seed instead of external hardware.

Update: I later wrote a program for Arduino that uses the chip's timers as an entropy source (the ADC turned out to be useless because the noisy bits are truncated), and this inspired the creation of the Entropy library.

In both cases, the randomness is not from, for instance, the temperature value itself, which only changes slowly, but from the least significant bits, which vary randomly from one read to the next. I read the value multiple times, once for each bit of output, bitshifting and XORing with the previous read. XORing a truly random bit with an uncorrelated bit preserves randomness, so the randomness gets spread around to all the bits and it becomes true white noise. Your bit rate will not be very high, though, since you only get one bit of output per acquisition time or timer cycle. With the timer method, I was getting about 64 bit/s.

Answer 3

Another trick for generating a random seed, is to count the number of clock cycles until an external event. For example if this is a device to be used by a person, count the number of clock cycles until he presses the 'go' button, and use that as the random seed.

Answer 4

To be sure to not restart with the same sequence, I use somme byte in the eeprom :

#include <avr/eeprom.h>
#include <stdlib.h> // rand

u16  EEMEM randinit; 

int main(void) {
        srand(eeprom_read_word(&randinit));
        eeprom_write_word(&randinit,rand());
        [...]
 }

This give quite good random, and does not cost much in programme/memory.

Answer 5

I have created a library that while original designed for the Arduino works well as a class in a C++ implementation using g++ on the avr, indeed it has recently been ported to the ARM architecture as well.

It makes use of the jitter between the watchdog timer and the system clock and has been tested on a number of different chips (documented on the wiki page)

http://code.google.com/p/avr-hardware-random-number-generation/wiki/WikiAVRentropy

Answer 6

Have you looked at using something like randomSeed()? - used in the Arduino IDE

You can use this function to sample a floating (free) analog pin on the atmel AVR, it then uses the value to create an arbitrary starting point for the pseudo random number function - random().

The value created by random() may be a pseudo random number - but the arbitrary starting point created by randomSeed() should be as real a random number/value as you can get.

Answer 7

There is a paper on how to achieve this with AVR hardware. It involves relying on clock jitter. Basically, you use a timer interrupt based off of one clock source to sample the lower bits of a separate timer which is clocked off a separate independent clock source. The two clocks will have some random jitter associated with them and the sampling will not be perfectly periodic.

I did a small proof of concept of this on an STM32 microcontroller, code is on github here. It got some good results based on a set of randomization test suites.

In my opinion, I think this is better than sampling a floating pin with an ADC which is extremely easy to attack (tie the pin to ground and your number isn't so random anymore!). I'm sure there's a way to manipulate a clock jitter based RNG, but it makes me feel a little bit better that I can do this purely based off of on-chip internal clock sources.