Arduino Forum

Using Arduino => Programming Questions => Topic started by: srinathdevelopment on Apr 26, 2012, 08:58 pm

Title: Using analogRead() on floating pin for random number generator seeding/generator
Post by: srinathdevelopment on Apr 26, 2012, 08:58 pm
As a followup of the discussion in this thread (http://arduino.cc/forum/index.php?topic=103112), 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 :(

Comments / Thoughts welcome.
Title: Re: Using analogRead() on floating pin for random number generator seeding/generator
Post by: AWOL on Apr 26, 2012, 09:03 pm
But what if you build your seed from the LSBs of 32 consecutive reads?
Title: Re: Using analogRead() on floating pin for random number generator seeding/generator
Post by: Coding Badly on Apr 26, 2012, 09:55 pm
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.
Title: Re: Using analogRead() on floating pin for random number generator seeding/generator
Post by: srinathdevelopment on Apr 26, 2012, 10:04 pm

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.
Title: Re: Using analogRead() on floating pin for random number generator seeding/generator
Post by: Coding Badly on Apr 26, 2012, 10:09 pm

Feed the data through this...
http://www.fourmilab.ch/random/
Title: Re: Using analogRead() on floating pin for random number generator seeding/generator
Post by: srinathdevelopment on Apr 26, 2012, 10:21 pm


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


interesting.... will try over the weekend. Thanks !
Title: Re: Using analogRead() on floating pin for random number generator seeding/generator
Post by: benediktkr on Nov 22, 2012, 03:06 pm
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
Title: Re: Using analogRead() on floating pin for random number generator seeding/generator
Post by: fungus on Nov 22, 2012, 03:11 pm

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 :(

Comments / Thoughts welcome.



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).
Title: Re: Using analogRead() on floating pin for random number generator seeding/generator
Post by: dhenry on Nov 22, 2012, 04:50 pm
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.
Title: Re: Using analogRead() on floating pin for random number generator seeding/generator
Post by: Coding Badly on Nov 22, 2012, 08:24 pm
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.
Title: Re: Using analogRead() on floating pin for random number generator seeding/generator
Post by: robtillaart on Nov 22, 2012, 08:42 pm

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 ;)
Title: Re: Using analogRead() on floating pin for random number generator seeding/generator
Post by: dhenry on Nov 22, 2012, 09:00 pm
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.

Obviously, adc'ng a floating pin adds more uncertainty to the process.
Title: Re: Using analogRead() on floating pin for random number generator seeding/generator
Post by: WizenedEE on Nov 22, 2012, 09:04 pm
http://arduino.cc/forum/index.php/topic,108380.0.html
http://arduino.cc/forum/index.php/topic,66206.0.html
Title: Re: Using analogRead() on floating pin for random number generator seeding/generator
Post by: Coding Badly on Nov 22, 2012, 09:20 pm
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.
Title: Re: Using analogRead() on floating pin for random number generator seeding/generator
Post by: benediktkr on Nov 22, 2012, 11:59 pm
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..
Title: Re: Using analogRead() on floating pin for random number generator seeding/generator
Post by: dhenry on Nov 23, 2012, 02:16 am
Yes.

It is complete with a customized version of analogRead() as well as a way to construct an 8-bit type from it.

Later in the thread, i also tried a noisy oscillator approach.
Title: Re: Using analogRead() on floating pin for random number generator seeding/generator
Post by: nickgammon on Nov 23, 2012, 07:54 am

The stock analogRead() is essentially incorrectly coded.
...
The ideal is solid, except it is incorrectly implemented.


In what way? Could you post your corrections please?

Have you posted the corrections to the coding bug list? If not, why not?

http://code.google.com/p/arduino/issues/list