[MAN][HARD][SOFT] Random Number Generation

Log in or register to post comments
Go To Last Post
21 posts / 0 new
Author
Message
S-Sohn
S-Sohn's picture
Level: Posting Freak
Joined: Sun. Aug 22, 2004
Posts: 1612 View posts
Location: Germany
#1
Posted by S-Sohn: Mon. Feb 4, 2008 - 12:21 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

A very busy semester has passed. One of the reasons why it was so busy was my work on the article
Stochastic processes in embedded systems – Random number generation
I did this work as course work at university.

Several possibilities to generate true random numbers (no PRNG) with an ATmega164P were tested by me. I think the results look promising. Some methods are already known - others are based on my own ideas. However, every single line was written by me. Look at the attached files for details.

Note: You must be logged in to download the files.

Regards
Sebastian

Attachment(s): 

Package icon Sourcecode.zip

Tags:

Learning and Information, Tutorials, ATmega16, ATmega164P
Last Edited: Sun. Feb 24, 2008 - 06:12 PM
Top
S-Sohn
S-Sohn's picture
Level: Posting Freak
Joined: Sun. Aug 22, 2004
Posts: 1612 View posts
Location: Germany
Posted by S-Sohn: Tue. Feb 5, 2008 - 08:09 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

My english is improvable.
Maybe a native english speaker is so kind and makes a review of the pdf file.
If neccessary I'll send this article in doc format.
Many thanks!

Regards
Sebastian

Top
stu_san
stu_san's picture
Level: Raving Lunatic
Joined: Fri. Dec 30, 2005
Posts: 2321 View posts
Location: Fort Collins, CO USA
Posted by stu_san: Wed. Feb 6, 2008 - 09:59 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I've taken the PDF and attached some quick text suggestions and comments. Feel free to accept or ignore what you like.

I used Adobe 8 Acrobat to make the changes, you may need Adobe 8 Reader to see them.

Nice paper - a lot of work!

Stu

Edit 1: Removed the PDF, as Sebastian has an updated version with my changes in it.

Engineering seems to boil down to: Cheap. Fast. Good. Choose two. Sometimes choose only one.

Newbie? Be sure to read the thread Newbie? Start here!

Last Edited: Mon. Feb 18, 2008 - 10:36 PM
Top
S-Sohn
S-Sohn's picture
Level: Posting Freak
Joined: Sun. Aug 22, 2004
Posts: 1612 View posts
Location: Germany
Posted by S-Sohn: Thu. Feb 7, 2008 - 11:22 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Great! Many thanks Stu!
Your comments are visible in the foxit reader, too.
I will update the PDF file next week after I have finished my exams.

Phew, my english is really improvable. Maybe I can visit an english course next semester.
Thanks again!

Regards
Sebastian

Top
S-Sohn
S-Sohn's picture
Level: Posting Freak
Joined: Sun. Aug 22, 2004
Posts: 1612 View posts
Location: Germany
Posted by S-Sohn: Mon. Feb 18, 2008 - 02:03 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I've uploaded a corrected version of the pdf file. Thank you Stu for your great and valuable help.

Regards
Sebastian

Top
RickB
RickB's picture
Level: Posting Freak
Joined: Sun. Jan 30, 2005
Posts: 1347 View posts
Location: Junction City, OR USA
Posted by RickB: Wed. Mar 5, 2008 - 04:21 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

S-Sohn:

Have you thought about analyzing the contents of ram after power on, to see if the random pattern changes between successive power on cycles?

Rick

Top
S-Sohn
S-Sohn's picture
Level: Posting Freak
Joined: Sun. Aug 22, 2004
Posts: 1612 View posts
Location: Germany
Posted by S-Sohn: Wed. Mar 5, 2008 - 04:49 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

No, I haven't. But I wouldn't expect too much from this method. Here's a quote from Atmel's white paper Innovative Techniques for Extremely Low Power Consumption:

