12
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ psuedo random works for dice games. I think he wants cryptographically secure. \$\endgroup\$ – Kortuk Jul 21 '10 at 19:19
  • 2
    \$\begingroup\$ Can you give a hint as to the application and/or the degree of randomness that you require? If it's for cryptography, there are additional considerations besides just the seed quality. Some of the suggestions already made-- like sampling environmental inputs of various types may or may not be appropriate based on your requirements. \$\endgroup\$ – Windell Oskay Jul 22 '10 at 6:08
6
\$\begingroup\$

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;
} 
\$\endgroup\$
  • 1
    \$\begingroup\$ Thatis awesome, I didn't realize the SecureAVR line existed, thanks for the pointer! \$\endgroup\$ – vicatcu Jul 22 '10 at 15:12
  • \$\begingroup\$ BTW: If you REALLY need security, the simple, effective, and fast LCG method I presented isn't what you want: Many LCGs can be broken; just get 2-3 values in a row, and plug them into an LCG generator with a set of known constants - this would include everything on the Wikipedia page. A matching pattern will let the attacker predict what the next number will be. It's possible (but harder) to figure out what the constants are from nothing, as well. \$\endgroup\$ – Kevin Vermeer Jul 22 '10 at 15:41
  • 1
    \$\begingroup\$ @reemrevnivek FYI, Atmel is selling off their SecureAVR line... they recommend their ARM-based 32-bit processors if you want cryptographic stuff which is a whole different ballgame in terms of development environment from AVR. They do have a couple with True RNGs on them though, maybe I'll play with them some day. \$\endgroup\$ – vicatcu Aug 5 '10 at 21:24
7
\$\begingroup\$

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.

\$\endgroup\$
  • 5
    \$\begingroup\$ Naming a (more or less true) RNG, "-PRNG" is unfortunate. \$\endgroup\$ – Nick T Dec 2 '10 at 0:54
  • \$\begingroup\$ +1 for ADC, I would think you're probably looking for something that changes at a higher frequency than a temperature sensor though. \$\endgroup\$ – Octopus Dec 17 '15 at 17:17
  • 1
    \$\begingroup\$ @Octopus Well you're not using the temperature as the entropy source, you're using the noisy least significant bits, which will change randomly every time you read the ADC even if the temperature is constant. When I tested on Arduino, though, these bits were always 0, so it wasn't feasible and I had to use timer variation instead. On another MCU I used that method on, the LSBs of the ADC were noisy and usable. \$\endgroup\$ – endolith Dec 17 '15 at 17:22
3
\$\begingroup\$

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.

\$\endgroup\$
  • 4
    \$\begingroup\$ This may not be very secure against side channel attacks as they can break in by securing control of one device, but as with all cryptography, application determines feasibility. \$\endgroup\$ – Kortuk Jul 21 '10 at 19:20
3
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ This reads byte 0 every time. What evidence do you have that this byte is random? If it is, this is a great technique! \$\endgroup\$ – Kevin Vermeer Jul 23 '10 at 1:19
  • \$\begingroup\$ This word (byte 0 & 1 in fact) will be random, because at each startup I initialise the random generator with it's content. THEN I upload it with a new rand(). So the next init will look random from the current one... and so on... But if I reset randinit to ffff (or 0000?), I will have the same randinit sequence! So it's not perfect. I forgot a warning about the fuse who erase the eeprom when uploading the *.hex ;) \$\endgroup\$ – jojo l'abricot Jul 23 '10 at 19:57
3
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ Sampling things like the analog pins is close to random, but will not have an even distribution. Run the seed through random a couple times, however, and it will. \$\endgroup\$ – Kevin Vermeer Jul 22 '10 at 3:34
  • \$\begingroup\$ ....through a pseudo random number generator a couple... <- How did that go missing? NTS: Engage brain first, then fingers. \$\endgroup\$ – Kevin Vermeer Jul 22 '10 at 10:06
  • \$\begingroup\$ Exactly - It's also not the most secure if using it for encryption / protection etc, but it will give you a nice random number for something like generative music or dice games. It's good and easy to implement too :) \$\endgroup\$ – Jim Jul 22 '10 at 10:17
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.