Pages: [1] 2   Go Down
 Author Topic: Using analogRead() on floating pin for random number generator seeding/generator  (Read 861 times) 0 Members and 1 Guest are viewing this topic.
Offline
Jr. Member
Karma: 0
Posts: 57
Nokia 6100 LCD Library
 « on: April 26, 2012, 01:58:29 pm » Bigger Smaller Reset

As a followup of the discussion in this thread, I decided to look at the frequency distribution of values you get by using analogRead() on a floating (unconnected) analog pin.

Background
A "good" random number generator should have a "flat" frequency distribution (equal probability of getting any number in range) - which of course is unlikely in this approach. The better approach is to "seed" the default pseudorandom generator in Arduino library - which does approximate to flat distribution - with some kind of random value - either a timer counter or as discussed in the post, analogRead() on a floating pin. The seed should be a fairly random, wide ranging number.

Test
I generated 1 million values from analogRead() on a floating pin, sent each value to my computer using serial & built a frequency distribution in excel.

Results
99.5% of the 1 million values were distributed between just 38 values out of 1024 possible values. Hmmm.... does not seem to be a wide "seed" range by any means

 Logged

Ardgrafix6100 - A fast, full-featured Arduino graphics driver for Nokia 6100 LCDs http://code.google.com/p/ardgrafix6100/

Global Moderator
UK
Offline
Brattain Member
Karma: 138
Posts: 19067
I don't think you connected the grounds, Dave.
 « Reply #1 on: April 26, 2012, 02:03:59 pm » Bigger Smaller Reset

But what if you build your seed from the LSBs of 32 consecutive reads?
 Logged

Pete, it's a fool looks for logic in the chambers of the human heart.

Global Moderator
Dallas
Offline
Shannon Member
Karma: 119
Posts: 10172
 « Reply #2 on: April 26, 2012, 02:55:50 pm » Bigger Smaller Reset

Quote
I decided to look at the frequency distribution of values you get by using analogRead() on a floating (unconnected) analog pin.

With an Uno?  Did you also test the Mega?  What about the bigger Mega?  The Teensys?  What about when the Teensy is plugged into a breadboard?  What if a neighbor pin is generating a PWM signal?  What if a neighbor pin is HIGH?  Or LOW?  What if the board is powered by USB?  What if the board is powered from VIN?  What happens when the board is placed close to a desk lamp?  Did you try the board near an OttLite?  What happens when your hand is close to the pin?  What about your mobile phone?  Did you test after running the air conditioner a bit so the air is drier?

The point is, an unconnected pin is a terrible way to generate a random number.  Even if you get good results some of the time there is no way to guarantee good results all of the time.  AWOL's suggestion helps in the case that the voltage is changing but it obviously won't help in the copious cases that the voltage is not changing or is heavily influenced by something near.
 Logged

Offline
Jr. Member
Karma: 0
Posts: 57
Nokia 6100 LCD Library
 « Reply #3 on: April 26, 2012, 03:04:58 pm » Bigger Smaller Reset

But what if you build your seed from the LSBs of 32 consecutive reads?

Nice & Noisy across the spectrum! :-) i truncated the 32 bit numbers to 16 bits to generate freq dist attached.

@Coding Badly - just an evaluation of an easy alternative that's not PseudoRandom - ie not replicable if u kinda know the seed range.
 Logged

Ardgrafix6100 - A fast, full-featured Arduino graphics driver for Nokia 6100 LCDs http://code.google.com/p/ardgrafix6100/

Global Moderator
Dallas
Offline
Shannon Member
Karma: 119
Posts: 10172
 « Reply #4 on: April 26, 2012, 03:09:34 pm » Bigger Smaller Reset

Feed the data through this...
http://www.fourmilab.ch/random/
 Logged

Offline
Jr. Member
Karma: 0
Posts: 57
Nokia 6100 LCD Library
 « Reply #5 on: April 26, 2012, 03:21:03 pm » Bigger Smaller Reset

Feed the data through this...
http://www.fourmilab.ch/random/

interesting.... will try over the weekend. Thanks !
 Logged

Ardgrafix6100 - A fast, full-featured Arduino graphics driver for Nokia 6100 LCDs http://code.google.com/p/ardgrafix6100/

Offline
Newbie
Karma: 0
Posts: 3
 « Reply #6 on: November 22, 2012, 09:06:50 am » Bigger Smaller Reset