Quote:
While in sleep mode, the only critical parameters to handle are the RAM and register contents. On AVR microcontrollers these contents are valid until ~0.3V Vcc, while the AVR’s Power-on Reset (POR) triggers at ~1.0V. If a power supply voltage drop should occur while in sleep mode with the BOD disabled, the SRAM and register contents will be valid until a POR occurs. A POR will enable the BOD again and set the POR flag to be read by the application firmware.
So, the content of the SRAM is guaranteed to stay unchanged down to a supply voltage of 0.3V. But there is no guarantee that the SRAM content will change below this voltage. I guess a short low voltage spike might not change the SRAM content and you usually don't know how long the power supply was off. The Power-On reset is triggered at a voltage of 1.0V. So there is no chance for the controller to determine if the supply voltage really dropped below the 0.3V limit.

Regards
Sebastian

Top
RickB
RickB's picture
Level: Posting Freak
Joined: Sun. Jan 30, 2005
Posts: 1347 View posts
Location: Junction City, OR USA
Posted by RickB: Thu. Mar 6, 2008 - 06:46 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Actually I am refering to a situation where the power has been off for period of time sufficient for the ps to drop to zero and ram contents to become uniform. I am not suggesting that the contents of ram would form the basis of a rng, but only does the contents change between power on cycles with enough variation to be used as a seed for a prng, perhaps using a check sum type of accumulation. It may well be that imbalances in each cell will cause each cell to consistently come up in its prefered state at power on, rendering this idea useless.

Rick

Top
zainka
zainka's picture
Level: Hangaround
Joined: Fri. Nov 16, 2001
Posts: 472 View posts
Location: Grimstad, NO(r)WAY!
Posted by zainka: Thu. Mar 6, 2008 - 08:45 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

...

RickB wrote:
Actually I am refering to a situation where the power has been off for period of time sufficient for the ps to drop to zero and ram contents to become uniform.

Thats the problem, you cant possible know that you really have been powered down except for the first time after assembled the PCB.

Regards
Vidar (Z)

----------------------------------------------------------

"The fool wonders, the wise man asks"

Top
RickB
RickB's picture
Level: Posting Freak
Joined: Sun. Jan 30, 2005
Posts: 1347 View posts
Location: Junction City, OR USA
Posted by RickB: Thu. Mar 6, 2008 - 04:41 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Zainka:

Are you suggesting that for test purposes, a voltmeter won't provide that answer?

Rick

Top
S-Sohn
S-Sohn's picture
Level: Posting Freak
Joined: Sun. Aug 22, 2004
Posts: 1612 View posts
Location: Germany
Posted by S-Sohn: Thu. Mar 6, 2008 - 07:04 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Usually you want to generate random numbers automatically. You don't have someone sitting next to the controller who checks if the power supply was off long enough. The controller can't determine it by itself.

An AVR can determine the reset source, but a set PORF in the MCUSR only states that the supply voltage was below 1V. The flag says not if the supply voltage was below the 0.3V limit nor how long the power-on reset was active. And then you still have no guarantee that the SRAM had changed - it only might have changed.

If you do some tests and come to the conclusion that it "works", you only can state that it works with your tested controller in Junction City. Under slightly other conditions (for example fluorescent lamp switched off) your results might become non random or even static.

You might check the power-on behaviour of the SRAM by yourself. Feel free to use my "Random Number Analysis Tool". Yes, I'm skeptic but that doesn't mean that I'm not interested in the results.

Regards
Sebastian

Top
zainka
zainka's picture
Level: Hangaround
Joined: Fri. Nov 16, 2001
Posts: 472 View posts
Location: Grimstad, NO(r)WAY!
Posted by zainka: Fri. Mar 7, 2008 - 09:39 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

RickB wrote:
Zainka:
Are you suggesting that for test purposes, a voltmeter won't provide that answer?

No, I am sugesting that the CPU it self wont know if power has been below 0.3 or not if you dont tell it, thus if controller resets by some reason you dont know if the SRAM has a "random" value.

In a test enviroment you can offcourse use wathever equipment you like but in the real world for a stand alone device you do not have that option.

i.e. Same as sebastian wrote above

Regards
Vidar (Z)

----------------------------------------------------------

"The fool wonders, the wise man asks"

Top
Zaphodikus
Zaphodikus's picture
Level: Wannabe
Joined: Sun. Aug 3, 2008
Posts: 60 View posts
Location: Cambridge, UK
Posted by Zaphodikus: Fri. Dec 26, 2008 - 10:01 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Not nearly as elegant as your beautiful hardware solution, here's part of a dog-simple generator I wrote for a mega8, and I seed my 256 byte list of numbers with a seed based on the amount of time since start-up till the first externally generated input. The faster your clock/timer the better the seed is - in my case (computer game start button) I have a human-input, so the seed is potentially really big.

byte RandomValue(void)
{
static byte randSeed;
//255 random numbers 0..255 generated on 13/12/2008 see http://www.random.org/sequences/
static byte rndTable[256] = {
   140,92,61,119,218,139,167,145,185,42,124,146,210,1,115,240,118,
   90,190,244,102,132,148,63,207,254,104,164,53,98,20,46,209,215,95,
   83,78,192,203,113,229,24,7,206,110,47,21,93,33,13,183,40,196,54,
   51,32,247,122,49,17,11,172,171,222,30,191,16,60,235,242,168,162,
   141,57,56,9,45,107,12,136,180,79,8,27,214,105,121,241,6,37,126,156,
   77,179,169,189,108,10,144,64,44,34,43,232,111,129,219,202,25,23,135,
   181,15,18,39,163,128,165,231,133,109,52,58,89,228,182,41,238,174,151,
   234,0,226,84,114,178,149,246,248,5,76,195,125,224,221,212,255,48,14,
   197,72,120,31,153,233,220,71,237,250,117,82,252,65,74,152,216,75,173,
   227,29,138,88,73,101,127,200,70,249,94,239,38,230,147,97,96,160,217,
   158,176,188,211,161,213,199,26,177,223,204,4,159,68,19,67,85,186,166,
   225,194,130,123,80,131,99,198,253,170,2,91,184,143,154,50,36,245,103,
   137,3,155,22,193,69,106,134,142,35,205,251,187,116,62,87,150,175,208,
   201,157,66,243,28,86,55,236,100,112,59,81
   };

   rndTable[randSeed] ^= NOW(); // modify the current random# entry
   return((byte)(NOW() ^ rndTable[randSeed++])); // bitwise XOR with lo byte of current time for random #
}

...
   // initialize the random number generator from the lo byte of the counter
   i=(byte)NOW();
   while (i--)
      RandomValue();
...

Since I'm only needing a 3-bit random value, this is a pretty cheap solution for the effort I believe (although the DATA budget is a bit high). I am pretty sure that without an external input like a switch debounce, security applications are beyond my simple solution. Bravo.

Conrad Braam - www.softcircuitry.blogspot.com - www.plcsimulator.org
Always start off poorly, that way when you finally figure it out, you can get a few surprise hits in.

Top
timgoh0
timgoh0's picture
Level: Hangaround
Joined: Sun. Apr 6, 2008
Posts: 409 View posts
Location: Singapore
Posted by timgoh0: Sat. Dec 27, 2008 - 12:37 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Zaphodikus, have you considered implementing RC4, seeing that you can fit a 256 element array in memory? RC4 is relatively easy to implement, and you can seed it from your switch bounce.

Top
Zaphodikus
Zaphodikus's picture
Level: Wannabe
Joined: Sun. Aug 3, 2008
Posts: 60 View posts
Location: Cambridge, UK
Posted by Zaphodikus: Sat. Dec 27, 2008 - 09:16 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Thanks, (reading up on crypto again quickly) - RC4 should compile to about 500 bytes with a 256byte stream. And would serve to slow 50% of hackers. Besides, you never stop the determined ones.
I really posted my simple solution here for the n00bs (or newbies) like me who like things simple, although I really need to do some analysis of my solution over the standard library rand() implementation before I make too much noise.
Technically you can create really long streams using simply you own machine-code from reading the flash, but that's non-trivial and 'probably' not going to give good number distribution.