You are entirely correct. I did extensive research on this and essentially debunked this claim made by Arduino. I did not find a stable and viable way to generate randomness on-board the Arduino.

See the full paper here: http://benedikt.sudo.is/ardrand.pdf
 Logged

Valencia, Spain
Online
Edison Member
Karma: 65
Posts: 2271
 « Reply #7 on: November 22, 2012, 09:11:10 am » Bigger Smaller Reset

Results
99.5% of the 1 million values were distributed between just 38 values out of 1024 possible values. Hmmm.... does not seem to be a wide "seed" range by any means

That's what cryptographers use hash functions for - take a sample of the bottom bits of the values and put them through a hash function (CRC32, MD5...whatever size you need).
 Logged

Offline
Edison Member
Karma: 114
Posts: 2205
 « Reply #8 on: November 22, 2012, 10:50:59 am » Bigger Smaller Reset

Quote
I did extensive research on this and essentially debunked this claim made by Arduino.

Take a look at this thread:

http://arduino.cc/forum/index.php/topic,133261.0.html

The stock analogRead() is essentially incorrectly coded.

I did a Chi-squared test on about 7k data points and it passed with flying color using the revised myanalogRead() provided in that thread. The distribution is also quite uniform.

It also talked about other ways to potentially produce truly random numbers from your arduino. The rc oscillator approach for example can be done with just a resistor + cap + onboard comparator.

The ideal is solid, except it is incorrectly implemented.
 Logged

Global Moderator
Dallas
Offline
Shannon Member
Karma: 119
Posts: 10172
 « Reply #9 on: November 22, 2012, 02:24:01 pm » Bigger Smaller Reset

I did a Chi-squared test on about 7k data points and it passed with flying color using the revised myanalogRead() provided in that thread. The distribution is also quite uniform.

So did I.  The result was a spectacular failure.
 Logged

Netherlands
Offline
Tesla Member
Karma: 90
Posts: 9414
In theory there is no difference between theory and practice, however in practice there are many...
 « Reply #10 on: November 22, 2012, 02:42:13 pm » Bigger Smaller Reset

The floating analog pin is an antenna receiving signals. The ADC converts this to 10 bits. Depending on what the analog pin receives the result will be more or less random.

What does the antenna receive? signals from all electronics in the neighbourhood and beyond ...

True randomness is very difficult to reach imho (although the frequency of this topic popping up in this forum is quite random
 Logged

Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -

Offline
Edison Member
Karma: 114
Posts: 2205
 « Reply #11 on: November 22, 2012, 03:00:13 pm » Bigger Smaller Reset

Quote
Depending on what the analog pin receives the result will be more or less random.

That is true but it ignores the issue that the distribution of that randomness is not desirable - which is the point raised by the paper cited in this thread, putting aside 1) the loading by the adc module; and 2) the inherent issue with the analogRead() call, well documented in a separate thread.

Thus, the lsb approach. It actually doesn't rely on the randomness of a signal on the adc pin, but the randomness of the last digit returned by the adc process. You can tie the pin to a known voltage (Vcc or ground), yet the adc's lsb is unstable.

 Logged

Offline
Edison Member
Karma: 15
Posts: 1009
Arduino rocks
 « Reply #12 on: November 22, 2012, 03:04:13 pm » Bigger Smaller Reset

 Logged

Global Moderator
Dallas
Offline
Shannon Member
Karma: 119
Posts: 10172
 « Reply #13 on: November 22, 2012, 03:20:49 pm » Bigger Smaller Reset

Thus, the lsb approach. It actually doesn't rely on the randomness of a signal on the adc pin, but the randomness of the last digit returned by the adc process. You can tie the pin to a known voltage (Vcc or ground), yet the adc's lsb is unstable.

Nope.  The technique failed again.  Analog input 1 ... failed.  Analog input 2 ... failed.  Speed up the ADC clock ... failed.  Speed it up even more ... failed.  Set it to the value used in the core ... failed.

Quote
It actually doesn't rely on the randomness of a signal on the adc pin...

It may not but it most certainly does not work the way you described.
 Logged

Offline
Newbie
Karma: 0
Posts: 3
 « Reply #14 on: November 22, 2012, 05:59:48 pm » Bigger Smaller Reset

the inherent issue with the analogRead() call, well documented in a separate thread.

Are you referring to http://arduino.cc/forum/index.php/topic,133261.0.html ?

I might pick this up again..
 Logged

 Pages: [1] 2   Go Up