Conrad Braam - www.softcircuitry.blogspot.com - www.plcsimulator.org
Always start off poorly, that way when you finally figure it out, you can get a few surprise hits in.

Top
dbvanhorn
dbvanhorn's picture
Level: Resident
Joined: Thu. Jan 31, 2008
Posts: 700 View posts
Posted by dbvanhorn: Fri. Jun 5, 2009 - 02:50 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

RickB wrote:
Actually I am refering to a situation where the power has been off for period of time sufficient for the ps to drop to zero and ram contents to become uniform. I am not suggesting that the contents of ram would form the basis of a rng, but only does the contents change between power on cycles with enough variation to be used as a seed for a prng, perhaps using a check sum type of accumulation. It may well be that imbalances in each cell will cause each cell to consistently come up in its prefered state at power on, rendering this idea useless.

Rick

I just became aware of this discussion, hopefully you guys are still around.

I had occasion to see this in action with SRAM. (not on an AVR, but I think it's still valid) We had a crypto system that used keys stored in battery backed SRAM. The classic way to restart it was to crash the power supply at the ram chip, but we found some systems refused to loose their keys! Even shorting the ram VCC to ground for weeks wouldn't erase the contents! It's all in how you read the spec sheet. It seems that the proper interpretation is that below voltage X, the ram is not guaranteed to retain information, but there is no low voltage where the ram is guaranteed to loose the information.

We finally solved the problem by putting the keys in a circular buffer and keeping them moving. Apparently when data sits in SRAM for a long time, the states "soak" into the insulators, and bias the cells such that they are very likely to come back up with the data they had before.

On systems that we thought were loosing their memory, we found that partial keys remained, and if you had a couple of uints to play with, you could get to a pretty close approximation of the key by looking at the locations that were the same between the units.

Top
zubianiko
zubianiko's picture
Level: New Member
Joined: Tue. Sep 11, 2012
Posts: 1 View posts
Posted by zubianiko: Wed. Sep 12, 2012 - 09:29 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

hello everybody how i am new here, how do i get started with the ATMEL AVR which has used the serial RS323.i don't have idea of this kit and i am to program the microcontroller ATMEGA8515L, can some body tell me hoe to get started???

Top
Gold Markclawson
clawson's picture
Level: Moderator
Joined: Mon. Jul 18, 2005
Posts: 103883 View posts
Location: (using avr-gcc in) Finchingfield, Essex, England
Posted by clawson: Thu. Sep 13, 2012 - 08:12 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

What on earth has that question got to do with random number generators? Start a separate thread in AVR Forum.

Moderator

Top
fmaimon
fmaimon's picture
Level: Hangaround
Joined: Sat. Jul 28, 2001
Posts: 357 View posts
Location: Rio de Janeiro
Posted by fmaimon: Thu. Jul 2, 2015 - 11:43 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Does anyone still have the original article? I can't find it anywhere...

Felipe Maimon

Top
valusoft
valusoft's picture
Level: Moderator
Joined: Sat. Jul 2, 2005
Posts: 16225 View posts
Location: Melbourne, Australia
Posted by valusoft: Fri. Jul 3, 2015 - 01:59 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 1

Hi Felipe,

 

The file(s) are still on the legacy site... but I have downloaded them and uploaded here for completeness sake.

 

Cheers,

 

Ross

 

Attachment(s): 

PDF icon Stochastic processes in embedded systems – Random number generation.pdf
Package icon Random Number Analysis Tool.zip

Ross McKenzie, Melbourne Australia

Top
fmaimon
fmaimon's picture
Level: Hangaround
Joined: Sat. Jul 28, 2001
Posts: 357 View posts
Location: Rio de Janeiro
Posted by fmaimon: Fri. Jul 3, 2015 - 12:33 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Thank you.

Felipe Maimon

Top